[saagarjha]

There was an interesting challenge at DEF CON CTF a while back that tested this, actually. It turns out that it is possible to write x86 code that is 1-bit-flip tolerant–that is, a bit flip anywhere in its code can be detected and recovered from with the same output. Of course, finding the sequence took (or so I hear) something like 3600 cores running for a day to discover it ;)

[rfoo]

Nit: not for a day, more like 8 hours, and that's because we were lazy and somebody said he "just happened" to have a cluster with unbalanced resources (mainly used for deep learning, but all GPUs occupied with quite a lot CPUs / RAMs left), so we decided to brute force the last 16 bits :)

Also, the challenge host left useful state (which bit was flipped) in registers before running teams' code, without this I'm not sure if it is even possible.

[saagarjha]

Sure, all's fair in a CTF. That story came to me through the mouths of at least a handful of people, who might have a bit of an incentive to exaggerate given that they hadn't quite been able to get to zero and might be a just a little sour :P

The state was quite helpful, yes–for x86 it seems like a "clean slate" shellcode would be quite difficult, if impossible, to achieve as we saw. However, I am left wondering how other ISAs would fare…perhaps worse, since x86 is notoriously dense. But maybe not? The fixed-width ones would probably be easy to try out, at least.

[rfoo]

Maybe being notoriously dense is not a bad thing? While those ModRM bytes popping up everywhere is annoying as f* (too easy to flip an instruction into a form with almost-guaranteed-to-be-invalid memory access), at least due to the density there won't be reserved bits. For example, in AArch64 if bit 28 and bit 27 is both zero the instruction will almost certainly be an invalid one (hitting unallocated area), and with a single bit flip all branch instructions will have [28:27] = b'00...

[1] https://developer.arm.com/docs/ddi0596/h/top-level-encodings...

[saagarjha]

Right, I was saying that the other ISAs would do wore because they aren't as dense and will hit something undefined much more readily. But the RISCs in general are much less likely to touch memory (only if you do a load/store from a register that isn't clean, maybe). From a glance, MIPS looks like it might work, since the opcode field seems to use all the bits and the remaining bits just encode reg/func/imm in various ways. The one caveat I see is that I think the top bit of opcode seems to encode memory accesses, so you may be forced to deal with at least one.

[exikyut]

This sounds really cool and interesting.

Was any code dumped anywhere?

I found this which corroborates everything you're saying but provides no further details: https://www.cspensky.info/slides/defcon_27_shortman.pdf

[saagarjha]

Oh, hey, it's Chad's slides!

Coverage of the finals is usually much less detailed, unfortunately, since the number of teams is much smaller and the challenges don't necessarily go up. However, https://oooverflow.io/dc-ctf-2020-quals/ has a couple more writeups linked from it; https://dttw.tech/posts/SJ40_7MNS#proof-by-exhaustion from PPP and http://www.secmem.org/blog/2019/08/19/Shellcoding-and-Bitfli... from SeoulPlusBadass.

[exikyut]

I see. Thanks very much for this info.

Binary bitflip resilience is really cool. The radiation-hardened-quine idea (https://codegolf.stackexchange.com/questions/57257/radiation..., https://github.com/mame/radiation-hardened-quine) is cool, but these source-based approaches depend on a perfectly functioning and rather large (Ruby, V8, whole browser) binary stack. A bitflip-protected hex monitor or kernel, on the other hand...