Re: Question w.r.t. AES-CBC IV
Unfortunately I can't remember the author, but there was a paper showing that an encrypted counter was secure to use as IVs for CBC mode. So encrypting a shorter random IV should also be secure. Greg. On 2010 Jun 2, at 9:36 , Ralph Holz wrote: Dear all, A colleague dropped in yesterday and confronted me with the following. He wanted to scrape off some additional bits when using AES-CBC because the messages in his concept are very short (a few hundred bit). So he was thinking about a variant of AES-CBC, where he uses just 32 (random) bits as a source for the IV. These are encrypted with AES and then used as the actual IV to feed into the CBC. As a result, he does not need to send a 128 bit IV to the receiver but just the 32 bit. His argument was that AES basically is used as an expansion function for the IV here, with the added benefit of encryption. On the whole, this should not weaken AES-CBC. Although he was not sure if it actually would strengthen it. While I am prepared to buy this argument (I am not a cryptographer...), I still felt that the argument might not be complete. After all, 32 bits don't provide much randomness, and I wasn't sure if this, overall, would not lead to more structure in the ciphercode - which might in turn give an attacker more clues with respect to the key. Are there any opinions on this? Regards, Ralph - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Possibly questionable security decisions in DNS root management
On 2009 Oct 19, at 9:15 , Jack Lloyd wrote: On Sat, Oct 17, 2009 at 02:23:25AM -0700, John Gilmore wrote: DSA was (designed to be) full of covert channels. And, for that matter, one can make DSA deterministic by choosing the k values to be HMAC-SHA256(key, H(m)) - this will cause the k values to be repeated, but only if the message itself repeats (which is fine, since seeing a repeated message/signature pair is harmless), or if one can induce collisions on HMAC with an unknown key (which seems a profoundly more difficult problem than breaking RSA or DSA). Ah, but this doesn't solve the problem; a compliant implementation would be deterministic and free of covert channels, but you can't reveal enough information to convince someone *else* that the implementation is compliant (short of using zero-knowledge proofs, let's not go there). So a hardware nubbin could still leak information. Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Certainty
On 2009 Aug 19, at 3:28 , Paul Hoffman wrote: At 5:28 PM -0400 8/19/09, Perry E. Metzger wrote: I believe attacks on Git's use of SHA-1 would require second pre- image attacks, and I don't think anyone has demonstrated such a thing for SHA-1 at this point. None the less, I agree that it would be better if Git eventually used better hash functions. Attacks only get better with time, and SHA-1 is certainly creaking. I understand that creaking is not a technical cryptography term, but certainly is. When do we become certain that devastating attacks on one feature of hash functions (collision resistance) have any effect at all on even weak attacks on a different feature (either first or second preimages)? This is a serious question. Has anyone seen any research that took some of the excellent research on collision resistance and used it directly for preimage attacks, even with greatly reduced rounds? Not directly, as far as I know. But some research and success on preimages, yes. The longer that MD5 goes without any hint of preimage attacks, the less certain I am that collision attacks are even related to preimage attacks. They aren't particularly related, but there was a presentation at Eurocrypt about MD5 preimages earlier this year. Or maybe it was MD4... Greg. Of course, I still believe in hash algorithm agility: regardless of how preimage attacks will be found, we need to be able to deal with them immediately. --Paul Hoffman, Director --VPN Consortium - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Crypto '09 rump session summary?
Target collisions for MD5 can be calculated in seconds on a laptop, based on just a small change in the first block of input. There was also a semi-successful demo of MD5 certificate problems; you could join the special wireless network, and any https connection would be silently proxied using the fake CA certificate generated a few months ago. (You had to set your clock back to 2004, though, since the CA certificate was intentionally generated to be long expired). The SHA-1 attack complexity of 2^52 was a correct improvement to an incorrect result. Don't currently have an accurate estimate; IIUC it's bounded above by 2^56. The related-key attacks on AES have been extended to AES-192, and also to some sort of non-standard AES-128, but it wasn't clear to me what it was that they did. AES-128 as standardized is still (and likely to remain) safe. The National Museum of Computing (at Bletchley Park in England) is doing interesting stuff, but is still starved for cash. There is a 501(c)3 you can donate to for tax deductibility and corporate matching, if people want to donate. Don't run algorithms on secret data in the cloud; it's not too difficult for an attacker to get themselves assigned to the same machine and use timing/cache attacks to recover your keys. (At that point I was tired and inebriated and left.) Greg. On 2009 Aug 19, at 2:01 , Perry E. Metzger wrote: Watching the rump session online briefly last night, I saw that some interesting new results on MD5 and AES seem to have been discussed at the conference. Would anyone care to give us a brief overview for the mailing list? Perry -- Perry E. Metzgerpe...@piermont.com - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: SHA-1 collisions now at 2^{52}?
On 2009 Apr 30, at 4:31 , Perry E. Metzger wrote:
Eric Rescorla e...@networkresonance.com writes:
McDonald, Hawkes and Pieprzyk claim that they have reduced the
collision
strength of SHA-1 to 2^{52}.
Slides here:
http://eurocrypt2009rump.cr.yp.to/
837a0a8086fa6ca714249409ddfae43d.pdf
Thanks to Paul Hoffman for pointing me to this.
This is a very important result. The need to transition from SHA-1
is no
longer theoretical.
It already wasn't theoretical... if you know what I mean. The writing
has been on the wall since Wang's attacks four years ago.
BTW, it is my (our) opinion that the current attacks can't be extended
to the SHA-2 family, due to the avalanche effect in the data
expansion, which is significantly different to the designs of its
ancestors. SHA-2 would need a new breakthrough.
Greg.
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Decimal encryption
One of the earlier messages (I lost it) said that Philipp said that there was information that could be used as a nonce. In that case, I would recommend a stream cipher used to generate 133 bits at a time; if the lump of bits represents an integer in the correct range, add it modulo 10^40... otherwise generate more bits. This is about as simple as it gets. Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Decimal encryption
Philipp Gühring wrote: Hi, G'day Philipp, I am searching for symmetric encryption algorithms for decimal strings. Let's say we have various 40-digit decimal numbers: 2349823966232362361233845734628834823823 3250920019325023523623692235235728239462 0198230198519248209721383748374928601923 As far as I calculated, a decimal has the equivalent of about 3,3219 bits, so with 40 digits, we have about 132,877 bits. Now I would like to encrypt those numbers in a way that the result is a decimal number again (that's one of the basic rules of symmetric encryption algorithms as far as I remember). Since the 132,877 bits is similar to 128 bit encryption (like eg. AES), I would like to use an algorithm with a somewhat comparable strength to AES. But the problem is that I have 132,877 bits, not 128 bits. And I can't cut it off or enhance it, since the result has to be a 40 digit decimal number again. Does anyone know a an algorithm that has reasonable strength and is able to operate on non-binary data? Preferrably on any chosen number-base? There is a fairly standard technique for handling things like this. 1. encode your number N into a 133-bit string S 2. encrypt S with your favourite 133-bit block cipher (see below) 3. decode S to a number N' 4. if N' = 10^40, goto 2 (that is, re-encrypt until it is in range) 5. N' is your answer. This is uniquely invertible, although a little slow (since on average it will take 8.9% or so more encryptions because of the inner loop, and some side-channel information leaks when it does the extra encryptions. Decryption is exactly the same operation except step 2 uses decryption mode of the block cipher. So, you don't have a 133-bit block cipher lying around? No worries, I'll sell you one ;-). Actually that is easy too. Take a trustworthy 128-bit block cipher like AES. To encrypt, do: 1. Encrypt the first 128 bits (ECB mode) 2. Encrypt the last 128 bits (also ECB mode). To decrypt, do decryptions in the reverse order, obviously. It's easy to see that this is a secure permutation if AES itself is, depending on your definition of secure; if you add a third step, to re-encrypt the first 128 bits, it is truly secure. (Without the third step, tweaking a bit in the first 5 bits will often leave the last 5 unchanged on decryption, which is clearly a distinguishing attack; the third encryption makes it an all-or-nothing transform.) I believe the above gives you a secure enough block cipher on 40 digit strings, and if you only ever encrypt single chunks, ECB mode should be fine... of course that depends on the real threat analysis of your system. It does about 2.19 AES encryptions per 40 digits, should be fast enough. hope that helps, Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Decimal encryption
Hal Finney wrote: So, you don't have a 133-bit block cipher lying around? No worries, I'll sell you one ;-). Actually that is easy too. Take a trustworthy 128-bit block cipher like AES. To encrypt, do: 1. Encrypt the first 128 bits (ECB mode) 2. Encrypt the last 128 bits (also ECB mode). I didn't understand this at first, but I finally saw that the point is to do the encryptions in-place; step 1 replaces the first 128 bits of the data with the encryption, and similarly for step 2. This is equivalent to doing CBC mode with a fixed IV of 0, and ciphertext stealing for the final partial block of 5 bits. Yes, I guess it is... hadn't thought of it that way. But yes, I confirm that I meant to do the encryptions in place. To decrypt, do decryptions in the reverse order, obviously. It's easy to see that this is a secure permutation if AES itself is, depending on your definition of secure; if you add a third step, to re-encrypt the first 128 bits, it is truly secure. (Without the third step, tweaking a bit in the first 5 bits will often leave the last 5 unchanged on decryption, which is clearly a distinguishing attack; the third encryption makes it an all-or-nothing transform.) I am not familiar with the security proof here, do you have a reference? Or is it an exercise for the student? It's a degenerate case of Rivest's All-or-nothing transform (which applies to larger, multi-block blocks, if you know what I mean :-) ). I believe he gave a security proof, some 6ish years ago. But I could be confabulating. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cube cryptanalysis?
David Wagner wrote: It's a brilliant piece of research. If you weren't at CRYPTO, you missed an outstanding talk (and this wasn't the only one!). Yes, the program chair and committee did a great job. Whatsisname? Oh, yeah, David Wagner. Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cube cryptanalysis?
Yes, of course Adi is correct, but I blame you for reading what I wrote and not what I meant... :-) Adi mentioned that the slides and paper will go online around the deadline for Eurocrypt submission; it will all become much clearer than my wounded explanations then. thanks and regards, Greg. (cc:ed back to the crypto list) Matt Ball wrote: Hi Greg, I don't think we've met, but I'm also at the crypto conference, and happened to be sitting next to Adi and showed him this e-mail thread. He mentioned that the following text was a little misleading: On Wed, Aug 20, 2008 at 2:40 PM, Greg Rose [EMAIL PROTECTED] mailto:[EMAIL PROTECTED] wrote: Basically the method focuses on terms of the polynomial in which only one secret bit of the key appears, and many of the non-secret bits. Using chosen (or lucky) plaintexts, vary all but one of the non-secret bits, and sum the output bits (mod 2, that is, XOR). Fix the other non-secret bit to 1. The attack does not vary only one of the non-secret bits, but rather some subset of the non-secret bits. The other non-secret bits need to stay constant. This could happen in counter mode, for example, when the nonce is fixed and only the counter field varies. I'll let Adi double-check this statement for correctness... :) Cheers, -Matt Previous message: James Muir wrote: Greg Rose wrote: Basically, any calculation with inputs and outputs can be represented as an (insanely complicated and probably intractable) set of binary multivariate polynomials. So long as the degree of the polynomials is not too large, the method allows most of the nonlinear terms to be cancelled out, even though the attacker can't possibly handle them. Then you solve a tractable system of linear equations to recover key (or state) bits. I would like to know how Dinur and Shamir's work differs from Courtois' previous work on Algebraic cryptanalysis of block ciphers. It is a refinement of Courtois' technique? Greg, do you, or someone else have some insight on this? I spent about an hour trying to come up with a short but legible explanation of the technique, and failed. Sorry about that. I can visualize it, and could probably reproduce Adi's drawings on a whiteboard, but not with typing. The following is as close as I could come. Basically the method focuses on terms of the polynomial in which only one secret bit of the key appears, and many of the non-secret bits. Using chosen (or lucky) plaintexts, vary all but one of the non-secret bits, and sum the output bits (mod 2, that is, XOR). Fix the other non-secret bit to 1. Now all the terms that involve less than the full complement of non-secret bits will appear an even number of times in the sum, and because it is mod 2, they will all cancel out! The only terms that will be left are the ones with one secret bit, and all ones for the non-secret bits... but that is linear in the secret bit! So what you are left with is a simple, linear, polynomial relating unknown (key) bits. Gather enough such equations, just a few more than the number of key bits will do, and solve the linear system in trivial time. Note that you had to have 2^(d-2) chosen plaintexts to sum over for each of the equations... that's where the complexity comes from. The attack is called Cube because in the case where d=4, each time you sum over all of the varying known bits, it can be visualized as the face of a cube, the corners of which are the possibilities for the 3 known inputs. Hope that helps. Note that the formula I typed from memory for the complexity was wrong... it's O(n * 2^(d-2)), if the above is correct. For anything more than this, you'll have to wait for the paper. Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] mailto:[EMAIL PROTECTED] -- Thanks! Matt Ball, IEEE P1619.x SISWG Chair M.V. Ball Technical Consulting, Inc. Phone: 303-469-2469, Cell: 303-717-2717 http://www.mvballtech.com http://www.linkedin.com/in/matthewvball - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cube cryptanalysis?
Steven M. Bellovin wrote: Greg, assorted folks noted, way back when, that Skipjack looked a lot like a stream cipher. Might it be vulnerable? Hmmm, interesting. I'm getting increasingly closer to talking through my hat, but... Skipjack has an 8x8 S-box, so by definition the maximum degree of the polynomials for a trip through the S-box is 8 (but it could be lower... I don't know off the top of my head). There are 32 rounds, but each word gets hit only in every fourth round... that is, each word gets hit 8 times. So the degree from beginning to end should be 64, probably out of range. However Adi mentioned a variant where you sort of meet in the middle, where you have one set of equations to get to some particular bit in the middle from the plaintext, and you get to the same bit backwards from the output bits, and by definition the two polynomials are equal. This should halve the degree, to around 32, if I've understood correctly. With an 80 bit key the attack might be more efficient than brute force. Again from memory the complexity was O(n*2^2d+n^2), (n-bit key, d degree) for skipjack this might be about 2^70. Skipjack's nearly non-existent key schedule really helps. This might be a good project for a grad student. Enough speculation from me... but I'll try to corner Adi later and ask him some of the questions that have been burning in my mind. Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cube cryptanalysis?
someone wrote: what about RC4, the most important stream cipher in the Internet world? So I cornered Adi for a while. Of course he'd thought of almost everything I wanted to ask. You're not the first to think of RC4 (I confess I wasn't either). No, if you try to express shuffling as a polynomial, its degree is off the planet. As for some of the other things I said: when you compound s-boxes, the degrees multiply. For some reason I can no longer explain, I thought they added. So there's good news and bad news. The good news is that my/our old designs are safe: degrees ~= 64. The bad news (if you think of it that way), Skipjack is also safe, the degree is 4096 (not 32), that is, 8^4 not 8*4. ... and I realised I forgot to mention probably the most interesting thing about the attack! It treats the cipher as a black box. You don't need to know anything about it, except access to an implementation that will accept variable keys for the precomputation phase. If it isn't vulnerable, the precomputation fails. But if it is vulnerable, you'll recover the keys even though you have no idea what the algorithm itself is. Somewhere along there you discover a distinguishing attack. Amazing. Someone else suggested Bluetooth (E0). Probably not vulnerable because the key scheduling is high degree, but neither Adi nor I can remember enough detail to be sure; the keystream generator would be vulnerable if the key-IV scheduling was simple enough. I'm not sure whether Adi's invited talk or Wang's rump session (breaking MD5, SHA-0, HAVAL, ...) is the high point of Crypto for me... I think Cube. Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cube cryptanalysis?
James Muir wrote: Greg Rose wrote: Basically, any calculation with inputs and outputs can be represented as an (insanely complicated and probably intractable) set of binary multivariate polynomials. So long as the degree of the polynomials is not too large, the method allows most of the nonlinear terms to be cancelled out, even though the attacker can't possibly handle them. Then you solve a tractable system of linear equations to recover key (or state) bits. I would like to know how Dinur and Shamir's work differs from Courtois' previous work on Algebraic cryptanalysis of block ciphers. It is a refinement of Courtois' technique? Greg, do you, or someone else have some insight on this? I spent about an hour trying to come up with a short but legible explanation of the technique, and failed. Sorry about that. I can visualize it, and could probably reproduce Adi's drawings on a whiteboard, but not with typing. The following is as close as I could come. Basically the method focuses on terms of the polynomial in which only one secret bit of the key appears, and many of the non-secret bits. Using chosen (or lucky) plaintexts, vary all but one of the non-secret bits, and sum the output bits (mod 2, that is, XOR). Fix the other non-secret bit to 1. Now all the terms that involve less than the full complement of non-secret bits will appear an even number of times in the sum, and because it is mod 2, they will all cancel out! The only terms that will be left are the ones with one secret bit, and all ones for the non-secret bits... but that is linear in the secret bit! So what you are left with is a simple, linear, polynomial relating unknown (key) bits. Gather enough such equations, just a few more than the number of key bits will do, and solve the linear system in trivial time. Note that you had to have 2^(d-2) chosen plaintexts to sum over for each of the equations... that's where the complexity comes from. The attack is called Cube because in the case where d=4, each time you sum over all of the varying known bits, it can be visualized as the face of a cube, the corners of which are the possibilities for the 3 known inputs. Hope that helps. Note that the formula I typed from memory for the complexity was wrong... it's O(n * 2^(d-2)), if the above is correct. For anything more than this, you'll have to wait for the paper. Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cube cryptanalysis?
Perry E. Metzger wrote: According to Bruce Schneier... http://www.schneier.com/blog/archives/2008/08/adi_shamirs_cub.html ...Adi Shamir described a new generalized cryptanalytic attack at Crypto today. Anyone have details to share? Stunningly smart, and an excellent and understandable presentation. Basically, any calculation with inputs and outputs can be represented as an (insanely complicated and probably intractable) set of binary multivariate polynomials. So long as the degree of the polynomials is not too large, the method allows most of the nonlinear terms to be cancelled out, even though the attacker can't possibly handle them. Then you solve a tractable system of linear equations to recover key (or state) bits. His example was an insanely complicated theoretical LFSR-based stream cipher; recovers keys with 2^28 (from memory, I might be a little out), with 2^40 precomputation, from only about a million output bits. They are working on applying the technique to real ciphers... Trivium, which is a well-respected E*Stream cipher, is in their sights. My team's last LFSR-based cipher, SOBER-128, is I think well respected and fairly conservative. I can say that we are extremely lucky in the way we load the key and IV, that the degree of the polynomials piles up and is quite high; once the cipher is actually running, there are output bits which would have been attackable (degree 16 is certainly tractable), except for lucky use of addition as well as s-boxes... the addition carries represent high degree terms. Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cube cryptanalysis?
Perry E. Metzger wrote: Greg Rose [EMAIL PROTECTED] writes: His example was an insanely complicated theoretical LFSR-based stream cipher; recovers keys with 2^28 (from memory, I might be a little out), with 2^40 precomputation, from only about a million output bits. They are working on applying the technique to real ciphers... Trivium, which is a well-respected E*Stream cipher, is in their sights. My team's last LFSR-based cipher, SOBER-128, is I think well respected and fairly conservative. I can say that we are extremely lucky in the way we load the key and IV, that the degree of the polynomials piles up and is quite high; once the cipher is actually running, there are output bits which would have been attackable (degree 16 is certainly tractable), except for lucky use of addition as well as s-boxes... the addition carries represent high degree terms. There are a bunch of deployed mobile phone ciphers that are in the stream cipher class -- any thoughts on whether any of them look vulnerable? With the disclaimer that I think I understand the attack but might nevertheless have misunderstood something: A5/1 is difficult for this attack to apply to because of the clock-controlled shift registers (Adi said this). A5/3 and the current WCDMA f8/f9 is based on Kasumi, and I'd be surprised if the attack applys. Ditto for the AES based CDMA security. The soon-to-be-adopted spare WCDMA algorithm, SNOW-3G, may be vulnerable if used in other ways, but appears to me to be secure in the way it is used in 3G phones. Again, somewhat lucky though, the attack comes very close to working. I believe the appropriate standards committee is going to go off and check this very closely (I spoke to one of the members). Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Using a MAC in addition to symmetric encryption
Erik Ostermueller wrote: If I exchange messages with a system and the messages are encrypted with a symmetric key, what further benefit would we get by using a MAC (Message Authentication Code) along with the message encryption? Being new to all this, using the encrytpion and MAC together seem redundant. One of my favourite papers, by Steve Bellovin, is at http://www.usenix.org/publications/library/proceedings/sec96/bellovin.html It shows a number of ways in which IPsec with encryption but no integrity can fail. Abstract: The Internet Engineering Task Force (IETF) is in the process of adopting standards for IP-layer encryption and authentication (IPSEC). We describe a number of attacks against various versions of these protocols, including confidentiality failures and authentication failures. The implications of these attacks are troubling for the utility of this entire effort. Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Bletchley Park museum in financial trouble
Perry E. Metzger wrote: A wonderful place. I hope it manages to pull through. http://resources.zdnet.co.uk/articles/imagegallery/0,102003,39415278,00.htm?r=234 There is a mechanism whereby US donors can send tax deductible donations to the trust. Go to http://www.cafamerica.org and search for the Codes and Ciphers Heritage Trust. I helped them rebuild Colossus a couple of years ago, and have just donated some more (thanks, Perry). Note, though, minimum donation is $500. Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Quantum Cryptography
At 10:44 -0700 2007/06/22, Ali, Saqib wrote: ...whereas the key distribution systems we have aren't affected by eavesdropping unless the attacker has the ability to perform 2^128 or more operations, which he doesn't. Paul: Here you are assuming that key exchange has already taken place. But key exchange is the toughest part. That is where Quantum Key Distribution QKD comes in the picture. Once the keys are exchanged using QKD, you have to rely on conventional cryptography to do bulk encryption using symmetric crypto. Using Quantum Crypto to do bulk encryption doesn't make any sense. It is only useful in key distribution. To be used in key distribution I have to have laid a private optical fiber between me and my correspondent. I could have paid a lot less for an armored truck to carry the key for me. (I know you can do QKD without the fiber these days, but how do you know that you agreed the key with the person you think you agreed it with? It's turtles all the way down.) Greg. saqib http://www.linkedin.com/in/encryption - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Can you keep a secret? This encrypted drive can...
At 17:58 -0500 2006/11/08, Leichter, Jerry wrote: No, SHA-1 is holding on (by a thread) because of differences in the details of the algorithm - details it shares with SHA-256. I don't think anyone will seriously argue that if SHA-1 is shown to be as vulnerable as we now know ND5 to be, then SHA-256 can still be taken to be safe for more than a fairly short time. Hmm, I disagree with this. Firstly, I don't think SHA-1 *is* holding on... while we don't have an example collision yet, there is no real doubt that one can be found in about 2^64 operations, which is less than the required 2^80. And SHA-2 does have a significantly different design in one area; the data expansion part is much stronger than SHA-1's, and almost certainly defeats the Wang-style attacks. Our paper on eprint gives some justification for why SHA-2 would appear to be resistant to these kinds of attacks. Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: hashes on restricted domains: random functions or permutations?
At 19:13 -0500 2006/10/17, Travis H. wrote: So I was reading about the OTP system (based on S/Key) described in RFC 2289. It basically hashes a secret several times (with salt to individualize it) and stores the value that the correct password will hash to. Now my question is, if we restrict ourselves to, say, 160-bit inputs, is SHA-1 a permutation, or do collisions exist? If there are collisions, then iterating the hash could lead to fewer possible values each time, potentially converging on a set of inputs that form a permutation and are closed under composition. It would be unexpected and certainly very surprising if SHA-1 formed a permutation of 160-bit inputs. Is that correct? What are the expected sizes of such sets? Is it worth worrying about? Yes, it's correct. No, it's not worth worrying about. See the Handbook of Applied Cryptography for more details, but the executive summary is: If you start with a particular input and repeatedly hash it (and on the assumption that SHA-1 is an approximation of a decent PRF), you expect to go through about 2^80 unique values before eventually settling into a cycle of length about 2^80. There are probably a (smallish) number of distinct such cycles. But since you'd have to wait a very long time before this mattered, it isn't a practical worry. Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: handling weak keys using random selection and CSPRNGs
At 17:05 -0400 2006/10/12, Steven M. Bellovin wrote: This is a very interesting suggestion, but I suspect people need to be cautious about false positives. MP3 and JPG files will, I think, have similar entropy statistics to encrypted files; so will many compressed files. Actually, no. I have a general purpose stats program that I often use for cryptanalysis as part of my tookit. I pointed it at my photos folder, and every single jpeg file had results like this: samples: 88246 unique: 256 sum: 11413854 sum squares: 1943201034 maximum: 255 minimum: 0 range:255 mean: 129.34132 variance: 5291.1565 std dev: 72.740336 median: 130 exp freq: 344.71094 max freq: 623 mode count: 1 mode: 0 min freq: 109 unmode count: 1 unmode: 192 chi^2:4375.0414 chi^2 df: 255 pr(chi^2):1.0 (*** certainly non-uniform distribution ***) bad buckets: 96 KS+: 1.0002392 pr(KS+): 0.86510 KS-: 6.6097712 pr(KS-): 1.0 (*** certainly non-uniform distribution ***) KS(both): 3.8050052 pr(KS_BOTH): 1.0 The simplest test is just the chi-squared test on the frequency of bytes, and it's way out of range on even fairly small jpegs. The Kolmogorov-Smirnoff test almost always bingos too. And even if the chi-squared passes, the binomial test on individual byte-value frequencies will flag the data as non-random; note the bad buckets count above; the detailed output is suppressed when the chi-squared test fails, since there will generally be too much of it. The only things that it usually passes as good are for-purpose random number generators' or ciphers' outputs. Everything else (including a terabyte of RC4 output, executables, zip archives, jpegs, mpegs, mp3s, ...) that I've pointed it at, fails one or more of the tests. True random-looking-ness is hard to find... :-) Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: A note on vendor reaction speed to the e=3 problem
At 14:33 -0400 2006/09/28, Leichter, Jerry wrote: | VMS has for years had a simple CHECKSUM command, which had a variant, CHECKSUM/IMAGE, applicable only to executable image files. It knew enough about the syntax of executables to skip over irrelevant metadata like link date and time. (The checksums computed weren't cryptographic - at least the last time I used it, many years ago. The command was created to use in patches to provide a quick verification that the file being patched was the right one.) I've always found it surprising that no one seems to have developed similar tools for Unix - with the Gnu libraries for portable access to object/ executable files, it could be done relatively easily. The sum command has existed in Unixes since before VMS existed. Checksum has too many characters in the name ;-). Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Exponent 3 damage spreads...
So, there is at least one top-level CA installed in some common browsers (I checked Firefox) that uses exponent-3. It is Starfield Technologies Inc. Starfield Class 2 CA. There may well be others... I only looked far enough to determine that that was a problem. So the next question becomes, what browsers used OpenSSL and/or their own broken code, and need to be patched? I have no idea. Thanks to Alex Gantman for asking the question... Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Why the exponent 3 error happened:
At 19:02 +1000 2006/09/14, James A. Donald wrote: Suppose the padding was simply 010101010101010 ... 1010101010101 hash with all leading zeros in the hash omitted, and four zero bits showing where the actual hash begins. Then the error would never have been possible. I beg to differ. A programmer who didn't understand the significance of crypto primitives would (as many did) just search for the end of the padding to locate the beginning of the hash, and check that the next set of bytes were identical to the hash, then return true. So 01010101 ... 1010101010101 hash crappetycrap would still be considered valid. There's a lot of code out there that ignored the fact that after the FFs was specific ASN.1 stuff, and just treated it as a defined part of the padding. Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Exponent 3 damage spreads...
At 23:40 +1200 2006/09/14, Peter Gutmann wrote: But wait, there's more! From what I understand of the attack, all you need for it to work is for the sig.value to be a perfect cube. To do this, all you need to do is vary a few of the bytes of the hash value, which you can do via a simple brute-force search. So even with a perfect implementation that does a memcmp() of a fixed binary string for all the data present but the hash, the attack still works. I thought this for a while, but no, it isn't true. Take a number k, which is of the order of 2^1008 (which is what a properly padded 1024-bit RSA signature will look like numerically). So the cube root of K is a real number of the order of 2^336... call this k'. Now on average it will be within +/- 0.25 of the nearest integer, so for sake of argument let i = k' + 0.25 be an integer. i^3 - k = (k' + 0.25)^3 - k = k + 0.25*k'^2 +0.0625*k' + 1/64 - k which is of order 0.25*k^2/3, ie, 2^670. Unless you are using very large hashes indeed, the chance of a properly padded RSA signature being a perfect cube is vanishingly small. In either of these cases, RSA e=3 is dead. Obesa cantavit. I don't yet agree with this conclusion. There'll always be broken standards out there that require e=3 (I know of at least one that uses e=2, and another that uses raw, unpadded RSA, and another that... well you get the idea), but the only quick, sure fix is to kill e=3, not to try and anticipate every potential way of trying to use it, because you'll never be secure that way. I just have to mention that e=2 is Rabin signatures, and they have different and very stringent requirements for signatures. Maybe the same problem exists, maybe it doesn't, I don't know. Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Chasing the Rabbit - a cryptanalytic contest
At 15:26 +0200 2006/08/23, Erik Zenner wrote: Hi all! At the rump session of Crypto 2006, we started the chasing the Rabbit contest. Dan Bernstein was so kind as to present the slides on our behalf. The details of the contest are given below; they can also be downloaded from http://www.cryptico.com/Files/Filer/rabbit_contest.pdf. Dan did *not* make the presentation. He was on the program but didn't speak. Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: U. Washington Crypto Course Available Online For Free
At 16:29 -0600 2006/06/08, John R. Black wrote: It is taught by good people, but I find it a bit strange they are all Microsoft employees. This is perhaps because U. Wash doesn't have any cryptographers. I hardly think that you can discount the skills of Josh Beneloh and Brian LaMacchia. Who is discounting? I said they are good people but that they work for Microsoft and not for the University of Washington. Yes, my apologies, I misparsed your statement. Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: U. Washington Crypto Course Available Online For Free
At 20:34 -0600 2006/06/06, John R. Black wrote: On Tue, Jun 06, 2006 at 01:57:25AM -0700, Udhay Shankar N wrote: http://it.slashdot.org/article.pl?sid=06/06/04/1311243 It is taught by good people, but I find it a bit strange they are all Microsoft employees. This is perhaps because U. Wash doesn't have any cryptographers. I hardly think that you can discount the skills of Josh Beneloh and Brian LaMacchia. That changes in the fall: they hired an excellent young cryptographer named Yoshi Kohno. Damn, I was trying to hire Yoshi... Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: is breaking RSA at least as hard as factoring or vice-versa?
At 1:41 -0600 2006/04/02, Travis H. wrote: So I'm reading up on unconditionally secure authentication in Simmon's Contemporary Cryptology, and he points out that with RSA, given d, you could calculate e (remember, this is authentication not encryption) if you could factor n, which relates the two. However, the implication is in the less useful direction; namely, that factoring n is at least as hard as breaking RSA. As of the books publication in 1992, it was not known whether the decryption of almost all ciphers for arbitrary exponents e is as hard as factoring. This is news to me! What's the current state of knowledge? It's conceivable that there might be a way to decrypt RSA messages without knowing d. If you don't know d, you still can't factor n. Whereas if you can factor n, you can find d, and decrypt messages. So the problems are not equivalent, and the RSA problem might be easier than the integer factorization problem. (At least, the above is my understanding.) Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Entropy Definition (was Re: passphrases with more than 160 bits of entropy)
At 22:09 -0500 2006/03/22, John Denker wrote: Aram Perez wrote: * Can you add or increase entropy? Shuffling a deck of cards increases the entropy of the deck. As a minor nit, shuffling *in an unpredictable manner* adds entropy, because there is extra randomness being brought into the process. If I was one of those people who can do a perfect riffle shuffle, reordering the cards in this entirely predictable manner does not increase or decrease the existing entropy. So in one sense, the answer is a simple no... nothing you can do to a passphrase can increase its (that is, the passphrase's) entropy. You can add randomness from another source, and increase the total entropy, but I don't think that is relevant to the original question. Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Symmetric ciphers as hash functions
At 01:33 2005-11-01 -0600, Travis H. wrote: The latest hashes, such as SHA-1, gave up on Feistel. Not so... the SHA family are all unbalanced Feistel structures. Basically, for SHA-1 a complex function of 4 words and key material (in this case expanded data to be hashed) is combined with the fifth word. The fact that the four words don't change is the giveaway that it's a feistel structure. The later SHAs have a more complicated structure, blurring the boundary a bit, but I'd still call them unbalanced Feistel. Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Venona not all decrypted?
At 16:20 2005-10-03 -0400, R.A. Hettinga wrote: I just heard that the Venona intercepts haven't all been decrypted, and that the reason for that was there wasn't enough budget to do so. Is that not enough budget to apply the one-time pads they already have, or is that the once-and-futile exercise of decrypting ciphertext with no one-time pad to go with it? Here's my understanding of how Venona worked, and why budget would be a problem. I could be completely off base, though. The OTPs were only very occasionally misused, by being used more than once. So the breaks occurred when two separate messages, or possibly fragments of messages, were combined in such a way as to cancel out the OTP, then the resulting running-key cipher was solved to yield the two messages. I don't think that the NSA had access to the pads themselves, except after having recovered the messages (and hence the pad for those messages). So there really isn't likelihood that that pad would be reused even more times. To detect that a pad has been reused, you basically have to line up two ciphertexts at the right places, combine them appropriately, and run a statistical test on the result to see if it shows significant bias. This is an O(n^2.m) problem, where n is the number of units to be tested (maybe whole messages, maybe pages of OTP, maybe at the character level? Who knows?) and m represents enough text to reliably detect a collision. There was a very large amount of intercepted data, and it's presumably all stored on tapes somewhere, so that n^2 factor probably involves actually mounting tapes and stuff. But in a way, you're right; it should, with today's technology, be possible to just read all the tapes once onto a big RAID, and set the cluster to work for a year or two. Greg. Greg RoseINTERNET: [EMAIL PROTECTED] Qualcomm Incorporated VOICE: +1-858-651-5733 FAX: +1-858-651-5766 5775 Morehouse Drivehttp://people.qualcomm.com/ggr/ San Diego, CA 92121 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: ECC patents?
At 09:54 2005-09-15 -0700, James A. Donald wrote: I doubt that the NSA paid any money whatsoever for this license, making it profoundly unimpressive as evidence that *any* curves have a plausible valid patent. If the NSA paid real money, the patent holders would be sticking it in our face as a price setting precedent. They (NSA) did pay, and they (Certicom) did stick it in our faces. See, eg., http://www.eweek.com/article2/0,1895,1498136,00.asp . Did you miss this at the time? Greg. Greg RoseINTERNET: [EMAIL PROTECTED] Qualcomm Incorporated VOICE: +1-858-651-5733 FAX: +1-858-651-5766 5775 Morehouse Drivehttp://people.qualcomm.com/ggr/ San Diego, CA 92121 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: expanding a password into many keys
At 10:34 2005-06-14 -0700, Eric Rescorla wrote: Hash-based constructions are the standard here, but I'm generally leary of using a pure hash. Probably the best basic function is to use HMAC(P,L_i) or perhaps HMAC(H(P),L_i), since HMAC wasn't designed to be used with non-random key values. You'd need someone with a better understanding of hash functions than I have to tell you which one of these is better. You know, the proof that HMAC is a good MAC requires that the *compression function* of the underlying hash is good. And for almost all applications like this one, both the input password and the sequence number, tag name, or whatever the second input is, all fit into a single compression function block. So you already get exactly what you need from the hash function, without needing the extra layer or two. They can't hurt much(*), but they don't actually help either. (*) actually each layer reduces the space of output keys slightly; not enough to matter in practice, but it is actually infinitesimally worse than just doing the hash. Greg. Greg RoseINTERNET: [EMAIL PROTECTED] Qualcomm Incorporated VOICE: +1-858-651-5733 FAX: +1-858-651-5766 5775 Morehouse Drivehttp://people.qualcomm.com/ggr/ San Diego, CA 92121 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [Clips] Storm Brews Over Encryption 'Safe Harbor' in Data Breach Bills
At 00:48 2005-06-03 +0100, Ian G wrote: Just to make it more interesting, the AG of New York, Elliot Spitzer has introduced a package of legislation intended to rein in identity theft including: Facilitating prosecutions against computer hackers by creating specific criminal penalties for the use of encryption to conceal a crime, to conceal the identity of another person who commits a crime, or to disrupt the normal operation of a computer; Ah, imagine the beautiful circularity of the Justice Department using encryption to protect their criminal identity database from disclosure... or not. Greg. Greg RoseINTERNET: [EMAIL PROTECTED] Qualcomm Incorporated VOICE: +1-858-651-5733 FAX: +1-858-651-5766 5775 Morehouse Drivehttp://people.qualcomm.com/ggr/ San Diego, CA 92121 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: SHA-1 cracked
At 22:33 2005-02-16 +, Ian G wrote: Steven M. Bellovin wrote: According to Bruce Schneier's blog (http://www.schneier.com/blog/archives/2005/02/sha1_broken.html), a team has found collisions in full SHA-1. It's probably not a practical threat today, since it takes 2^69 operations to do it and we haven't heard claims that NSA et al. have built massively parallel hash function collision finders, but it's an impressive achievement nevertheless -- especially since it comes just a week after NIST stated that there were no successful attacks on SHA-1. Stefan Brands just posted on my blog (and I saw reference to this in other blogs, posted anon) saying that it seems that Schneier forgot to mention that the paper has a footnote which says that the attack on full SHA-1 only works if some padding (which SHA-1 requires) is not done. http://www.financialcryptography.com/mt/archives/000355.html No, that's not what it says. It says that Note that padding rules were not applied to the message. This is exactly the same as the previous breaks; it just means that the collision appears in the chaining output... if you just append anything at all to the end of the texts, and pad it correctly, you will have valid SHA-1 hashes. Nothing different here than from the MD4/MD5/SHA-0 breaks. Since I'm typing anyway, I'll also reply to Joseph Ashwood's earlier mail, in which he said: [...] SHA-1 showing big cracks, the entire SHA series is in doubt, and needs to be heavily reconsidered, [...] If you look at Phil Hawkes' paper http://eprint.iacr.org/2004/207.pdf, you will see that the SHA-2s are very different algorithms, and my own opinion is that the data-expansion part of the algorithm is *seriously* beefed up. My guess is that the NSA were already worried about this kind of attack (whether they'd found it or not). We don't have a good analysis of the data-expansion part, but I'm pretty sure that it'll defeat the Wang attacks. Greg. Greg RoseINTERNET: [EMAIL PROTECTED] Qualcomm Incorporated VOICE: +1-858-651-5733 FAX: +1-858-651-5766 5775 Morehouse Drivehttp://people.qualcomm.com/ggr/ San Diego, CA 92121 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: SSL/TLS passive sniffing
At 22:51 2004-12-22 +0100, Florian Weimer wrote: * John Denker: Florian Weimer wrote: Would you recommend to switch to /dev/urandom (which doesn't block if the entropy estimate for the in-kernel pool reaches 0), and stick to generating new DH parameters for each connection, No, I wouldn't. Not even for the public parameters? Am I understanding correctly? Does SSL/TLS really generate a new P and G for each connection? If so, can someone explain the rationale behind this? It seems insane to me. And not doing so would certainly ease the problem on the entropy pool, not to mention CPU load for primality testing. I must be misunderstanding. Surely. Please? Greg. Greg RoseINTERNET: [EMAIL PROTECTED] Qualcomm Incorporated VOICE: +1-858-651-5733 FAX: +1-858-651-5766 5775 Morehouse Drivehttp://people.qualcomm.com/ggr/ San Diego, CA 92121 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: Bad day at the hash function factory
I wrote: Phil Hawkes' paper on the SHA-2 round function has just been posted as Eprint number 207. It contains rather a lot of detail, unlike some of the other papers on the subject of hash function collisions. At 14:17 2004-08-23 -0400, Trei, Peter wrote: Could you possibly post a direct link? http://eprint.iacr.org/2004/207.pdf Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Bad day at the hash function factory
Phil Hawkes' paper on the SHA-2 round function has just been posted as Eprint number 207. It contains rather a lot of detail, unlike some of the other papers on the subject of hash function collisions. Greg. Greg RoseINTERNET: [EMAIL PROTECTED] Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199 Level 3, 230 Victoria Road, http://people.qualcomm.com/ggr/ Gladesville NSW 2111/232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: MD5 collisions?
In the light of day and less inebriated, I'd like to clarify some of what I wrote last night, and maybe expand a bit. My original account wasn't what I'd like to think of as a record for posterity. Greg. At 13:11 2004-08-18 +1000, Greg Rose wrote: Xiaoyun Wang was almost unintelligible. This was not meant as a criticism. It just meant you had to concentrate really hard. Her English is much better than my Chinese. But the attack works with any initial values, which means that they can take any prefix, and produce collisions between two different suffixes. The can produce the first collision for a given initial value in less than an hour, and then can crank them out at about one every 5 minutes. As mentioned previously, the idea is to produce a good partial collision with the first blocks input to the hash, and then from two similar starting points, find subsequent blocks that correct them back to the same output. So, for a given input chaining vector, it takes about an hour to get the partial collisions in the first input block. From there, they can compute subsequent second blocks to produce the collisions in a few minutes. Note that they did two entirely new collisions for MD5 overnight, communicating back to China, when they found out about the endianness problems. No-one can now argue that they can't find collisions at will. It seems to be a straightforward differential cryptanalysis attack, so one wonders why no-one else came up with it. With further hindsight, and Phil Hawkes' help, I understand now. The technique needs to alternate between single bit (xor) differences and subtractive differences, with careful conditioning of the bits affected to make sure the right carries do, or don't, propagate. This is explained in Phil's upcoming paper about SHA-2 cancellations, which was presented later in the rump session. That should be on e-print in the next couple of days. The Chinese team is also writing a much more detailed paper, but it will take longer. There has been criticism about the Wang et. al paper that it doesn't explain how they get the collisions. That isn't right. Note that from the incorrect paper to the corrected one, the delta values didn't change. Basically, if you throw random numbers in as inputs, in pairs with the specified deltas, you should eventually be able to create your own MD5 collisions for fun or profit. How they got this insight, we'll have to wait for... but the method is already there. Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: MD5 collisions?
At 00:49 2004-08-19 +1000, Greg Rose wrote: There has been criticism about the Wang et. al paper that it doesn't explain how they get the collisions. That isn't right. Note that from the incorrect paper to the corrected one, the delta values didn't change. Basically, if you throw random numbers in as inputs, in pairs with the specified deltas, you should eventually be able to create your own MD5 collisions for fun or profit. This, too, is overly simplistic an explanation. Doing it like this would effectively multiply the work for the near-collision in the first block and the correction in the second block, which is not what you want. To be efficient, you need to divide-and-conquer; make random pairs of first blocks until you find a pair that have the right very small difference in their chaining outputs. Then, from those first blocks, try to find second blocks that work. This adds the amounts of work, rather than multiplying them. Apologies for any confusion. Greg. Greg RoseINTERNET: [EMAIL PROTECTED] Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199 Level 3, 230 Victoria Road, http://people.qualcomm.com/ggr/ Gladesville NSW 2111/232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: MD5 collisions?
At 12:04 2004-08-18 -0400, Whyte, William wrote: There has been criticism about the Wang et. al paper that it doesn't explain how they get the collisions. That isn't right. Note that from the incorrect paper to the corrected one, the delta values didn't change. Basically, if you throw random numbers in as inputs, in pairs with the specified deltas, you should eventually be able to create your own MD5 collisions for fun or profit. So this is big. This doesn't just break collision resistance, it breaks second preimage resistance. Is that right? If I've understood it correctly, the answer is sort of. For a given input, it seems that there is some non-trivial chance that the input+delta would produce the same hash, that is, a 2nd preimage. But the probability, for any single arbitrary message, might be quite low (especially since you'd have to multiply the probabilities of success for the first and second blocks; see my other message just before this one). But it seems to me that that probability would still be much better than the 2^-n that it should be for an n-bit hash. For example, the MD5 collision in 2^40 work is really two separate near-collisions, each taking a bit less than 2^40 work. If you apply the deltas to a random message M, both blocks at the same time, it seems to me that the probability of success is about 2^-80; it either works or it doesn't. But that 2^-80 is a much better chance than you would have had for two random messages (which is really message M and a random delta). But I could also be mistaken on this. Greg. Greg RoseINTERNET: [EMAIL PROTECTED] Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199 Level 3, 230 Victoria Road, http://people.qualcomm.com/ggr/ Gladesville NSW 2111/232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: MD5 collisions?
At 14:12 2004-08-17 -0300, Mads Rasmussen wrote: Eric Rescorla wrote: Check out this ePrint paper, which claims to have collisions in MD5, MD4, HAVAL, and full RIPEMD. http://eprint.iacr.org/2004/199.pdf The authors claim that the MD5 attack took an hour for the first collision and 15 seconds to 5 minutes for subsequent attacks with the same first 512 bits. So what's the status?, the MD5 collisions has been confirmed by Eric Rescorla (taken the type into consideration), the MD4 by David Shaw, what about Haval and RipeMD?. I did a test on the RipeMD results and couldn't get the results written. Anybody else having the same problems? Any news on Antoine Joux and his attack on SHA-0? how did he create the collision previously announced on sci.crypt? Eli Biham -- has collisions on 34 (out of 80) rounds of SHA-1, but can extend that to probably 46. Still nowhere near a break. Antoine Joux -- his team announced the collision on SHA-0 earlier this week. There is concentration on the so-called IF function in the first 20 rounds... f(a,b,c) = (a b) ^ (~a c). That is, the bits of a choose whether to pass the bits from b, or c, to the result. The technique (and Eli's) depends on getting a near collision in the first block hashed, then using more near collisions to move the different bits around, finally using another near collision to converge after the fourth block hashed. This took 20 days on 160 Itanium processors. It was about 2^50 hash evaluations. Xiaoyun Wang was almost unintelligible. But the attack works with any initial values, which means that they can take any prefix, and produce collisions between two different suffixes. The can produce the first collision for a given initial value in less than an hour, and then can crank them out at about one every 5 minutes. It seems to be a straightforward differential cryptanalysis attack, so one wonders why no-one else came up with it. The attack on Haval takes about 64 tries. On MD4, about 4 tries. RIPE-MD, about 2 hours (but can improve it). SHA-0 about 2^40 (1000 times better than Joux). Xuejia Lai clarified that the paper on E-print has been updated with correct initial values. They were initially byte-reversed, which they blamed on Bruce Schneier. Greg. Regards, Mads Rasmussen Open Communications Security - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] Greg RoseINTERNET: [EMAIL PROTECTED] Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199 Level 3, 230 Victoria Road, http://people.qualcomm.com/ggr/ Gladesville NSW 2111/232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: SHA-1 rumors
At 15:50 2004-08-16 -0400, Matt Curtin wrote: Eric Rescorla [EMAIL PROTECTED] writes: P.S. AFAIK, although Dobbertin was able to find preimages for reduced MD4, there still isn't a complete break in MD4. Correct? Dobbertin's work on was reduced MD5. I haven't heard anything about progress on that front for several years. No, it was on the compression function, but not in any sense reduced. But you had to start with particular values of the chaining variables, and in practice no-one knows how to do that, so MD5 (as a whole) isn't broken by this, at least until tomorrow evening. The rumour here is that MD5, HAVAL, and RIPE-MD are all goners. We know SHA-0 is toast too. There might also be results against SHA-1. Hash functions are hard. And the reason you haven't heard any progress from Dobbertin is because his employers told him to either stop working on it, or stop talking about it, depending which version of the story you've heard. Since he works for the German NSA-equivalent, I guess he would take this seriously. Greg. Greg RoseINTERNET: [EMAIL PROTECTED] Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199 Level 3, 230 Victoria Road, http://people.qualcomm.com/ggr/ Gladesville NSW 2111/232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: EZ Pass and the fast lane ....
At 21:54 2004-07-09 +0100, Ian Grigg wrote: John Gilmore wrote: It would be relatively easy to catch someone doing this - just cross-correlate with other information (address of home and work) and then photograph the car at the on-ramp. Am I missing something? It seems to me that EZ Pass spoofing should become as popular as cellphone cloning, until they change the protocol. You pick up a tracking number by listening to other peoples' transmissions, then impersonate them once so that their account gets charged for your toll (or so that it looks like their car is traveling down a monitored stretch of road). It should be easy to automate picking up dozens or hundreds of tracking numbers while just driving around; and this can foil both track-the-whole-populace surveillance, AND toll collection. Miscreants would appear to be other cars; tracking them would not be feasible. Well, I am presuming that ... the EZ Pass does have an account number, right? And then, the car does have a licence place? So, just correlate the account numbers with the licence plates as they go through the gates. If they could do that reliably, they wouldn't need the toll thingy, nu? I have been told by someone in the photo-enforcement industry that their reliability is only around 75%, and they're very expensive, and ... anyway, not a viable solution to the problem given the current economics. But to a weekly commuter over one of the bridges in New York, for example, it's $1000 per year. What incentive does a miscreant have to reprogram hundreds or thousands of other cars??? Until recently, when viruses and worms started to be used to assist spamming, what incentive did a miscreant have to invade hundreds or thousands of computers? Greg. Greg RoseINTERNET: [EMAIL PROTECTED] Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199 Level 3, 230 Victoria Road, http://people.qualcomm.com/ggr/ Gladesville NSW 2111/232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: BBC story on Iran codes
At 15:41 2004-06-19 -0400, Perry E. Metzger wrote: http://news.bbc.co.uk/1/hi/technology/3804895.stm No real new info, but some good background. Several familiar names, such as Ross Anderson, are interviewed. Gee, a pity they can't calculate 2^128 correctly. Greg. Greg RoseINTERNET: [EMAIL PROTECTED] Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199 Level 3, 230 Victoria Road, http://people.qualcomm.com/ggr/ Gladesville NSW 2111/232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: I don't know PAIN...
At 03:03 AM 12/21/2003, Ian Grigg wrote: What is the source of the acronym PAIN? I've seen, for many years, the acronym CAIN, where the C is Confidentiality. I think that was in the Orange Book. There's also, historically, an R for Robustness or Reliability in many military contexts, instead of the N for Nonrepudiation. That is, protection from denial-of-service attacks. Lastly, the A is often Authorization rather than Authentication, since integrity implies identification of the source. The first time I recall seeing PAIN was just a few weeks ago, in postings by Lynn. I don't know if that helps, because I certainly got mightily confused while writing it. Greg. Lynn said: ... A security taxonomy, PAIN: * privacy (aka thinks like encryption) * authentication (origin) * integrity (contents) * non-repudiation I.e., its provenance? Google shows only a few hits, indicating it is not widespread. iang - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] Greg Rose INTERNET: [EMAIL PROTECTED] Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199 Level 3, 230 Victoria Road,http://people.qualcomm.com/ggr/ Gladesville NSW 2111232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Open Source Embedded SSL - Export Questions
At 12:27 PM 11/27/2003, Thor Lancelot Simon wrote: RC4 is extremely weak for some applications. A block cipher is greatly preferable. I'm afraid that I can't agree with this howling logical error. RC4 is showing its age, but there are other stream ciphers that are acceptable, and there are block ciphers (such as FEAL, same vintage as RC4) that aren't even vaguely secure. Greg. Greg Rose INTERNET: [EMAIL PROTECTED] Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199 Level 3, 230 Victoria Road,http://people.qualcomm.com/ggr/ Gladesville NSW 2111232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Literature about Merkle hash tries?
At 01:14 AM 10/1/2003 +0300, Benja Fallenstein wrote: So, anyway, anybody know references? I've not come across any yet. I know that the technique dates back (at least) to IBM in the 60s. I used to know the name of the inventor but can't bring it to mind at the moment. The Berkeley UNIX library dbm uses essentially this philosophy, but the tree is not binary; rather each node stores up to one disk block's worth of pointers. Nodes split when they get too full. When the point is to handle a lot of data, this makes much more sense. Hope that helps, Greg. Greg Rose INTERNET: [EMAIL PROTECTED] Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199 Level 3, 230 Victoria Road,http://people.qualcomm.com/ggr/ Gladesville NSW 2111232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: A quick question...
At 11:53 PM 9/27/2003 +0100, Paul Walker wrote: Talking to a friend the other day, he was telling me about a potential loophole with SHA-1 hashes protected by an RSA signature. Basically, he seemed to think that with an SHA hash of a suitable length (say, 2^20), the hash could be cubed and still not 'fail', since it was below the key modulus. If you change the hash length, this problem doesn't occur. I'm unconvinced for a number of reasons - this sounds very strange to me. Not least because, even if cubing the hash does work (why cubing?), since it's infeasible to create a binary which produces a given hash it still doesn't help. I think your friend has a very limited understanding of what's going on; he's right in some small sense, but wrong in practice. Cubing is coming from the assumption that the public exponent is 3, which is possible for RSA but rare in practice; 17 or 2^16+1 are much more common values. It also relies on using some rawly implemented RSA, so that all that is in the RSA payload is the hash, and nothing else. This violates all the standards that specify that the payload should be padded with stuff that, among other things, guarantees that even with an exponent of three, the answer will have exceeded the modulus and been subject to modular reduction. So he's talking through his hat. Could someone help shed some light on this? Either pointing me at a paper documenting the hole, or confirming that it's gibberish (at which point I'll go back to work and ask him for more details :). So, here's the attack. Suppose you have a 160-bit SHA-1 hash of some document, and it just happens to be a perfect cube (integer-speaking). Then the cube root of that hash is a valid signature independent of the modulus, so long as the public exponent is 3. Adding (and checking) correct padding (eg. OAEP or PSS, see the PKCS standards) makes it extremely unlikely that there will be a cube root for the attack to work on. Others may want to correct me or elaborate further, but I think that's correct. regards, Greg. Greg Rose INTERNET: [EMAIL PROTECTED] Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199 Level 3, 230 Victoria Road,http://people.qualcomm.com/ggr/ Gladesville NSW 2111232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Code breakers crack GSM cellphone encryption
At 05:18 PM 9/7/2003 -0700, David Honig wrote: A copy of the research was sent to GSM authorities in order to correct the problem, and the method is being patented so that in future it can be used by the law enforcement agencies. Laughing my ass off. Since when do governments care about patents? How would this help/harm them from exploiting it? Not that high-end LEOs haven't already had this capacity ---Biham et al are only the first *open* researchers to reveal this. Actually, patenting the method isn't nearly as silly as it sounds. Produced in quantity, a device to break GSM using this attack is not going to cost much more than a cellphone (without subsidies). Patenting the attack prevents the production of the radio shack (tm) gsm scanner, so that it at least requires serious attackers, not idle retirees or jealous teenagers. Greg. Greg Rose INTERNET: [EMAIL PROTECTED] Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199 Level 3, 230 Victoria Road,http://people.qualcomm.com/ggr/ Gladesville NSW 2111232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Code breakers crack GSM cellphone encryption
At 11:43 AM 9/8/2003 -0400, Anton Stiglic wrote: I think this is different however. The recent attack focused on the A5/3 encryption algorithm, while the work of Lucky, Briceno, Goldberg, Wagner, Biryukov, Shamir (and others?) was on A5/1 and A5/2 (and other crypto algorithms of GSM, such as COMP128, ...). No, that's not right. The attack *avoids* A5/3, by making the terminal end of the call fall back to A5/2, solving for the key in real time, then continuing to use the same key with A5/3. A5/3 (based on Kasumi, and essentially the same as the WCDMA algorithm UEA1) is not in any way compromised by this attack. Greg. Greg Rose INTERNET: [EMAIL PROTECTED] Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199 Level 3, 230 Victoria Road,http://people.qualcomm.com/ggr/ Gladesville NSW 2111232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Crypto 2003
This year's Crypto conference is in Santa Barbara August 17-21. The early registration deadline is July 14th. Full program information is available at http://www.iacr.org/conferences/crypto2003/2003Program.html . It'll be great, both technically and socially! regards, Greg. (General Chair) Greg Rose INTERNET: [EMAIL PROTECTED] Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199 Level 3, 230 Victoria Road,http://people.qualcomm.com/ggr/ Gladesville NSW 2111232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
