From the abstract it seems that they are claiming:
1) Boy, those chaotic systems look complex. 2) Gee they can synchronize 3) If we superimpose other chaotic systems on top, then it looks even more complexer.
So something like Walsh codes implemented badly. Walsh codes have nothing to do with cryptography btw.
What they haven''t shown is a lower bound for brute for attack complexity, or why it is resistant to any of the normal attack methods. I don't see why an imposter could not sync to the source the same way the intended recipient does. From the paper, I see several linear systems of equations describing the chaotic oscillators.
This will fall fast when a real cryptographer has go at it.
Agreed, provided such and attack fits in the scenario. I'm just questioning the semantic difference between 'secret salt' and 'key'. I don't see a real difference.
Yes. This is a fairly general problem. People think they can identify 'bad' random from 'good' random sequences, whereas in reality all random sequences are equally likely.
Testing random data is really a case of separating all the sequences into two sets - the bad and the good. The trick is to make the bad set match to well understood error modes of the source, otherwise it's a waste of time and detrimental to the security. You are trying to detect bad random data. You can't. You are trying to identify a bad source, and that is a different thing.
In the iPhone case, I wouldn't even try to dictate pin usage. I'd bolster the post-theft-location services and separate he corporate app, whatever it is to use a better credential but they'd have to pay me to come and help them:)
The 'block generation' term is not very well defined in SP800-90A, B, C or FIPS140-2. It could be interpreted as the output size of the drbg at the SP800-90 boundary or an internal service boundary or the FIPS140 boundary.
Either way, FIPS 4.9.2 introduced algorithmic invariants that reduces the entropy. Depending on the model you choose, it could increase episilon in the full entropy source definition in SP800-90 to above 1 in 2^64, thus breaking SP800-90.
I submitted comments to NIST telling them to fix it.
>And how do you know the NSA's influence didn't simply steamroll over all your professional objections and put the flawed standard in the chips anyway? The NSA has social as well as technological backdoors.
There are publicly published and peer reviewed mathematical proofs that the extraction algorithm (AES-CBC-MAC) and the PRNG algorithm (AES-CTR-DRBG) are secure outside of the NIST specs.
I have also done things to work around all the questionable aspects of the SP800-90 spec. E.G. Massive over reseeding. Not throwing away data marked as unhealthy by the online heath test - mix it in instead, just don't count its entropy. Not implementing FIPS 4.9.2 because it's evil. Not implementing the Dual_EC_DRBG because it was shown to be broke in 2006 and it's stupid anyway being slow and hard to understand. Preventing the personalization strings and 'additional entropy' inputs that could be used as an attack vector or side channel stimulus. Etc.
I've done my best to ensure that if there is some trick up their sleeves in the spec, I've done what's necessary to work around it.
Yup, if you take the output of an RNG and change it, you're probably alright as long as you don't add non random data to the stream or you make changes based on the data values.
E.G. Throw away every third value -- OK Add a zero every three values - Not OK XOR pairs and output a single value - OK Throw away matching pairs - Not OK
I've got a proper crypto mathematician helping me on this. If there's a concrete finding it'll be published, but for now, it's more than enough to want to steer clear of it from a cryptographic perspective.
Given say a 128 bit key made from a FIPS compliant 16 bit output RNG:
Take the upper 32 bits. There are 2^16 values where the upper half==the lower half. For each of those 2^16 values, there are 2^96 values removed from the 2^128 bit number space (I.E. all the combinations of the lower 96 bits with the upper 32 where the halves match). So that's 2^(16+96). So the size of the output space is reduced to 2^128 - 2^112.
Then slide right 16 bits and repeat. Subtract another 2^112, but eliminate the overlap with the first elimination - that's where the math gets tricky. I have it written down at home.
Repeat until you have considered all adjacent 16 bit pairs in the key.
What you end up with is a 2^128 number space with a large number of holes. All present values are equally likely and the probability of all other values is 0. In terms of reducing the brute force search, it's significant, especially if you have a huge data center in Utah.
What may be worse (I don't know) is the simultaneous equations that it creates that are invariant for keys from such a source. Maybe they could be used in a cryptographic attack to help solve the sorts of attack that try to build big systems of simultaneous equations to attack the key schedule.
>Let's take it as read that you are indeed a (possibly former) Intel employee who worked on RDRAND. You may, but I should really stick to bitching about the spec rather than things concerning my employer.
I'm working on persuading NIST and X9.82 to write the specs such that a conformant implementation could expose internal state (like the raw entropy) without violating FIPS140-2 which has all sort of restrictions on that sort of thing. This also has to be done right so that it would make sense in a CPU. This is what's known as a 'hard problem'. If I succeed I expect it would be in 3-5 years and it might be somewhere other than in NIST, since those crypto specs are mostly untrusted toast now except for US government suppliers.
While it's entirely possible to create trustworthy hardware, I don't know how it's possible to convey the trustworthiness. What you can do, which is probably as good as can be done, is to create things such that individually subverted instances of the hardware could be trivially distinguished from the standard issue hardware.
>OTOH if the RNG breaks for whatever reason and keeps returning the same value, then throwing away identical sequential results would prevent the broken values from passing into the algorithm.
Yes, but SP800-90 has proper tests for addressing a crapped out RNG. FIPS140-2 (the enclosing spec) is no place to add ad-hoc tests that reduce the entropy of the output.
>Wait what - you designed Intel's RdRand hardware RNG? Me and many others. I was the primary designer of the crypto processing hardware which intersects with these specs. My public comments on the specs are here .
>So, since there is a lot of paranoia about backdoors in that, is there a backdoor?:P No. I say that as a personal statement. I don't speak for my employer in public forums.
I'm in it to improve security of users from all comers. Good RNGs are a prerequisite for good security and in my design philosophy, security wins over slavish compliance to debatable clauses is specs. I'll seek a waiver for not putting in the back door, but I won't knowingly ship an insecure design.
But it gives you a set of algebraic equations you can use to attack a key composed of multiple of these values. key[31:16] != key[15:0] key[47:32] != key[31:16] key[63:48] != key[47:32]... key[127:112] != key[111:96]
Imagine all the ways you could use these equations to attack they key schedule in a block cipher.
Slashdot Mirror
Because culture is important.
If you make yogurt.
Pardon?
From the abstract it seems that they are claiming:
1) Boy, those chaotic systems look complex.
2) Gee they can synchronize
3) If we superimpose other chaotic systems on top, then it looks even more complexer.
So something like Walsh codes implemented badly. Walsh codes have nothing to do with cryptography btw.
What they haven''t shown is a lower bound for brute for attack complexity, or why it is resistant to any of the normal attack methods. I don't see why an imposter could not sync to the source the same way the intended recipient does. From the paper, I see several linear systems of equations describing the chaotic oscillators.
This will fall fast when a real cryptographer has go at it.
Agreed, provided such and attack fits in the scenario. I'm just questioning the semantic difference between 'secret salt' and 'key'. I don't see a real difference.
Some of think being intolerant of intolerance is just fine. It's the exception to the rule.
Right, but Hash(data=(secret_salt || plaintext)) looks very much like message_authentication_code(key=secret_salt, data=plaintext).
Not all keys are for encryption.
Secret salt? Isn't that what we normally call a key?
I think both creationists and sane people mostly agree the universe exists. Maybe they mean "estimated to have existed".
Correct. It's the fault of HBO.
>Roku and AppleTV have it.
Not if you don't have a HBO cable account. I have a Roku that is HBOgo capable, they will not sell me access.
>The one odd omissions was no HBOGo.
Not really. HBO have been doing their best to prevent willing, paying customers watching their shows for a long time.
If it's obvious they were assaulting people without cause, why haven't they been arrested, prosecuted and thrown in jail?
It doesn't matter why he acts to shit on gay people, it matters that he does.
Yes. This is a fairly general problem. People think they can identify 'bad' random from 'good' random sequences, whereas in reality all random sequences are equally likely.
Testing random data is really a case of separating all the sequences into two sets - the bad and the good. The trick is to make the bad set match to well understood error modes of the source, otherwise it's a waste of time and detrimental to the security. You are trying to detect bad random data. You can't. You are trying to identify a bad source, and that is a different thing.
In the iPhone case, I wouldn't even try to dictate pin usage. I'd bolster the post-theft-location services and separate he corporate app, whatever it is to use a better credential but they'd have to pay me to come and help them :)
The 'block generation' term is not very well defined in SP800-90A, B, C or FIPS140-2. It could be interpreted as the output size of the drbg at the SP800-90 boundary or an internal service boundary or the FIPS140 boundary.
Either way, FIPS 4.9.2 introduced algorithmic invariants that reduces the entropy. Depending on the model you choose, it could increase episilon in the full entropy source definition in SP800-90 to above 1 in 2^64, thus breaking SP800-90.
I submitted comments to NIST telling them to fix it.
>And how do you know the NSA's influence didn't simply steamroll over all your professional objections and put the flawed standard in the chips anyway? The NSA has social as well as technological backdoors.
There are publicly published and peer reviewed mathematical proofs that the extraction algorithm (AES-CBC-MAC) and the PRNG algorithm (AES-CTR-DRBG) are secure outside of the NIST specs.
I have also done things to work around all the questionable aspects of the SP800-90 spec. E.G. Massive over reseeding. Not throwing away data marked as unhealthy by the online heath test - mix it in instead, just don't count its entropy. Not implementing FIPS 4.9.2 because it's evil. Not implementing the Dual_EC_DRBG because it was shown to be broke in 2006 and it's stupid anyway being slow and hard to understand. Preventing the personalization strings and 'additional entropy' inputs that could be used as an attack vector or side channel stimulus. Etc.
I've done my best to ensure that if there is some trick up their sleeves in the spec, I've done what's necessary to work around it.
Yup, if you take the output of an RNG and change it, you're probably alright as long as you don't add non random data to the stream or you make changes based on the data values.
E.G.
Throw away every third value -- OK
Add a zero every three values - Not OK
XOR pairs and output a single value - OK
Throw away matching pairs - Not OK
I've got a proper crypto mathematician helping me on this. If there's a concrete finding it'll be published, but for now, it's more than enough to want to steer clear of it from a cryptographic perspective.
You are assuming they have balls to go deep with.
Here's the basic idea...
Given say a 128 bit key made from a FIPS compliant 16 bit output RNG:
Take the upper 32 bits. There are 2^16 values where the upper half==the lower half. For each of those 2^16 values, there are 2^96 values removed from the 2^128 bit number space (I.E. all the combinations of the lower 96 bits with the upper 32 where the halves match). So that's 2^(16+96). So the size of the output space is reduced to 2^128 - 2^112.
Then slide right 16 bits and repeat. Subtract another 2^112, but eliminate the overlap with the first elimination - that's where the math gets tricky. I have it written down at home.
Repeat until you have considered all adjacent 16 bit pairs in the key.
What you end up with is a 2^128 number space with a large number of holes. All present values are equally likely and the probability of all other values is 0. In terms of reducing the brute force search, it's significant, especially if you have a huge data center in Utah.
What may be worse (I don't know) is the simultaneous equations that it creates that are invariant for keys from such a source. Maybe they could be used in a cryptographic attack to help solve the sorts of attack that try to build big systems of simultaneous equations to attack the key schedule.
>Let's take it as read that you are indeed a (possibly former) Intel employee who worked on RDRAND.
You may, but I should really stick to bitching about the spec rather than things concerning my employer.
I'm working on persuading NIST and X9.82 to write the specs such that a conformant implementation could expose internal state (like the raw entropy) without violating FIPS140-2 which has all sort of restrictions on that sort of thing. This also has to be done right so that it would make sense in a CPU. This is what's known as a 'hard problem'. If I succeed I expect it would be in 3-5 years and it might be somewhere other than in NIST, since those crypto specs are mostly untrusted toast now except for US government suppliers.
While it's entirely possible to create trustworthy hardware, I don't know how it's possible to convey the trustworthiness. What you can do, which is probably as good as can be done, is to create things such that individually subverted instances of the hardware could be trivially distinguished from the standard issue hardware.
>OTOH if the RNG breaks for whatever reason and keeps returning the same value, then throwing away identical sequential results would prevent the broken values from passing into the algorithm.
Yes, but SP800-90 has proper tests for addressing a crapped out RNG. FIPS140-2 (the enclosing spec) is no place to add ad-hoc tests that reduce the entropy of the output.
It's more than that by a lot. The min entropy of a composed number isn't the sum of the shannon entropies of the constituent numbers.
I'd post the math here, but I'm a work and my half written book that addresses this is at home.
>Wait what - you designed Intel's RdRand hardware RNG?
Me and many others. I was the primary designer of the crypto processing hardware which intersects with these specs. My public comments on the specs are here .
>So, since there is a lot of paranoia about backdoors in that, is there a backdoor? :P
No. I say that as a personal statement. I don't speak for my employer in public forums.
I'm in it to improve security of users from all comers. Good RNGs are a prerequisite for good security and in my design philosophy, security wins over slavish compliance to debatable clauses is specs. I'll seek a waiver for not putting in the back door, but I won't knowingly ship an insecure design.
But it gives you a set of algebraic equations you can use to attack a key composed of multiple of these values. ...
key[31:16] != key[15:0]
key[47:32] != key[31:16]
key[63:48] != key[47:32]
key[127:112] != key[111:96]
Imagine all the ways you could use these equations to attack they key schedule in a block cipher.