Philips/NXP/Mifare CRYPTO1 mostly reverse-engineered
From http://cryptanalysis.eu/blog/2007/12/29/mifare-crypto1: MiFare’s CRYPTO1 stream cipher has captured my attention for a while. However, hardware reverse-engineering is not a field I actively engage in. So I was very happy when Karsten Nohl (University of Virginia), Starbug and Henryk Plötz gave a talk at the 24C3 [the 24th Congress of the Chaos Computer Club taking place in Berlin at this very moment] yesterday evening showing that they have reverse-engineered most parts of this cipher. CRYPTO1 uses a 48-bit LFSR-based filter generator to generate key stream. The filter function - if I understood correctly - uses 20 taps (this was not mentioned in the talk, I asked Karsten privately about this) however the degree of the boolean function implementing the filter, thus it remains to be seen whether algebraic attacks can be applied. Even if no algebraic attacks are applied, a BSW sampling TMTO will break CRYPTO1 completely. This was pretty obvious before they gave their talk, but now vendors actually have to worry about this being out in the wild once the feedback and the filter function have been revealed. My colleague Erik took photos of the slides which I put up on Zooomr [0]. A video recording of the talk should be available shortly and will be linked here. [0] http://www.zooomr.com/photos/ralf/sets/26758/ - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: WEP cracked even worse
On Apr 4, 2007, at 03:38 , Dave Korn wrote: On 04 April 2007 00:44, Perry E. Metzger wrote: Not that WEP has been considered remotely secure for some time, but the best crack is now down to 40,000 packets for a 50% chance of cracking the key. http://www.cdc.informatik.tu-darmstadt.de/aircrack-ptw/ Sorry, is that actually better than The final nail in WEP's coffin, which IIUIC can get the entire keystream (who needs the key?) in log2 (nbytes) packet exchanges (to oversimplify a bit, but about right order-of-magnitude)? Hi Dave, this of course is a question of how you value an attack: a key recovery usually is worth more than a decryption oracle. To send arbitrary packets with the fragmentation attacks described in [1, Section 2.6], you need just a single (suitable) data packet. However, in order to decrypt packets, you need either 2 (connectivity to other networks that you have a host on that you can control, e.g the internet) or approx. 2^7 packets (no access to outside hosts) _per byte_ that you want to decrypt. Our method surely pays of if you want to decrypt more than a handful of packets. Cheers, Ralf [1] Andrea Bittau, Mark Handley, Joshua Lackey The Final Nail in WEP’s Coffin IEEE Symposium on Security and Privacy 2006, http://doi.ieeecomputersociety.org/10.1109/SP.2006.40 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: padlocks with backdoors - TSA approved
On Feb 26, 2007, at 21:20 , Hadmut Danisch wrote: Hi, has this been mentioned here before? Yes. It is old news, Bruce Schneier's Cryptogram mentioned it in April 2004, actually [1]. Never seen anything in real world which is such a precise analogon of a crypto backdoor for governmental access. Welcome to the real world. Things suck here. Ironically, they advertise it as a big advantage and important feature, since it allows to arrive with the lock intact and in place instead of cut off. Some of apparently have the feature that you can tell *IF* the TSA has opened them with their master-keys. You are supposed to find a TSA notice in your bag if it has been opened and searched. Although I'm not sure whether you can really raise hell if they forget to stick the notice in there after having searched your bag. This is the point where I decided to have nightmares from now on. G'night then. Cheers, Ralf [1] Crypto-Gram Newsletter, April 15th, 2004 http://www.schneier.com/crypto-gram-0404.html - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Exponent 3 damage spreads...
On Sep 25, 2006, at 10:29 AM, Simon Josefsson wrote:
Leichter, Jerry [EMAIL PROTECTED] writes:
I agree that there are two issues, and they need to be treated
properly. The first - including data after the ASN.1 blob in the
signature computation but then ignoring it in determining the
semantics - is, I'll argue, an implementation error. You list only
OpenSSL as definitely vulnerable, NSS as ?, so it sounds like
only one definitive example.
Yes. I'm only familiar with NSS as a user, not as a developer. For
some reason, the Mozilla bug tracker hides information about this
problem from us, so it is difficult to track the code down.
I believe I identified the patch that solved the problem in NSS,
search for 350640 in:
http://bonsai.mozilla.org/cvsquery.cgi?branch=HEADfile=mozilla/
security/nss/date=month
The bug discussion is not public:
https://bugzilla.mozilla.org/show_bug.cgi?id=350640
Possibly also bug reports 351079 and 351848 are related to the same
problem, but these bugs are also hidden.
The actual patch for 350640 is:
http://bonsai.mozilla.org/cvsview2.cgi?
diff_mode=contextwhitespace_mode=showsubdir=mozilla/security/nss/
lib/
utilcommand=DIFF_FRAMESETfile=secdig.crev1=1.6rev2=1.7root=/
cvsroot
If some NSS developer could chime in, that would help.
Even if NSS has the same problem, one has to look at code
provenance.
Sure.
Hi Simon,
I'm not a NSS developer, but we did have a look at the code here to
figure out what EXACTLY those guys patched. The relevant portion can
quite easily be found by diff'ing the tags FIREFOX_1_5_0_6_RELEASE
vs. FIREFOX_1_5_0_7_RELEASE on their CVS tree for example. Insofar I
don't think that leaving the bug reports private after actually
shoving out the release does not really help things in this
situation; quite the opposite.
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.
At least some versions of PKCS#1 does NOT say that, e.g., RFC 3447.
RFC 3447 essentially says to generate a new token and use memcmp().
Such implementations would not be vulnerable to any of the current
attacks, except the Kaliski ASN.1 OID attack (an attack that doesn't
work on existing implementations).
See above.
Cheers,
Ralf
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [cryptography] Re: Why the exponent 3 error happened:
On Sep 20, 2006, at 3:10 PM, Kuehn, Ulrich wrote: -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). Hi Ulrich, You're using a version that has already been fixed. However the main problem seems to be that you're trying to parse a certificate in PEM format using the option -inform DER instead of -inform PEM ;) At least that's how I can reproduce your error... Cheers, Ralf smime.p7s Description: S/MIME cryptographic signature
Re: [cryptography] Re: Why the exponent 3 error happened:
On Sep 16, 2006, at 11:31 PM, Eric Young wrote: This is a question I would not mind having answered; while the exponent 3 attack works when there are low bits to 'modify', there has been talk of an attack where the ASN.1 is correctly right justified (hash is the least significant bytes), but incorrect ASN. 1 encoding is used to add 'arbitrary' bytes before the hash. So in this case some of the most significant bytes are fixed, the least significant bytes are fixed, but some in the middle can be modified. Does the exponent 3 attack work in this case? My personal feel is that his would be much harder, but is such an attack infeasible? This issue about ASN.1 parameters being an evil concept goes away if the attack can only work when the least significant bytes need to be modifiable. Hi Eric, the attack indeed is not infeasible. Although if you do not want to violate the padding specifications (minimum of eight 0xFF bytes), you need moduli longer than 1024 bits. My colleague Andrei Pyshkin had the following idea: In the following, we will assume to public exponent e=3. Let s be the signature of a message m. The message can be broken down into 3 parts: m := f_1 || v || f_2 with f_1, f_2 being fixed and v variable. Note that f_2 denotes the lowermost bits of the message. Furthermore let d=bitlength(f_2). In order to calculate a signature s such that m is a perfect cube, we carry out the following steps: 1. Calculate an x such that f_2 = x^3 mod 2^d with x 2^d. This will succeed with probability 1/2. 2. Calculate s_0 = floor(cuberoot(m)) 3. Calculate the signature s = s_0 + x - (s_0 mod 2^d) Calculating the bounds for which moduli and fixed data structures this attack will succeed is left as an excercise to the inclined reader. 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: https://certificates.starfieldtech.com/repository/sf-class2-root.crt Cheers, Ralf - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
CLC 2006 - Workshop on Codes and Lattices in Cryptography
Apologies in advance if you receive multiple copies of this announcement. -Ralf CLC2006 - Workshop on Codes and Lattices in Cryptography https://clc2006.cdc.informatik.tu-darmstadt.de September 25th-27th, 2006 Technische Universitaet Darmstadt Organizers: Johannes Buchmann - Alexander May - Ulrich Vollmer Confirmed Speakers: Miklos Ajtai (IBM, USA) Thierry Berger (Universite de Limoges, France) Johannes Blömer (Universitaet Paderborn, Germany) Nicolas T. Courtois (Axalto, France) Matthieu Finiasz (EPFL, France) Philipe Gaborit (Universite de Limoges, France) Venkatesan Guruswami (University of Washington, USA) Hideki Imai (University of Tokyo, Japan) Kazukuni Kobara (University of Tokyo, Japan) Pierre Loidreau (ENSTA, France) Alexander May (TU Darmstadt, Germany) Daniele Micciancio (University of California, San Diego) Oded Regev (Tel-Aviv University, Israel) Claus-Peter Schnorr (Universitaet Frankfurt, Germany) Nicolas Sendrier (INRIA, France) Code-based systems belong to the most promising candidates for post-quantum cryptography. They are highly efficient. By easing the constraints on storage capacity for key material, technological progress has paved the way for their practical deployment. Yet, do we feel certain enough of their security to recommend wide-spread adoption? While the last 25 years since the first proposal of such a system by R.J. McEliece have seen a steady stream of research into their security, this effort pales in comparison to the scrutiny devoted to currently deployed systems like RSA and ECC. Efficient lattice reduction algorithms have been very potent tools of cryptanalysis of many public-key cryptosystems. Applied to code-based systems this tool has turned out to be a very blunt one since the lift of cryptographically useful error-correcting codes yields lattices of intractably high dimensions with an abundance of short vectors. Yet, the question still remains open whether there is more than the surface parallelism between, say, the decoding problem and the closest vector problem in a lattice, whether cross-fertilization between the research into the security of code- and lattice-based cryptosystems is possible. This small workshop undertakes an exploration of this question and hopes to stimulate the dialogue between researchers of both communities. The topics are * Attacks on code- or lattice-based systems * Hardness of underlying problems, weak instances * The link between Decoding, Learning and Closest Vector Problems * Average versus Worst Case Complexity * Indistinguishability of hidden-trap door and random instances * Security proofs of code-based systems * Lattice reduction for cryptanalysis * Lattice reduction algorithms, including their sensitivity to properties of the instances they are applied to Contributions to the workshop are solicited by invitation only. Travel and lodging costs for the invited speakers are covered by the workshop organizers. In order to encourage the presentation of work-in-progress and contributions of survey character, all research presented may be published elsewhere. However, we kindly request that participants submit a three-page summary of their contribution for inclusion in the pre-proceedings. There will be opportunity for revision and enlargement in view of the results of the workshop. Post-proceedings will be made available to the cryptographic community from the document server of the hosting department. The organizers gratefully acknowledge the generous support of the Federal Office for Information Security (BSI). -- Ralf-P. Weinmann [EMAIL PROTECTED] PGP fingerprint: 1024D/EF114FC02F150EB9D4F275B6159CEBEAEFCD9B06 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Secure Science issues preview of their upcoming block cipher
Jerrold Leichter wrote: I can come up with a cipher provably just as secure as AES-128 very quickly (Actually, based on the paper a while back on many alternative ways to formulate AES - it had a catchy title something like How Many Ways Can You Spell AES?, except that I can't find one like that now - one could even come up with a formulation that is (a) probably as secure as AES-128; (b) actually faster in hardware or simpler to implement or whatever...) You're probably looking for [1] by Barkan and Biham. What they do is replacing the irreducible polynomial and all the constants involved in Rijndael to get what they call dual ciphers; basically those ciphers are isomorphic to Rijndael. All in all they get 240 dual ciphers which are listed in [2]. What I found more interesting back then was that they also give square dual and log dual ciphers of Rijndael. I.e. let E be the Rijndael encryption and E' be the encryption function of the square/log dual Rijndael construction. Furthermore let f be a function that either performs bytewise squaring in GF(2^8) or replaces each byte with a logarithmic representation (relative to a generator g. you also need to fix log_g(0) = -\infty for this to make sense). Then E'(f(plaintext), f(key)) = f(E(plaintext, key)) holds. The squaring construction then also naturally extends to what they call higher-order self dual ciphers: meaning you can apply the squaring multiple times. In 2004 Wu, Lu and Laih then demonstrated that using Barkan's and Biham's method can indeed lead to more efficient implementations of AES/Rijndael in hardware. Cheers, Ralf [1] Elad Barkan and Eli Biham: In How Many Ways Can You Write Rijndael? ASIACRYPT 2002, Springer note: also on ePrint as http://eprint.iacr.org/2002/157 if you don't have Springer Link access [2] Elad Barkan and Eli Biham: The Book of Rijndaels http://eprint.iacr.org/2002/158 [3] Shee-Yau Wu and Shih-Chuan Lu and Chi Sung Laih: Design of AES Based on Dual Cipher and Composite Field Topics in Cryptology, CT-RSA 2004, Springer -- Ralf-P. Weinmann [EMAIL PROTECTED] TU Darmstadt, FB Informatik, FG Theoretische Informatik Tel: +49-(0)6151-16-6628 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Easy VPNs?
Ian Grigg [EMAIL PROTECTED] writes: I'm curious - my understanding of a VPN was that it set up a network that all applications could transparently communicate over. Port forwarding appears not to be that, in practice each application has to be reconfigured to talk to the appropriate port, or, each port has to be forwarded. Am I missing something here? If there is an easy SSH based strategy for VPNs, what is it? iang Well it's not a VPN per se, and it's dependent on the SSH client you're using but it may help you anyway: When using an OpenSSH [1] client one can enable dynamic portforwarding (the -D switch or the DynamicForward option in ssh_config) which gives you a SOCKS server on the machine you ssh from. Under un*xy operating systems supporting LD_PRELOAD or similar dynamic linker options you can then use something like tsocks [2] to make all dynamically linked (and non-suid) applications performing only outbound TCP connections use your SOCKS server. This is sort of a hack but works pretty good for me. Something I've done as well in the past is run Slirp[3] on a remote machine and have an SSH tunnel between Slirp and the PPP daemon on my local machine. This assumes you have sufficient privileges on the client machine however. It allows you to do both outbound TCP and UDP however I do not really advise this strategy because of [4]. Cheers, Ralf [1] OpenSSH http://www.openssh.org [2] TSOCKS - A transparent SOCKS proxying library http://tsocks.sourceforge.net [3] Slirp http://slirp.sourceforge.net [4] Why TCP over TCP Is a Bad Idea http://sites.inka.de/sites/bigred/devel/tcp-tcp.html -- Ralf-P. Weinmann [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
