7 ms·
Beating Google's kernelCTF PoW using AVX512
- davidfiala 1y agoAbsolutely excellent!
- quasiconnected 1y agoBeautiful use of number theory for the mersenne number modulo!
- Havoc 1y agoSome level of submission difficulty makes sense to keep the garbage submissions at bay but that seems a bit over the top? Can't imagine it makes a big difference to them whether google pays out 50k or 2x 50k for high quality bugs relevant to their company
- jameshart 1y agoRight? This gives the impression that there might be people out there who have developed valid attacks but who are holding back from revealing them because they haven’t optimized their strategy to ensure they can win the CTF race. This seems like a perverse incentive creating suboptimal behavior.
- Retr0id 1y agoThat's why they removed it.
- markasoftware 1y agono it's not. Google still has a long time between each submission cycle, and people are still holding back their exploits in the hope they'll win the next one. It's just a matter of luck now, rather than a matter of optimizing PoW.
- jameshart 1y agoStill a race though. So you can’t rig it by optimizing your proof of work implementation, people are still going to look for an edge. These are CTF experts, exploiting systems is what they do.
- deleted 1y ago[deleted]
- bee_rider 1y agoAt the beginning of the post, they note a default implementation that uses some Google library. So maybe the assumption (which worked out for a while?) was that nobody would bother doing the “over the top” thing and try to beat Google’s library? One option could be to just open up, like, 10 slots instead, right? Most folks might use this implementation (since it has been posted anyway). That way coming second place in the race isn’t so bad…
- internetter 1y agoI honestly don't see why there shouldn't be infinite slots. Google has the money. Right now they've created a backlog of an unknowable number of exploits, sequentually being submitted one by one. It is possible the backlog grows faster than it is emptied. If they let them all through at once, there would be an upfront cost but it wouldn't be like that every time, and the pace at which explitable bugs are fixed increases. The only restriction should be that the first submission of a given bug is the one that gets the reward.
- overfeed 1y ago> Can't imagine it makes a big difference to them whether google pays out 50k or 2x 50k for high quality bugs You're brushing over important implemention details - it's not Google running this program but a specific team inside the company that has a fixed budget, a limited headcount and doing the best with what they have. Your argument is similar to "America has trillions in GDP and could afford to provide twice the number of free treatments to kids with cancer" - it sounds reasonable in aggregate, but breaks down in the specifics; the individual hospital systems, teams and care providers are currently working close to their limits.
- Havoc 1y agoI wasn't brushing over anything - just didn't know that. idk how google internal finances work...
- avidiax 1y ago> The proof of work (implemented here) is a certain verifiable delay function (VDF) known as "sloth". VDFs are cryptographic primitives which prove that a nontrivial amount of time has passed by requiring a long, serial computation. This computation outputs a proof which can be (relatively) quickly verified. Because the computation is serial, scaling to more computational resources (such as more CPU or GPU cores) does not reduce the runtime. Maybe this sort of thing is a market opportunity for the CPU makers? Add two special instructions, one that iterates a sloth given the seed value, and the final instruction that signs the result cryptographically to prove that it was produced by this model of CPU. Perhaps have hardware rate limiting to prevent overclocking. Another idea would be to monitor CPU uptime and sign the uptime + a challenge. The uptime is cleared after signing. This is more like proof of stake, where we are proving that we dedicated n seconds of CPU ownership, while allowing the CPU to be used productively otherwise.
- bawolff 1y agoSo if i unerstand correctly - its 4 second proof of work, and there is a payout once a month. Are there really so many exploits that people are racing to get it every month?
- philodeon 1y agoYes, the myth of Linux kernel security is just that, a myth.
- api 1y agoBut we don’t need safe languages.
- jeffbee 1y agoHow does this myth even exist? There has never been a moment in the history of Linux where it lacked an exploitable flaw. The only uncertainty is that for the last couple of days we aren't sure exactly what the exploit is.
- landr0id 1y agoA myth propelled by people who don't understand security continually saying "Anyone can read the code, therefore it's more secure".
- mmsc 1y agob-b-but, my linux distribution is perfect for multi-tenant/multi-user purposes!!
- udev4096 1y agoMost of the serious security researchers, such as Daniel Micay (lead developer of GrapheneOS), have been quite vocal [0] on how insecure linux is. [0] - https://old.reddit.com/r/GrapheneOS/comments/bddq5u/os_security_ios_vs_grapheneos_vs_stock_android/ekzo6c0/?context=3#ekzo6c0 https://old.reddit.com/r/GrapheneOS/comments/bddq5u/os_secur...
- ramshanker 1y agoAwesome. Just when I was starting to wonder if we finally had a chance to thwart L7 attacks using these PoW tricks.
- IshKebab 1y agoKind of feels like a weird criteria to reduce the number of submissions. In the real world it doesn't matter if an exploit takes 4 seconds or 6. Why not use some other more interesting criteria like how long ago was the bug introduced, or some of the many bonus criteria they have? Just seems weird for it to be a race.
- deleted 1y ago[deleted]
- SunlitCat 1y agoThere is something off with > ...and despite supporting it [AVX512] on consumer CPUs for several generations... I dunno. Before Rocket Lake (11th gen) AVX512 was only available in those enthusiast cpu, xeon cpu or in some mobile processors (which i wouldn't really call consumer cpu). With the 12th gen (and that performance/efficiency core concept), they disabled it after a few months in those core and it was never seen again. I am pretty sure tho, after AMD has some kind of success with AVX512 Intel will reintroduce it again. btw. I am still rocking an Intel i9-11900 cpu in my setup here. ;)
- anematode 1y agofixed :) thx
- SunlitCat 1y agoAwesome! I always love to read about such stuff, especially if it includes playing around with AVX512!
- Aurornis 1y ago> With the 12th gen (and that performance/efficiency core concept), they disabled it after a few months in those core and it was never seen again. The 12th gen CPUs with performance cores didn't even advertise AVX512 support or have it enabled out of the box. They didn't include AVX512 on the efficiency cores for space reasons, so the entire CPU was considered to not have AVX512. It was only through a quirk of some BIOS options that you could disable the efficiency cores and enable AVX512 on the remaining CPU. You had to give up the E-cores as a tradeoff.
- adgjlsfhk1 1y agoIMO this is more a sign of complete dysfunction at Intel. They definitely could have made avx512 instructions trigger a switch to p-cores, and honestly probably could have supported them completely (if slightly slowly) by splitting the same way AMD does on Zen4 and Zen5 C cores. The fact that they shipped P cores and E cores that had different assembly sets is what you get when you have separate teams competing with each other rather than working together to make a good product.
- pittma 1y agoCool stuff! This method is very similar to how AVX-512-optimized RSA implementations work too, as they also have to do Very Large Exponentiations. This paper[1] covers how RSA does its windowing, which includes the formula showing how the window size can be arbitrary. One additional thing AVX-512 RSA implementations do, though, is store the results of the multiplications for the range [0..2^{window-size}) in a table; then, for each window, that result is retrieved from the table[2] and only the shifting/repositioning has to be done. 1. https://dpitt.me/files/sime.pdf https://dpitt.me/files/sime.pdf (hosted on my domain because it's pulled from a journal) 2. https://github.com/aws/aws-lc/blob/9c8bd6d7b8adccdd8af4242e074633ef09b5ecdf/crypto/fipsmodule/bn/asm/rsaz-2k-avx512.pl#L509 https://github.com/aws/aws-lc/blob/9c8bd6d7b8adccdd8af4242e0...
- anematode 1y agoOoh interesting, I should have looked at this while developing.... Looks like that code could definitely use another version for e.g. Zen 5 where using zmm registers would lead to a 2x multiplication throughput. Also the mask registers are bounced to GPRs for arithmetic but that's suboptimal on Zen 4/5. Separately, I'm wondering whether the carries really need to be propagated in one step. (At least I think that's what's going on?) The chance that a carry in leads to an additional carry out beyond what's already there in the high 12 bits is very small, so in my code, I assume that carries only happen once and then loop back if necessary. That reduces the latency in the common case. I guess with a branch there could be timing attack issues though
- pittma 1y agoymms were used here on purpose! With full-width registers, the IFMA insns have a deleterious effect on frequency, at least in the Icelake timeframe.
- anematode 1y agoYe, hence a separate version for CPUs which don't have that problem. Although, maintaining so many of these RSA kernels does seem like a pain. Didn't realize u wrote that code; super cool that it's used in practice!
- supriyo-biswas 1y agoCan anyone tell me how they equated the Python function in the blog to what was shown in the Google's POW implementation? Seems a little difficult to follow.
- bonzini 1y agoThe "exponent = (p + 1) // 4" in the Google code is 2^1277. To raise a number to such a huge power, you square it 1277 times (and that is what the Python function does). That works because if the initial value is "x", each squaring doubles the number of "x"s, and at the end you have 2^1277 of them.
- dcrazy 1y agoFor more on the base-52 representation that this article mentions, see this other post from today’s front page: https://news.ycombinator.com/item?id=44132673 https://news.ycombinator.com/item?id=44132673
- bluelightning2k 1y agoThis is impressive. But it just strikes me as optimizing the wrong thing. A CTF shouldn't be about submission ops. Surely it would be better for everyone if all teams who send the flag within a submission window share the prize
- rfoo 1y agoThat would be a different meta-game and while I didn't think deep into it, I believe the likely outcome is - people are just discouraged and won't consider submitting to kernelCTF.
- kimixa 1y agoI'd also say that this encourages people to sit on exploits instead of reporting them immediately, so they can try to submit it next time if they didn't get it, even without submission timing shenanigans. So it may be actively encouraging the "wrong" thing as well.
- saagarjha 1y agoSure but basically every CTF has this kind of stuff going on
- vlovich123 1y agoI don't understand the purpose of the race. Why not just pay out per unique exploit?
- rfoo 1y agoBoss want a strictly fixed budget for running those cool programs. The rationale behind these programs (at least partially) is about measuring exploits and mitigations dynamics, not buying bugs. And, Linux is just too buggy that if you pay for every 0-day it's basically out of control. Google tried to do so (and to drain people's hoarded bugs) once, ran a limited time promotion with no race, every 0 day counts, got flooded. And at the same time you don't want to piss the community, so here we go.
- 0x0 1y agoIf linux kernel security really is so bad that google had to add a proof-of-work to introduce a 4 second race for 0day submissions, I'm surprised they're ok with still using the Linux kernel as the base for Android.
- udev4096 1y agoAndroid has a vastly improved and better version of linux kernel: https://old.reddit.com/r/GrapheneOS/comments/bddq5u/os_security_ios_vs_grapheneos_vs_stock_android/ekxifpa/?context=3#ekxifpa https://old.reddit.com/r/GrapheneOS/comments/bddq5u/os_secur...
- kimixa 1y agoAll of that's talking about the userspace though?
- rfoo 1y agoNot all. For example kCFI is kernel space. Also, attack surface reduction is a very valid strategy, so it may seem like about the userspace (sandbox for every apps etc) but it could make a big different in how much of the kernel attack surface is exposed.
- deleted 1y ago[deleted]
- mmsc 1y agoAmazing stuff, but also reads like a comedy due to the obstacles to win this challenge. Real rube goldberg stuff.
- initramfs 1y agoneat. what website template is that? I'm looking for a simple blog.
- lawrenceyan 1y agoMath is cool.
- fitzn 1y agoThey won in 3.6 secs, but second place took 3.73 (or 3.74 if being consistent with the winning time). So, did second place also optimize the PoW or were they presumably on an FPGA as well? The previous submission the author describes as being some expensive FPGA one was 4+ seconds. You'd think he'd mention something about how second place on his week was potentially the second fastest submission of all time, no?
- underdeserver 1y agoThe image says (dupe). I'm guessing it's the OP's team, trying to submit as themselves multiple times in parallel.
- yorwba 1y agoFrom the article: "Only the first team who is able to connect to and exploit the server, and submit the flag to a Google Form, receives a payout; any subsequent submissions are marked as duplicates."
- deleted 1y ago[deleted]
- mshockwave 1y agoNitpick: static link won’t give you inlining but only eliminates the overhead of PLT. LTO will give you more opportunities for inlining
- anematode 1y agoConsulted with Will to see exactly what he did and fixed, thx!
- joelthelion 1y agoIt's a bit depressing that after all of these years, professionals only need 3 seconds to own a Linux box...