Re: [Cryptography] AES-256- More NIST-y? paranoia
On Oct 8, 2013, at 6:10 PM, Arnold Reinhold wrote: > > On Oct 7, 2013, at 12:55 PM, Jerry Leichter wrote: > >> On Oct 7, 2013, at 11:45 AM, Arnold Reinhold wrote: >>> If we are going to always use a construction like AES(KDF(key)), as Nico >>> suggests, why not go further and use a KDF with variable length output like >>> Keccak to replace the AES key schedule? And instead of making provisions to >>> drop in a different cipher should a weakness be discovered in AES, make >>> the number of AES (and maybe KDF) rounds a negotiated parameter. Given >>> that x86 and ARM now have AES round instructions, other cipher algorithms >>> are unlikely to catch up in performance in the foreseeable future, even >>> with an higher AES round count. Increasing round count is effortless >>> compared to deploying a new cipher algorithm, even if provision is made the >>> protocol. Dropping such provisions (at least in new designs) simplifies >>> everything and simplicity is good for security. >> That's a really nice idea. It has a non-obvious advantage: Suppose the AES >> round instructions (or the round key computations instructions) have been >> "spiked" to leak information in some non-obvious way - e.g., they cause a >> power glitch that someone with the knowledge of what to look for can use to >> read of some of the key bits. The round key computation instructions >> obviously have direct access to the actual key, while the round computation >> instructions have access to the round keys, and with the standard round >> function, given the round keys it's possible to determine the actual key. >> >> If, on the other hand, you use a cryptographically secure transformation >> from key to round key, and avoid the built-in round key instructions >> entirely; and you use CTR mode, so that the round computation instructions >> never see the actual data; then AES round computation functions have nothing >> useful to leak (unless they are leaking all their output, which would >> require a huge data rate and would be easily noticed). This also means that >> even if the round instructions are implemented in software which allows for >> side-channel attacks (i.e., it uses an optimized table instruction against >> which cache attacks work), there's no useful data to *be* leaked. > > At least in the Intel AES instruction set, the encode and decode instruction > have access to each round key except the first. So they could leak that data, > and it's at least conceivable that one can recover the first round key from > later ones (perhaps this has been analyzed?). Knowing all the round keys of > course enables one to decode the data. Still, this greatly increases the > volume o data that must be leaked and if any instructions are currently > "spiked," it is most likely the round key generation assist instruction. One > could include an IV in the initial hash, so no information could be gained > about the key itself. This would work with AES(KDF(key+IV)) as well, > however. > >> >> So this is a mode for safely using possibly rigged hardware. (Of course >> there are many other ways the hardware could be rigged to work against you. >> But with their intended use, hardware encryption instructions have a huge >> target painted on them.) >> >> Of course, Keccak itself, in this mode, would have access to the real key. >> However, it would at least for now be implemented in software, and it's >> designed to be implementable without exposing side-channel attacks. >> >> There are two questions that need to be looked at: >> >> 1. Is AES used with (essentially) random round keys secure? At what level >> of security? One would think so, but this needs to be looked at carefully. > > The fact that the round keys are simply xor'd with the AES state at the start > of each round suggest this likely secure. One would have to examine the KDF > to make sure the there is nothing comparable to the related key attacks on > the AES key set up. > >> 2. Is the performance acceptable? > > The comparison would be to AES(KDF(key)). And in how many applications is key > agility critical? > >> >> BTW, some of the other SHA-3 proposals use the AES round transformation as a >> primitive, so could also potentially be used in generating a secure round >> key schedule. That might (or might not) put security-critical information >> back into the hardware instructions. >> >> If Keccak becomes the standard, we can expect to see a hardware Keccak-f >> implementation (the inner transformation that is the basis of each Keeccak >> round) at some point. Could that be used in a way that doesn't give it the >> ability to leak critical information? >> -- Jerry >> > > Given multi-billion transistor CPU chips with no means to audit them, It's > hard to see how they can be fully trusted. > > Arnold Reinhold __
Re: [Cryptography] AES-256- More NIST-y? paranoia
On Oct 7, 2013, at 12:55 PM, Jerry Leichter wrote: > On Oct 7, 2013, at 11:45 AM, Arnold Reinhold wrote: >> If we are going to always use a construction like AES(KDF(key)), as Nico >> suggests, why not go further and use a KDF with variable length output like >> Keccak to replace the AES key schedule? And instead of making provisions to >> drop in a different cipher should a weakness be discovered in AES, make the >> number of AES (and maybe KDF) rounds a negotiated parameter. Given that x86 >> and ARM now have AES round instructions, other cipher algorithms are >> unlikely to catch up in performance in the foreseeable future, even with an >> higher AES round count. Increasing round count is effortless compared to >> deploying a new cipher algorithm, even if provision is made the protocol. >> Dropping such provisions (at least in new designs) simplifies everything and >> simplicity is good for security. > That's a really nice idea. It has a non-obvious advantage: Suppose the AES > round instructions (or the round key computations instructions) have been > "spiked" to leak information in some non-obvious way - e.g., they cause a > power glitch that someone with the knowledge of what to look for can use to > read of some of the key bits. The round key computation instructions > obviously have direct access to the actual key, while the round computation > instructions have access to the round keys, and with the standard round > function, given the round keys it's possible to determine the actual key. > > If, on the other hand, you use a cryptographically secure transformation from > key to round key, and avoid the built-in round key instructions entirely; and > you use CTR mode, so that the round computation instructions never see the > actual data; then AES round computation functions have nothing useful to leak > (unless they are leaking all their output, which would require a huge data > rate and would be easily noticed). This also means that even if the round > instructions are implemented in software which allows for side-channel > attacks (i.e., it uses an optimized table instruction against which cache > attacks work), there's no useful data to *be* leaked. At least in the Intel AES instruction set, the encode and decode instruction have access to each round key except the first. So they could leak that data, and it's at least conceivable that one can recover the first round key from later ones (perhaps this has been analyzed?). Knowing all the round keys of course enables one to decode the data. Still, this greatly increases the volume o data that must be leaked and if any instructions are currently "spiked," it is most likely the round key generation assist instruction. One could include an IV in the initial hash, so no information could be gained about the key itself. This would work with AES(KDF(key+IV)) as well, however. > > So this is a mode for safely using possibly rigged hardware. (Of course > there are many other ways the hardware could be rigged to work against you. > But with their intended use, hardware encryption instructions have a huge > target painted on them.) > > Of course, Keccak itself, in this mode, would have access to the real key. > However, it would at least for now be implemented in software, and it's > designed to be implementable without exposing side-channel attacks. > > There are two questions that need to be looked at: > > 1. Is AES used with (essentially) random round keys secure? At what level > of security? One would think so, but this needs to be looked at carefully. The fact that the round keys are simply xor'd with the AES state at the start of each round suggest this likely secure. One would have to examine the KDF to make sure the there is nothing comparable to the related key attacks on the AES key set up. > 2. Is the performance acceptable? The comparison would be to AES(KDF(key)). And in how many applications is key agility critical? > > BTW, some of the other SHA-3 proposals use the AES round transformation as a > primitive, so could also potentially be used in generating a secure round key > schedule. That might (or might not) put security-critical information back > into the hardware instructions. > > If Keccak becomes the standard, we can expect to see a hardware Keccak-f > implementation (the inner transformation that is the basis of each Keeccak > round) at some point. Could that be used in a way that doesn't give it the > ability to leak critical information? >-- Jerry > Given multi-billion transistor CPU chips with no means to audit them, It's hard to see how they can be fully trusted. Arnold Reinhold ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] AES-256- More NIST-y? paranoia
Le 7 oct. 2013 à 17:45, Arnold Reinhold a écrit : > other cipher algorithms are unlikely to catch up in performance in the > foreseeable future You should take a look a this algorithm : http://eprint.iacr.org/2013/551.pdf - The block size is variable and unknown from an attacker. - The size of the key has no limit and is unknown from an attacker. - The key size does not affect the algorithm speed (using a 256 bit key is the same as using a 1024 bit key). - The algorithm is much faster than the average cryptographic function. Experimental test showed 600 Mo/s - 4 cycles/byte on an Intel Core 2 Duo P8600 2.40GHz and 1,2 Go/s - 2 cycles/byte on an Intel i5-3210M 2.50GHz. Both CPU had only 2 cores. ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] AES-256- More NIST-y? paranoia
On Oct 4, 2013, at 12:20 PM, Ray Dillinger wrote: > So, it seems that instead of AES256(key) the cipher in practice should be > AES256(SHA256(key)). > Is it not the case that (assuming SHA256 is not broken) this defines a cipher > effectively immune to the related-key attack? So you're essentially saying that AES would be stronger if it had a different key schedule? At 08:59 AM 10/5/2013, Jerry Leichter wrote: - If this is the primitive black box that does a single block encryption, you've about doubled the cost and you've got this messy combined thing you probably won't want to call a "primitive". You've doubled the cost of key scheduling, but usually that's more like one-time than per-packet. If the hash is complex, you might have also doubled the cost of silicon for embedded apps, which is more of a problem. - If you say "well, I'll take the overall key and replace it by its hash", you're defining a (probably good) protocol. But once you're defining a protocol, you might as well just specify random keys and forget about the hash. I'd expect that the point of related-key attacks is to find weaknesses in key scheduling that are exposed by deliberately NOT using random keys when the protocol's authors wanted you to use them. ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] AES-256- More NIST-y? paranoia
On Mon, Oct 07, 2013 at 11:45:56AM -0400, Arnold Reinhold wrote: > If we are going to always use a construction like AES(KDF(key)), as > Nico suggests, why not go further and use a KDF with variable length > output like Keccak to replace the AES key schedule? And instead of Note, btw, that Keccak is very much like a KDF, and KDFs generally produce variable length output. In fact, the HKDF construction [RFC5869] is rather similar to the sponge concept underlying Keccak. It was the use of SHA-256 as a KDF [but not in an HKDF-like construction] that I was objecting to. > making provisions to drop in a different cipher should a weakness be > discovered in AES, make the number of AES (and maybe KDF) rounds a > negotiated parameter. Given that x86 and ARM now have AES round > instructions, other cipher algorithms are unlikely to catch up in > performance in the foreseeable future, even with an higher AES round > count. Increasing round count is effortless compared to deploying a > new cipher algorithm, even if provision is made the protocol. Dropping > such provisions (at least in new designs) simplifies everything and > simplicity is good for security. As Jerry Leichter said, that's a really nice idea. My IANAC concern would be that there might be greatly diminished returns past some number of rounds relative to the sorts of future attacks that that might drastically weaken AES. There are also issues with cipher modes to worry about, so that on the whole I would still like to have algorithm agility (though I don't think you were arguing against it!); but the addition of a cipher strength knob might well be useful. You're quite right that with CPU support for AES it will be very difficult to justify switching to any other cipher... There's always 3AES (a form of round count, but a layer up, and with much bigger step sizes). I suspect it's not AES we'll have problems with, but everything else (asymmetric crypto and cipher modes most likely). Nico -- ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] AES-256- More NIST-y? paranoia
On Oct 7, 2013, at 11:45 AM, Arnold Reinhold wrote: > If we are going to always use a construction like AES(KDF(key)), as Nico > suggests, why not go further and use a KDF with variable length output like > Keccak to replace the AES key schedule? And instead of making provisions to > drop in a different cipher should a weakness be discovered in AES, make the > number of AES (and maybe KDF) rounds a negotiated parameter. Given that x86 > and ARM now have AES round instructions, other cipher algorithms are unlikely > to catch up in performance in the foreseeable future, even with an higher AES > round count. Increasing round count is effortless compared to deploying a new > cipher algorithm, even if provision is made the protocol. Dropping such > provisions (at least in new designs) simplifies everything and simplicity is > good for security. That's a really nice idea. It has a non-obvious advantage: Suppose the AES round instructions (or the round key computations instructions) have been "spiked" to leak information in some non-obvious way - e.g., they cause a power glitch that someone with the knowledge of what to look for can use to read of some of the key bits. The round key computation instructions obviously have direct access to the actual key, while the round computation instructions have access to the round keys, and with the standard round function, given the round keys it's possible to determine the actual key. If, on the other hand, you use a cryptographically secure transformation from key to round key, and avoid the built-in round key instructions entirely; and you use CTR mode, so that the round computation instructions never see the actual data; then AES round computation functions have nothing useful to leak (unless they are leaking all their output, which would require a huge data rate and would be easily noticed). This also means that even if the round instructions are implemented in software which allows for side-channel attacks (i.e., it uses an optimized table instruction against which cache attacks work), there's no useful data to *be* leaked. So this is a mode for safely using possibly rigged hardware. (Of course there are many other ways the hardware could be rigged to work against you. But with their intended use, hardware encryption instructions have a huge target painted on them.) Of course, Keccak itself, in this mode, would have access to the real key. However, it would at least for now be implemented in software, and it's designed to be implementable without exposing side-channel attacks. There are two questions that need to be looked at: 1. Is AES used with (essentially) random round keys secure? At what level of security? One would think so, but this needs to be looked at carefully. 2. Is the performance acceptable? BTW, some of the other SHA-3 proposals use the AES round transformation as a primitive, so could also potentially be used in generating a secure round key schedule. That might (or might not) put security-critical information back into the hardware instructions. If Keccak becomes the standard, we can expect to see a hardware Keccak-f implementation (the inner transformation that is the basis of each Keeccak round) at some point. Could that be used in a way that doesn't give it the ability to leak critical information? -- Jerry ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] AES-256- More NIST-y? paranoia
If we are going to always use a construction like AES(KDF(key)), as Nico suggests, why not go further and use a KDF with variable length output like Keccak to replace the AES key schedule? And instead of making provisions to drop in a different cipher should a weakness be discovered in AES, make the number of AES (and maybe KDF) rounds a negotiated parameter. Given that x86 and ARM now have AES round instructions, other cipher algorithms are unlikely to catch up in performance in the foreseeable future, even with an higher AES round count. Increasing round count is effortless compared to deploying a new cipher algorithm, even if provision is made the protocol. Dropping such provisions (at least in new designs) simplifies everything and simplicity is good for security. Arnold Reinhold On Sat, 5 Oct 2013 19:37, Nico Williams wrote: > On Fri, Oct 4, 2013 at 11:20 AM, Ray Dillinger wrote: >> So, it seems that instead of AES256(key) the cipher in practice should be >> AES256(SHA256(key)). > > More like: use a KDF and separate keys (obtained by applying a KDF to > a root key) for separate but related purposes. > > For example, if you have a full-duplex pipe with a single pre-shared > secret key then: a) you should want separate keys for each direction > (so you don't need a direction flag in the messages to deal with > reflection attacks), b) you should derive a new set of keys for each > "connection" if there are multiple connections between the same two > peers. And if you're using an AEAD-by-generic-composition cipher mode > then you'll want separate keys for data authentication vs. data > encryption. > > The KDF might well be SHA256, but doesn't have to be. Depending on > characteristics of the original key you might need a more complex KDF > (e.g., a PBKDF if the original is a human-memorable password). This > (and various other details about accepted KDF technology that I'm > eliding) is the reason that you should want to think of a KDF rather > than a hash function. > > Suppose some day you want to switch to a cipher with a different key > size. If all you have to do is tell the KDF how large the key is, > then it's easy, but if you have to change the KDF along with the > cipher then you have more work to do, work that might or might not be > easy. Being able to treat the protocol elements as modular has > significant advantages -and some pitfalls- over more monolythic > constructions. > > Nico ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] AES-256- More NIST-y? paranoia
On Sun, Oct 6, 2013 at 9:10 PM, Phillip Hallam-Baker wrote: > I am even > starting to think that maybe we should start using the NSA checksum > approach. > > Incidentally, that checksum could be explained simply by padding prepping an > EC encrypted session key. PKCS#1 has similar stuff to ensure that there is > no known plaintext in there. Using the encryption algorithm instead of the > OAEP hash function makes much better sense. > Wait, am I misunderstanding, or is the NSA recommending that people "checksum" by leaving behind the key encrypted with a backdoor the NSA and the NSA only can read? Wow. —♯ƒ • François-René ÐVB Rideau •Reflection&Cybernethics• http://fare.tunes.org Few facts are more revealing than the direction people travel when they vote with their feet. — Don Boudreaux http://bit.ly/afZgx2 ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] AES-256- More NIST-y? paranoia
On Thu, Oct 3, 2013 at 12:21 PM, Jerry Leichter wrote: > On Oct 3, 2013, at 10:09 AM, Brian Gladman wrote: > >> Leaving aside the question of whether anyone "weakened" it, is it > >> true that AES-256 provides comparable security to AES-128? > > > > I may be wrong about this, but if you are talking about the theoretical > > strength of AES-256, then I am not aware of any attacks against it that > > come even remotely close to reducing its effective key length to 128 > > bits. So my answer would be 'no'. > There are *related key* attacks against full AES-192 and AES-256 with > complexity 2^119. http://eprint.iacr.org/2009/374 reports on improved > versions of these attacks against *reduced round variants" of AES-256; for > a 10-round variant of AES-256 (the same number of rounds as AES-128), the > attacks have complexity 2^45 (under a "strong related sub-key" attack). > > None of these attacks gain any advantage when applied to AES-128. > > As *practical attacks today*, these are of no interest - related key > attacks only apply in rather unrealistic scenarios, even a 2^119 strength > is way beyond any realistic attack, and no one would use a reduced-round > version of AES-256. > > As a *theoretical checkpoint on the strength of AES* ... the abstract says > the results "raise[s] serious concern about the remaining safety margin > offered by the AES family of cryptosystems". > > The contact author on this paper, BTW, is Adi Shamir. Shamir said that he would like to see AES detuned for speed and extra rounds added during the RSA conf cryptographers panel a couple of years back. That is the main incentive for using AES 256 over 128. Nobody is going to be breaking AES 128 by brute force so key size above that is irrelevant but you do get the extra rounds. Saving symmetric key bits does not really bother me as pretty much any mechanism I use to derive them is going to give me plenty. I am even starting to think that maybe we should start using the NSA checksum approach. Incidentally, that checksum could be explained simply by padding prepping an EC encrypted session key. PKCS#1 has similar stuff to ensure that there is no known plaintext in there. Using the encryption algorithm instead of the OAEP hash function makes much better sense. -- Website: http://hallambaker.com/ ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] AES-256- More NIST-y? paranoia
On Fri, Oct 4, 2013 at 11:20 AM, Ray Dillinger wrote: > So, it seems that instead of AES256(key) the cipher in practice should be > AES256(SHA256(key)). More like: use a KDF and separate keys (obtained by applying a KDF to a root key) for separate but related purposes. For example, if you have a full-duplex pipe with a single pre-shared secret key then: a) you should want separate keys for each direction (so you don't need a direction flag in the messages to deal with reflection attacks), b) you should derive a new set of keys for each "connection" if there are multiple connections between the same two peers. And if you're using an AEAD-by-generic-composition cipher mode then you'll want separate keys for data authentication vs. data encryption. The KDF might well be SHA256, but doesn't have to be. Depending on characteristics of the original key you might need a more complex KDF (e.g., a PBKDF if the original is a human-memorable password). This (and various other details about accepted KDF technology that I'm eliding) is the reason that you should want to think of a KDF rather than a hash function. Suppose some day you want to switch to a cipher with a different key size. If all you have to do is tell the KDF how large the key is, then it's easy, but if you have to change the KDF along with the cipher then you have more work to do, work that might or might not be easy. Being able to treat the protocol elements as modular has significant advantages -and some pitfalls- over more monolythic constructions. Nico -- ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] AES-256- More NIST-y? paranoia
On Oct 4, 2013, at 12:20 PM, Ray Dillinger wrote: > So, it seems that instead of AES256(key) the cipher in practice should be > AES256(SHA256(key)). > > Is it not the case that (assuming SHA256 is not broken) this defines a cipher > effectively immune to the related-key attack? Yes, but think about how you would fit it into the question I raised: - If this is the primitive black box that does a single block encryption, you've about doubled the cost and you've got this messy combined thing you probably won't want to call a "primitive". - If you say "well, I'll take the overall key and replace it by its hash", you're defining a (probably good) protocol. But once you're defining a protocol, you might as well just specify random keys and forget about the hash. Pinning down where the primitive ends and the protocol is tricky and ultimately of little value. The takeaway is that crypto algorithms have to be used with caution. Even a perfect block cipher, if used in "the most obvious way" (ECB mode), reveals when it has been given identical inputs. Which is why it's been argued that any encryption primitive (at some level) has to be probabilistic, so that identical inputs don't produce identical outputs. (Note that this implies that output must always be larger then the input!) Still, we have attainable models in which no semantic information about the input leaks (given random keys). Related key attacks rely on a different model which has nothing much to do with practical usage but are obvious from a purely theoretical point of view: OK, we've insulated ourselves from attacks via the plaintext input, how about the key? More broadly there are plenty of attacks (probably including most of the related key attacks; I haven't looked closely enough to be sure) that are based on weaknesses in key scheduling. If you're going to make a cryptographic hash function a fundamental part of your block cipher, why not use it to generate round keys? The only reason I know of - and in practical terms it's not a trivial one - is the substantial performance hit. -- Jerry ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] AES-256- More NIST-y? paranoia
On 10/03/2013 06:59 PM, Watson Ladd wrote: On Thu, Oct 3, 2013 at 3:25 PM, wrote: On Oct 3, 2013, at 12:21 PM, Jerry Leichter wrote: As *practical attacks today*, these are of no interest - related key attacks only apply in rather unrealistic scenarios, even a 2^119 strength is way beyond any realistic attack, and no one would use a reduced-round version of AES-256. >> Expanding a bit on what I said: Ideally, you'd like a cryptographic algorithm let you build a pair of black boxes. I put my data and a key into my black box, send you the output; you put the received data and the same key (or a paired key) into your black box; and out comes the data I sent you, fully secure and authenticated. Unfortunately, we have no clue how to build such black boxes. Even if the black boxes implement just the secrecy transformation for a stream of blocks (i.e., they are symmetric block ciphers), if there's a related key attack, I'm in danger if I haven't chosen my keys carefully enough. So, it seems that instead of AES256(key) the cipher in practice should be AES256(SHA256(key)). Is it not the case that (assuming SHA256 is not broken) this defines a cipher effectively immune to the related-key attack? Bear ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] AES-256- More NIST-y? paranoia
On Thu, Oct 3, 2013 at 3:25 PM, wrote: > On Oct 3, 2013, at 12:21 PM, Jerry Leichter wrote: > > As *practical attacks today*, these are of no interest - related key > attacks only apply in rather unrealistic scenarios, even a 2^119 strength > is way beyond any realistic attack, and no one would use a reduced-round > version of AES-256. > Expanding a bit on what I said: Ideally, you'd like a cryptographic > algorithm let you build a pair of black boxes. I put my data and a key > into my black box, send you the output; you put the received data and the > same key (or a paired key) into your black box; and out comes the data I > sent you, fully secure and authenticated. Unfortunately, we have no clue > how to build such black boxes. Even if the black boxes implement just the > secrecy transformation for a stream of blocks (i.e., they are symmetric > block ciphers), if there's a related key attack, I'm in danger if I haven't > chosen my keys carefully enough. > This is complete and utter bullshit if you can count, or make big enough random numbers if you cannot. Read "Cryptography in NaCl" or Rogaway's analysis of authenticated encryption modes in standards if you don't believe this is a solved problem in theory, or heck, even the GCM or CCM standards. Or Rogaways OCB paper. > > No protocol anyone is likely to use is subject to a related key attack, > but it's one of those flaws that mean we haven't really gotten where we > should. Also, any flaw is a hint that there might be other, more dangerous > flaws elsewhere. > PRP security does not imply security in the related-key model. It also doesn't imply sPRP security. But you don't need it. Now, if you are making a claim about block cipher constructions, go show me why this matters by publishing an attack or some theoretical analysis about related keys leading to good attacks in a stronger setting. > If you think in these terms about asymmetric crypto, the situation is > much, much worse. It turns out that you have to be really careful about > what you shove into those boxes, or you open yourself up to all kinds of > attacks. The classic paper on this subject is > http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=4568385&url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel5%2F4568363%2F4568364%2F04568385.pdf%3Farnumber%3D4568385, > the text for which appears to available only for a fee. > -- Jerry > > ___ > The cryptography mailing list > cryptography@metzdowd.com > http://www.metzdowd.com/mailman/listinfo/cryptography > Sincerely, Watson Ladd -- "Those who would give up Essential Liberty to purchase a little Temporary Safety deserve neither Liberty nor Safety." -- Benjamin Franklin ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] AES-256- More NIST-y? paranoia
On Oct 3, 2013, at 12:21 PM, Jerry Leichter wrote: > As *practical attacks today*, these are of no interest - related key attacks > only apply in rather unrealistic scenarios, even a 2^119 strength is way > beyond any realistic attack, and no one would use a reduced-round version of > AES-256. Expanding a bit on what I said: Ideally, you'd like a cryptographic algorithm let you build a pair of black boxes. I put my data and a key into my black box, send you the output; you put the received data and the same key (or a paired key) into your black box; and out comes the data I sent you, fully secure and authenticated. Unfortunately, we have no clue how to build such black boxes. Even if the black boxes implement just the secrecy transformation for a stream of blocks (i.e., they are symmetric block ciphers), if there's a related key attack, I'm in danger if I haven't chosen my keys carefully enough. No protocol anyone is likely to use is subject to a related key attack, but it's one of those flaws that mean we haven't really gotten where we should. Also, any flaw is a hint that there might be other, more dangerous flaws elsewhere. If you think in these terms about asymmetric crypto, the situation is much, much worse. It turns out that you have to be really careful about what you shove into those boxes, or you open yourself up to all kinds of attacks. The classic paper on this subject is http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=4568385&url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel5%2F4568363%2F4568364%2F04568385.pdf%3Farnumber%3D4568385, the text for which appears to available only for a fee. -- Jerry ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] AES-256- More NIST-y? paranoia
On Wed, Oct 2, 2013 at 8:13 PM, Ray Dillinger wrote: > Leaving aside the question of whether anyone "weakened" it, is it > true that AES-256 provides comparable security to AES-128? No, there's a common misconception that the related key attacks make AES-256 worse than AES-128 because AES-128 is not susceptible to these attacks. The alleged source of this information is a Bruce Schneier blog post (which is fine in and of itself, it's being misinterpreted). In Schneier et al's book Cryptography Engineering he recommends AES-256 over AES-128, despite the flaws, but suggests we might consider looking for a better cipher at this point. The rationale is that AES-256 still provides a wider security margin. -- Tony Arcieri ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] AES-256- More NIST-y? paranoia
On Oct 3, 2013, at 10:09 AM, Brian Gladman wrote: >> Leaving aside the question of whether anyone "weakened" it, is it >> true that AES-256 provides comparable security to AES-128? > > I may be wrong about this, but if you are talking about the theoretical > strength of AES-256, then I am not aware of any attacks against it that > come even remotely close to reducing its effective key length to 128 > bits. So my answer would be 'no'. There are *related key* attacks against full AES-192 and AES-256 with complexity 2^119. http://eprint.iacr.org/2009/374 reports on improved versions of these attacks against *reduced round variants" of AES-256; for a 10-round variant of AES-256 (the same number of rounds as AES-128), the attacks have complexity 2^45 (under a "strong related sub-key" attack). None of these attacks gain any advantage when applied to AES-128. As *practical attacks today*, these are of no interest - related key attacks only apply in rather unrealistic scenarios, even a 2^119 strength is way beyond any realistic attack, and no one would use a reduced-round version of AES-256. As a *theoretical checkpoint on the strength of AES* ... the abstract says the results "raise[s] serious concern about the remaining safety margin offered by the AES family of cryptosystems". The contact author on this paper, BTW, is Adi Shamir. > But, having said that, I consider the use of AES-256 in place of AES-128 > to be driven more by marketing hype than by reality. The theoreticaal > strength of modern cryptographic algorithms is the least of our worries > in producing practical secure systems. 100% agreement. -- Jerry ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] AES-256- More NIST-y? paranoia
On 03/10/2013 04:13, Ray Dillinger wrote: > On 10/02/2013 02:13 PM, Brian Gladman wrote: > >> The NIST specification only eliminated Rijndael options - none of the >> Rijndael options included in AES were changed in any way by NIST. > > Leaving aside the question of whether anyone "weakened" it, is it > true that AES-256 provides comparable security to AES-128? I may be wrong about this, but if you are talking about the theoretical strength of AES-256, then I am not aware of any attacks against it that come even remotely close to reducing its effective key length to 128 bits. So my answer would be 'no'. But, having said that, I consider the use of AES-256 in place of AES-128 to be driven more by marketing hype than by reality. The theoreticaal strength of modern cryptographic algorithms is the least of our worries in producing practical secure systems. Brian Gladman ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] AES-256- More NIST-y? paranoia
I know others have already knocked this one down, but we are now in an area where conspiracy theories are real, so for avoidance of doubt... On 2/10/13 00:58 AM, Peter Fairbrother wrote: AES, the latest-and-greatest block cipher, comes in two main forms - AES-128 and AES-256. AES-256 is supposed to have a brute force work factor of 2^256 - but we find that in fact it actually has a very similar work factor to that of AES-128, due to bad subkey scheduling. This might relate to the related-key discoveries in 2009. Here's an explanation from Dani Nagy that might reach the non-cryptographer: http://financialcryptography.com/mt/archives/001180.html Thing is, that bad subkey scheduling was introduced by NIST ... after Rijndael, which won the open block cipher competition with what seems to be all-the-way good scheduling, was transformed into AES by NIST. So, why did NIST change the subkey scheduling? I don't think they did. Our Java code was submitted as part of the competition, and it only got renamed after the competition. No crypto changes that I recall. iang ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] AES-256- More NIST-y? paranoia
On 10/02/2013 02:13 PM, Brian Gladman wrote: The NIST specification only eliminated Rijndael options - none of the Rijndael options included in AES were changed in any way by NIST. Leaving aside the question of whether anyone "weakened" it, is it true that AES-256 provides comparable security to AES-128? Bear ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] AES-256- More NIST-y? paranoia
On 02/10/2013 13:58, John Kelsey wrote: > On Oct 1, 2013, at 5:58 PM, Peter Fairbrother wrote: > >> AES, the latest-and-greatest block cipher, comes in two main forms - AES-128 >> and AES-256. >> >> AES-256 is supposed to have a brute force work factor of 2^256 - but we >> find that in fact it actually has a very similar work factor to that of >> AES-128, due to bad subkey scheduling. >> >> Thing is, that bad subkey scheduling was introduced by NIST ... after >> Rijndael, which won the open block cipher competition with what seems to be >> all-the-way good scheduling, was transformed into AES by NIST. > > What on Earth are you talking about? AES' key schedule wasn't designed by > NIST. The only change NIST made to Rijndael was not including some of the > alternative block sizes. You can go look up the old Rijndael specs online if > you want to verify this. As someone who was heavily involved in writing the AES specification as eventually used by NIST, I can confirm what John is saying. The NIST specification only eliminated Rijndael options - none of the Rijndael options included in AES were changed in any way by NIST. Brian Gladman ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] AES-256- More NIST-y? paranoia
On Oct 1, 2013, at 5:58 PM, Peter Fairbrother wrote: > AES, the latest-and-greatest block cipher, comes in two main forms - AES-128 > and AES-256. > > AES-256 is supposed to have a brute force work factor of 2^256 - but we find > that in fact it actually has a very similar work factor to that of AES-128, > due to bad subkey scheduling. > > Thing is, that bad subkey scheduling was introduced by NIST ... after > Rijndael, which won the open block cipher competition with what seems to be > all-the-way good scheduling, was transformed into AES by NIST. What on Earth are you talking about? AES' key schedule wasn't designed by NIST. The only change NIST made to Rijndael was not including some of the alternative block sizes. You can go look up the old Rijndael specs online if you want to verify this. > -- Peter Fairbrother --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] AES-256- More NIST-y? paranoia
On Oct 1, 2013, at 5:58 PM, Peter Fairbrother wrote: > [and why doesn't AES-256 have 256-bit blocks???] Because there's no security advantage, but a practical disadvantage. When blocks are small enough, the birthday paradox may imply repeated blocks after too short a time to be comfortable. Whether this matters to you actually depends on how you use the cipher. If you're using CBC, for example, you don't want to ever see a repeated block used with a single key. With 64-bit blocks (as in DES), you expect to see a repetition after 2^32 blocks or 2^38 bytes, which in a modern network is something that might actually come up. A 128-bit block won't see a collision for 2^64 blocks or 2^71 bytes, which is unlikely to be an issue any time in the foreseeable future. Note that many other modes are immune to this particular issue. For example, CTR mode with a 64-bit block won't repeat until you've used it for 2^64 blocks (though you would probably want to rekey earlier just to be safe). I know of no other vulnerability that are related to the block size, though they may be out there; I'd love to learn about them. On the other hand, using different block sizes keeps you from easily substituting one cipher for another. Interchanging AES-128 and AES-256 - or substituting in some entirely different cipher with the same block size - is straightforward. (The changed key length can be painful, but since keys are fairly small anyway you can just reserve key space large enough for any cipher you might be interested int.) Changing the block size affects much more code and may require changes to the protocol (e.g., you might need to reserve more bits to represent the length of a short final block). -- Jerry ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
[Cryptography] AES-256- More NIST-y? paranoia
AES, the latest-and-greatest block cipher, comes in two main forms - AES-128 and AES-256. AES-256 is supposed to have a brute force work factor of 2^256 - but we find that in fact it actually has a very similar work factor to that of AES-128, due to bad subkey scheduling. Thing is, that bad subkey scheduling was introduced by NIST ... after Rijndael, which won the open block cipher competition with what seems to be all-the-way good scheduling, was transformed into AES by NIST. So, why did NIST change the subkey scheduling? I don't know. Inquiring minds ... NIST have previously changed cipher specs under NSA guidance, most famously for DES, with apparently good intentions then - but with NSA and it's two-faced mission, we always have to look at capabilities, not intentions. -- Peter Fairbrother [and why doesn't AES-256 have 256-bit blocks???] ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography