5 ms·
There are a verity of techniques[0] for breaking LFSRSs if you have the outputs. CBC modes security requires that IV's actually be random or indistinguishable
by anologwintermut 13y ago
There are a verity of techniques[0] for breaking LFSRSs if you have the outputs.
CBC modes security requires that IV's actually be random or indistinguishable from random. LFSR output streams are not indistinguishable from random, so the system is on face not secure.
A slight digression: Asking how you'd actually figure that out, in the context of arguing for the security of the system, is the wrong question and a flawed approach to designing cryptographic standards. The same question could be asked about the last packet IV issue Rogaway raised. No one knew at the time how to exploit it then, but it was still a bad idea, as time has proved. I can't see the attack is not the right design philosophy for cryptographic system. To anyone reading this, please please don't use it. It usually leads to broken shit and, if some of the people proposing the standards are malicious, certainly will if they are cleverer than you ( and the NSA probably is).
Now, if you are just curious how to break it: All you have to do is get a few IVs. Suppose the system does encrypt then mac. Let's assume you can get the system to decrypt its own messages and give you the result (this is a weaker version of a chosen cipher text attack and authenticated AES CBC is still safe even with this issue provided IV's are random). Simply replay a given message a few times. The IV changes each time, and hence you get the result of m xor IV_1, m xor IV_2, m xor IV_3, etc. Minimally, this gives you the XOR's of the various IV's with each other which may be enough to calculate the LFSR state. If you happen to know m as well, then you have the IVs. Game over.
Lastly, assuming you don't get a chosen plaintext attack for a protocol with as broad uses as IPSEC seems like a bad idea. Minimally, you clearly get one if it's used to secure http with javascript in it via the same mechanisms as BEAST. You also get one in the case of ICMP echo. File sharing protocols would seem to also readily provide them.
[0]http://crypto.stackexchange.com/questions/5293/cryptanalysis-of-linear-feedback-shift-registers/5309#5309 http://crypto.stackexchange.com/questions/5293/cryptanalysis...
- tptacek 13y agoI don't think I'm sticking up for LFSR-based IVs, but here you need your messages replayed in a pretty specific set of constraints: almost back to back (to get the samples you need to infer the state of the LFSR), and all in the same session. By comparison, Lucky 13 doesn't get to assume those constraints, right? I don't think LFSR CBC IVs are a good idea (though again note that they work in CTR), but they seem like an awfully dumb way to backdoor a standard, and it's straightforward to see how a well-intentioned suggestion could propose their introduction.
- anologwintermut 13y agoOh, to be clear, I don't think the NSA back doored the standard that way. I think the IETF was just doing what they do: ignoring principled cryptographic design because they thought they knew better. Hence why I made the point about the incorrect design philosophy. It happens to be the case that this kind if philosophy is also easy to subvert if someone is malicious. I don't think that's what happened in this case.
- anologwintermut 13y agoTwo technical notes: 1) AES CTR needs a nonce (number used once) not an IV. So a maximal LFSR works up until it repeats. People call it an IV, but strictly speaking IV's need to also be random. 2) I have no idea if you need the replays in a very specific order or not. If you know the m being decrypted, then you always get the IVs. I suspect if given random parts of the output sequence of an LSFRs and the distances between them, it's still easy to recover the seed.
- tptacek 13y agoStrong agree on the distinction between IVs and nonces (I wrote about them in a blog post recently and the confusion annoys me too).
- marshray 13y agoAn LFSR system may not an explicit backdoor, but it's piling pointless complexity upon general confusion by well-intentioned people who were apparently being manipulated and misdiredcted.