6 ms·

An LFSR? Really? If this person was really NSA-qualified to recommend this stuff, he would have known that known plaintext was the least of your problems. I'm

An LFSR? Really? If this person was really NSA-qualified to recommend this stuff, he would have known that known plaintext was the least of your problems. I'm sorry, tytso. It sounds like you all got expertly socially engineered.

eps 13y ago
Elaborate?
- marshray 13y ago
  Discussion continued in other thread https://news.ycombinator.com/item?id=6347924 https://news.ycombinator.com/item?id=6347924
tptacek 13y ago
What's the attack you're thinking of against CBC with IVs drawn from an LFSR?
- anologwintermut 13y ago
  LFSRs are not cryptographically secure random number generators. So you can, given a few IVs, recover the internal state and predict all subsequent IVs. Then it's just a matter of mounting an (adaptive) chosen plaintext attack against the system knowing what the next IV will be. This is something you can't do against AES CBC mode if the IV is actually random. It fails in the same way if you use the last packet's cipher-text as the IV and there are pauses between packets.
  - tptacek 13y ago
    The point of using an LFSR for IV generation is that it allows you not to transmit the IV on every message. Can you go into more detail about how you, a passive observer, are collecting enough information to reverse the LFSR? (This is aside from the fact that we're talking about an extremely elaborate way to construct a CPA attack against a protocol that does not automatically give attackers chosen plaintext).
    - 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 ago
        I 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.

eps 13y ago

Elaborate?

marshray 13y ago
Discussion continued in other thread https://news.ycombinator.com/item?id=6347924 https://news.ycombinator.com/item?id=6347924

tptacek 13y ago

What's the attack you're thinking of against CBC with IVs drawn from an LFSR?

anologwintermut 13y ago
LFSRs are not cryptographically secure random number generators. So you can, given a few IVs, recover the internal state and predict all subsequent IVs. Then it's just a matter of mounting an (adaptive) chosen plaintext attack against the system knowing what the next IV will be. This is something you can't do against AES CBC mode if the IV is actually random. It fails in the same way if you use the last packet's cipher-text as the IV and there are pauses between packets.
- tptacek 13y ago
  The point of using an LFSR for IV generation is that it allows you not to transmit the IV on every message. Can you go into more detail about how you, a passive observer, are collecting enough information to reverse the LFSR? (This is aside from the fact that we're talking about an extremely elaborate way to construct a CPA attack against a protocol that does not automatically give attackers chosen plaintext).
  - 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 ago
      I 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.