RE: Why the exponent 3 error happened:
From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED]
Sent: Sonntag, 17. September 2006 06:01
For another example of just how badly this kind of thing can
be done, look at this code excerpt from Firefox version
1.5.0.7, which is the fixed version. There are two PKCS-1
parsing functions, one which returns the hash and its prefix,
the other of which is given the hash and asked whether it
matches the RSA-signed value. This is from the latter one:
/*
* check the padding that was used
*/
if (buffer[0] != 0 || buffer[1] != 1)
goto loser;
for (i = 2; i modulus_len - hash_len - 1; i++) {
if (buffer[i] == 0)
break;
if (buffer[i] != 0xff)
goto loser;
}
/*
* make sure we get the same results
*/
if (PORT_Memcmp(buffer + modulus_len - hash_len, hash,
hash_len) != 0)
goto loser;
PORT_Free(buffer);
return SECSuccess;
Here, buffer holds the result of the RSA exponentiation, of
size modulus_len, and we are passed hash of size hash_len to compare.
I don't think this code is used, fortunately. It will accept
anything of the form 0, 1, 0, garbage, hash. Just goes to
show how easy it is to get this kind of parsing wrong.
Unfortunately, this code _is_ used! It took me quite a while to understand
under what circumstances, but here is the result. The problem is fixed as of
version 1.5.0.8 (out now). Interestingly, the mozilla people fixed it by
themselves in the 2.0 version (and any public beta I could find), but for the
1.5 version it took my bug report...
So here is how the code is used and some hints (I am reluctant to give out the
details right now, given that there are still many vulnerable systems out
there. However, I am sure you can easily work out the details):
Whenever a SSL or TLS server send a ServerKeyExchange message, the key
contained in there is signed with a fresh nonce. This signature is checked
using RSA_CheckSign().
Faking a signature for a key with a small exponent like 3 is easy. This can be
used to break the SSL/TLS authentication.
Better upgrade asap...
Regards,
Ulrich
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: TPM disk crypto
From: Ivan Krstić [mailto:[EMAIL PROTECTED] Kuehn, Ulrich wrote: Who is we? In the case of my own system I payed for (so speaking for myself) I would like to have such a mechanism to have the system prove to me before login that it is not tampered with. The TCG approach does not provide this. What does prove mean here? Does having a hash of the system state for visual inspection before boot do it? Well, reliably obtaining the end of a hash chain would do, but it would be very inconvenient to compare that manually (visually) to a hash written on a piece of paper in my wallet. That is not user-friendly. However, if the system provided a possibility to reliably stop the boot process when something is changed, that would do. With reliably stopping the boot process I mean the following: Given that stage i of the process is running, it takes the hash of the next stage, compares that to an expected value. If they match, the current stage extends the TPM register (when also running the TCG stuff), and executes the next stage. If the computed and expected hashes do not match, the machine goes into a predetermined halt state. Predetermined means that the system administrator (on behalf of the system owner) can determine the expected hash value. I hope this makes it clear what I meant in the text quoted above. To implement this the TCG-preBIOS would need to implement this halt state, possibly along with some other additional features like where to store the expected hashes etc. Cheers, Ulrich - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: TPM disk crypto
From: James A. Donald [mailto:[EMAIL PROTECTED] Sent: Dienstag, 10. Oktober 2006 06:40 What we want is that a bank client can prove to the bank it is the real client, and not trojaned. What the evil guys at RIAA want is that their music player can prove it is their real music player, and not hacked by the end user. Having a system that will only boot up in a known state is going to lead to legions of unhappy customers who find their system does not come up at all. Who is we? In the case of my own system I payed for (so speaking for myself) I would like to have such a mechanism to have the system prove to me before login that it is not tampered with. The TCG approach does not provide this. Oh, and predetermined means that the machine admin can declare to which known state the system is going to boot. From a company point of view it might be interesting to make sure the employees have systems that come up to a predetermined state, or not at all, so when infected this turns up at next boot so that the admin can fix it. Here the TCG approach would also be helpful as the remote attestation against a central server (or a number of them) can help. And for the RIAA guys, they have no business on the machine I did pay for (!), as long as I do not infringe their copyright. Assumed innocent until proven guilty! On the other hand, there has been an infamous record company that miserably failed to ensure their components on consumers' computers are _not_ a security risk. Ulrich - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: TPM disk crypto
From: Erik Tews [mailto:[EMAIL PROTECTED] Sent: Donnerstag, 5. Oktober 2006 23:52 [...] Later, you can remotely query your system and get a report what has been bootet on your system. You can do this query using a java application and tpm4java. However, this is the big problem with the TPM according to the TCG spec. While you can remotely verify that the system came up according to what you installed there, you have no means to force it to either come up the way you want, or to be in a clear error state. That is the huge difference between the verifiable booting the TPM provides and secure booting, which would run only predetermined software. I assume that the TCG chose not to implement the latter due to fear of public bashing... Ulrich - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: Exponent 3 damage spreads...
From: Ralf-Philipp Weinmann
[...]
Relevant files to this problem that were patched turned out
to be security/nss/lib/cryptohi/secvfy.c and
nss/lib/util/secdig.c. Have a look at the function
DecryptSigBlock() in secdig.c, lines 92-95
/* make sure the parameters are not too bogus. */
if (di-digestAlgorithm.parameters.len 2) {
goto sigloser;
}
Quite amused, we also noted the following:
/* XXX Check that tag is an appropriate algorithm? */
---
/* Check that tag is an appropriate algorithm */
if (tag == SEC_OID_UNKNOWN) {
goto sigloser;
}
This means, that before the patch was applied, NSS indeed was
vulnerable to Kaliski's OID attack.
While the patch for Firefox obviously fixed the bugs in
security/nss/lib/cryptohi/whatever,
There is another pkcs#1-padding check in security/nss/lib/softtoken/rsawrapr.c,
see function
RSA_CheckSign() and RSA_CheckSignRecover(). Does anybody know what these
functions are used for?
I tried to find that out, but did not get very far...
(Hal Finney also noted these functions some days ago).
It seems to be another creative bug:
/*
* check the padding that was used
*/
if (buffer[0] != 0 || buffer[1] != 1)
goto loser;
for (i = 2; i modulus_len - hash_len - 1; i++) {
if (buffer[i] == 0)
break;
if (buffer[i] != 0xff)
goto loser;
}
/*
* make sure we get the same results
*/
if (PORT_Memcmp(buffer + modulus_len - hash_len, hash, hash_len) != 0)
goto loser;
So it would accept a padding ( 00 || 01 || 00 || garbage || hash ), which is
not exactly what pkcs#1 says :)
The same loop is used in RSA_CheckSignRecover(), but I did not succeed in
finding out what it is exactly used for and if that is a safe application of
the rather wrong code.
Cheers,
Ulrich
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: Exponent 3 damage spreads...
Peter, From: Peter Gutmann [mailto:[EMAIL PROTECTED] David Wagner [EMAIL PROTECTED] writes: (a) Any implementation that doesn't check whether there is extra junk left over after the hash digest isn't implementing the PKCS#1.5 standard correctly. That's a bug in the implementation. No, it's a bug in the spec: 9.4 Encryption-block parsing [...] Nothing in there about trailing garbage. Actually, this part is about _encryption_, we are talking here about signature padding. But the PKCS#1 spec talks about building up the complete padded signature input at the verifier, and then comparing it. However, there is a note saying that alternatively one could parse the padding without saying how this would be done. The reason to use such a thing is given as saving intermediate memory. Oh well! So in fact what a lot of implementors do, parsing the padding, is not specified in sufficient detail to get it right. I would consider this buggy implementation resulting from buggy specification. Regards, Ulrich - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: Exponent 3 damage spreads...
Peter, From: Peter Gutmann [mailto:[EMAIL PROTECTED] Kuehn, Ulrich [EMAIL PROTECTED] writes: But the PKCS#1 spec talks about building up the complete padded signature input at the verifier, and then comparing it. Uhh, did you actually read the rest of my post? *One variant of the PKCS #1 spec, that didn't exist at the time the the affected other standards were created*, talks about ..., not the PKCS #1 spec as a whole. I even quoted the original text of the spec in my message. It might have helped if you indicated that the citation was from the PKCS#1 standard version 1.5 (?). Interestingly, I find there (version 1.5) also 10.2.3 Data decoding The data D shall be BER-decoded to give an ASN.1 value of type DigestInfo, which shall be separated into a message digest MD and a message-digest algorithm identifier. The message-digest algorithm identifier shall determine the selected message-digest algorithm for the next step. It is an error if the message-digest algorithm identifier does not identify the MD2, MD4 or MD5 message-digest algorithm. Here, any trailing garbage would be included in data D. But does an ASN.1 value allow such a thing? I am asking this independently of our discussion here. Anyway, I think we agree on the point that the spec (even version 2.1) is in some point unprecise which should be considered a bug, as it can lead to implementation flaws. And yes, given what we know, e=3 is a good candidate for elimination :) Ulrich - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: [cryptography] Re: Why the exponent 3 error happened:
From: Ralf-Philipp Weinmann [mailto:[EMAIL PROTECTED] [...] Unfortunately we only found out that there has been prior art by Yutaka Oiwa et al. *AFTER* we successfully forged a certificate using this method (we being Andrei Pyshkin, Erik Tews and myself). The certificate we forged however adheres to the padding specifications unlike the one by Yutaka Oiwa that Simon Josefsson forwarded to the list a couple of days ago: -BEGIN CERTIFICATE- MIICgzCCAWugAwIBAgIBFzANBgkqhkiG9w0BAQUFADBoMQswCQYDVQQGEwJVUzEl MCMGA1UEChMcU3RhcmZpZWxkIFRlY2hub2xvZ2llcywgSW5jLjEyMDAGA1UECxMp U3RhcmZpZWxkIENsYXNzIDIgQ2VydGlmaWNhdGlvbiBBdXRob3JpdHkwHhcNMDYw ODE5MTY1MTMwWhcNMDYxMDE4MTY1MTMwWjARMQ8wDQYDVQQDEwZIYWNrZXIwgZ8w DQYJKoZIhvcNAQEBBQADgY0AMIGJAoGBAKSu6ChWttBsOpaBrYf4PzyCGNe6DuE7 rmq4CMskdz8uiAJ3wVd8jGsjdeY4YzoXSVp+9mEF6XqNgyDf8Ub3kNgPYxvJ28lg QVpd5RdGWXHo14LWBTD1mtFkCiAhVlATsVNI/tjv2tv7Jp8EsylbDHe7hslA0rns Rr2cS9bvpM03AgMBAAGjEzARMA8GA1UdEwEB/wQFMAMBAf8wDQYJKoZIhvcNAQEF BQADggEB ADLL/Up63HkFWD15INcW Xd1nZGI+gO/whm58ICyJ1Js7ON6N4NyBTwe8513CvdOlOdG/Ctmy2gxEE47HhEed ST8AUooI0ey599t84P20gGRuOYIjr7c= -END CERTIFICATE- Broken implementations can successfully verify it using the Starfield Class 2 Certification Authority: I tried to parse and verify this certificate using openssl's asn1parse command. However, I get an error: Error in encoding 7469:error:0D07207B:asn1 encoding routines:ASN1_get_object:header too long:asn1_lib.c:150: I am using openssl version 0.9.8c as of Sep 05, 2006 (Linux/Debian system). Any ideas what I am doing wrong? Cheers, Ulrich - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: Why the exponent 3 error happened:
I noticed the exact same code being present in the mozilla 1.7.13 source ... I
wonder what the correct consequence would be? Have us crypto people proof-read
all relevant source code? Better educate developers?
Interestingly the attacker's playground between the 0, 1, 0 and the hash gets
bigger with larger key sizes, so I wonder if attacks get easier for longer
keys...
Cheers,
Ulrich
From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED]
For another example of just how badly this kind of thing can
be done, look at this code excerpt from Firefox version
1.5.0.7, which is the fixed version. There are two PKCS-1
parsing functions, one which returns the hash and its prefix,
the other of which is given the hash and asked whether it
matches the RSA-signed value. This is from the latter one:
/*
* check the padding that was used
*/
if (buffer[0] != 0 || buffer[1] != 1)
goto loser;
for (i = 2; i modulus_len - hash_len - 1; i++) {
if (buffer[i] == 0)
break;
if (buffer[i] != 0xff)
goto loser;
}
/*
* make sure we get the same results
*/
if (PORT_Memcmp(buffer + modulus_len - hash_len, hash,
hash_len) != 0)
goto loser;
PORT_Free(buffer);
return SECSuccess;
Here, buffer holds the result of the RSA exponentiation, of
size modulus_len, and we are passed hash of size hash_len to compare.
I don't think this code is used, fortunately. It will accept
anything of the form 0, 1, 0, garbage, hash. Just goes to
show how easy it is to get this kind of parsing wrong.
(Note, this is from
mozilla/security/nss/lib/softoken/rsawrapr.c:RSA_CheckSign())
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: IGE mode is broken (Re: IGE mode in OpenSSL)
-Original Message- From: Ben Laurie [mailto:[EMAIL PROTECTED] Sent: Samstag, 9. September 2006 22:39 To: Adam Back Cc: Travis H.; Cryptography; Anton Stiglic Subject: Re: IGE mode is broken (Re: IGE mode in OpenSSL) [...] In any case, I am not actually interested IGE itself, rather in biIGE (i.e. IGE applied twice, once in each direction), and I don't care about authentication, I care about error propagation - specifically, I want errors to propagate throughout the plaintext. In fact, I suppose I do care about authentication, but in the negative sense - I want it to not be possible to authenticate the message. Do I understand correctly? You do want that nobody is able to authenticate a message, however, it shall not be intelligible if manipulated with? Or do you want that the authentication test fails if the message has been tampered with? I may have misunderstood the IGE paper, but I believe it includes proofs for error propagation in biIGE. Obviously if you can prove that errors always propagate (with high probability, of course) then you can have authentication cheaply - in comparison to the already high cost of biIGE, that is. I you want authentication, then authenticate. Use something with known security properties. So instead of running over the plaintext twice like with forward/backward IGE, try something like EAX, which is essentially counter mode with CBC-MAC for explicit authentication. Comes with proofs of security. But then, maybe I did not understand your problem (see above). Regards, Ulrich - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: the meaning of linearity, was Re: picking a hash function to be encrypted
-Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] The thing I've always wondered about stream ciphers is why we only talk about linear ones. A stream cipher is fundamentally constructed of two things: A stream of bits (alleged to be unpredictable) as long as the plaintext; and a combining function that takes one plaintext bit and one stream bit and produces a ciphertext bit. The combining function has to conserve information. If you only combine single bits, there are only two possible functions: XOR and the complement of XOR. But consider RC4: It actually generates a byte at a time. We just choose to use that byte as a vector of 8 bits. For plaintexts that are multiples of 8 bits long - just about everything these days - there are many possible combining functions. Most aren't even close to linear. I am not sure this will add to the security of the whole thing. My reasoning behind that is: The combining function needs to be invertible (we want to recover the plaintext, don't we?), so we have an 8-bit block cipher with an 8-bit key (supplied by the key stream generator). Given known plaintext and corresponding ciphertext, there should not be too many keys that map the plaintext to the ciphertext. I don't have the probability at hand how many such 'collisions' you would expect from 256 random permutations, but intuitively I would not expect too many. However, I could be wrong here and would like to be corrected in this case. Regards, Ulrich - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: Linux RNG paper
From: Travis H. [mailto:[EMAIL PROTECTED] On 5/4/06, markus reichelt [EMAIL PROTECTED] wrote: Agreed; but regarding unix systems, I know of none crypto implementation that does integrity checking. Not just de/encrypt the data, but verify that the encrypted data has not been tampered with. Are you sure? There's a aes-cbc-essiv:sha256 cipher with dm-crypt. Are they using sha256 for something other than integrity? That sounds like they are applying sha256 to the passphrase, and not for adding redundancy to the data. The big problem with disk encryption is to achieve nondeterministic encryption and authenticated encryption. Nondeterminism requires a new IV each time you encrypt a sector (I am talking here of sectors, to avoid confusion with blocks of a block cipher) for disk storage. The reason for nondeterminism is that otherwise at least common prefixes of the old and new contents show up in the ciphertext. Authenticated encryption basically prevents tampering with ciphertext going unnoticed. However, some while ago I read a paper somewhere pointing out that the lower block layer at least in linux is not capable of dealing with data errors due to authentication failure. If interest is, I could try to dig out the reference. Nevertheless, if you want to add extra IVs (not determined deterministically from the block number) and authentication tag, you could store them in extra sectors which do not show up in the plaintext-device. Caching should be not too difficult. However, if the authentication tags / IVs cannot be read anymore due to an oops-up in the code, disk failure etc. you might run into serious problems, as now multiple sectors are affected. Maybe there are other solutions? Regards, Ulrich - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
AW: [Clips] Banks Seek Better Online-Security Tools
-Ursprüngliche Nachricht- Von: Nicholas Bohm [mailto:[EMAIL PROTECTED] Gesendet: Dienstag, 6. Dezember 2005 12:03 An: Florian Weimer Cc: cryptography@metzdowd.com Betreff: Re: [Clips] Banks Seek Better Online-Security Tools Florian Weimer wrote: * Nicholas Bohm: [...] I hope, not too confidently, that before the attackers adjust enough, banks will start giving their customers FINREAD type secure-signature-creation devices of decent provenance whose security does not rely on non-compromise of my PC or network. In 2000 someone here in Germany already demonstrated how to attack smart card based HBCI transactions. Those transactions are authorized by an RSA signature done by the card. The attack demonstration used a trojan (I think it was something like back orifice) to remote control the victim's PC with the attached smart card reader, so that the PIN entered on the PC key board(!) could be sniffed and subsequently the PC including reader and smart card be used as a sort of remote signature generation device, authorizing any transaction of the attacker's choice. So under some circumstances even signature-based authorization does not work as advertised. The attack relyed on the card reader not having a separate keyboard for PIN entry. Interestingly, I wonder what would happen if a reader with display and keyboard is used in an online attack, i.e. the adversary sneaks in a fraudulent transaction when the hash for the signature is computed. I do not know from the top of my head what is supposed to be displayed in the reader's display, so I do not know what impact such an attempt would have. Any suggestions? Ulrich - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
AW: [EMAIL PROTECTED]: Skype security evaluation]
-Ursprüngliche Nachricht- Von: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] Im Auftrag von cyphrpunk Gesendet: Freitag, 28. Oktober 2005 06:07 An: [EMAIL PROTECTED]; cryptography@metzdowd.com Betreff: Re: [EMAIL PROTECTED]: Skype security evaluation] Wasn't there a rumor last year that Skype didn't do any encryption padding, it just did a straight exponentiation of the plaintext? Would that be safe, if as the report suggests, the data being encrypted is 128 random bits (and assuming the encryption exponent is considerably bigger than 3)? Seems like it's probably OK. A bit risky perhaps to ride bareback like that but I don't see anything inherently fatal. There are results available on this issue: First, a paper by Boneh, Joux, and Nguyen Why Textbook ElGamal and RSA Encryption are Insecure, showing that you can essentially half the number of bits in the message, i.e. in this case the symmetric key transmitted. Second, it turns out that the tricky part is the implementation of the decryption side, where the straight-forward way -- ignoring the padding with 0s They are zeroes, aren't they? -- gives you a system that might be attacked in a chosen plaintext scenario very efficiently, obtaining the symmetric key. See my paper Side-Channel Attacks on Textbook RSA and ElGamal Encryption at PKC2003 for details. Hope this answers your question. Ulrich - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
AW: Possibly new result on truncating hashes
John Kelsey wrote:
Unfortunately, we can't make this argument, because this
postulated collision algorithm can't be used to find a
collision in the whole SHA256 more efficiently than brute force.
Let's do the counting argument: Each time we call the
160-bit collision algorithm, we get a new pair which has the
same first 160 bits of SHA256 output, and random unrelated
last 96 bits of SHA256 output. Each pair has a probability
of 2^{-96} of colliding in the remaining bits. So, to get a
collision on the whole SHA256 using this 160-bit collision
algorithm, we expect to have to try about 2^{96} collision
pairs, each found at a cost of 2^{64}. The resulting work is
2^{64} * 2^{96} = 2^{160}, more than a straight brute-force
collision search on SHA256.
Hmm, wouldn't you expect a lot of partial collisions among all those 2^96
collision pairs? That is, after
2^80 runs of the algorithm you would obtain your first partial collision in
collision pairs, don't you?
For 2^96 that's roughly 2^32 such pairs of pairs. Those might help you to speed
up your search.
Am I missing something here?
Ulrich
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
