Philips/NXP/Mifare CRYPTO1 mostly reverse-engineered

2007-12-30 Thread Ralf-Philipp Weinmann

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

2007-04-05 Thread Ralf-Philipp Weinmann


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

2007-02-27 Thread Ralf-Philipp Weinmann


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...

2006-09-28 Thread Ralf-Philipp Weinmann


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:

2006-09-20 Thread Ralf-Philipp Weinmann


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:

2006-09-19 Thread Ralf-Philipp Weinmann


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

2006-07-31 Thread Ralf-Philipp Weinmann
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

2005-03-25 Thread Ralf-Philipp Weinmann
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?

2003-10-11 Thread Ralf-Philipp Weinmann
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]