>From - Mon Jul 07 07:59:54 1997 Path: news.ibm.net.il!ibm.net!newsfeed.uk.ibm.net!ibm.net!nntp.uio.no!news.maxwell.syr.edu!howland.erols.net!agate!not-for-mail From: daw@joseph.cs.berkeley.edu (David Wagner) Newsgroups: sci.crypt Subject: Re: Break EC-Key Cards / PIN Numbers. Date: 5 Jul 1997 14:36:12 -0700 Organization: ISAAC Group, UC Berkeley Lines: 21 Message-ID: <5pmeoc$9j1@joseph.cs.berkeley.edu> References: <5p8dlh$egm$1@nz12.rz.uni-karlsruhe.de> <33B88085.6AA9@cs.purdue.edu> <5pao4b$qf$1@rzsun02.rrz.uni-hamburg.de> <33B9430D.4C06@cs.purdue.edu> NNTP-Posting-Host: joseph.cs.berkeley.edu Xref: news.ibm.net.il sci.crypt:52746 X-Cache: nntpcache 1.0.6 (see ftp://suburbia.net/pub/nntpcache) X-Cache: nntpcache 1.0.6 (see ftp://suburbia.net/pub/nntpcache) Thanks for posting a partial description of the European card PIN algorithm. I had not seen that before. Here's an idea. Note that some cards give you more bits of known ciphertext than others. For instance, PIN - offset1 = [6-9][6-9][6-9][6-9] gives you 16 bits of known ciphertext; about 2.5% of all cards have this form, and this form is easily recognizable given a magnetic card reader. Therefore, I propose that you gather a number of cards and take the best three or four of the lot (e.g. the ones which give you the most known ciphertext). Furthermore, in the key search engine, you should try to eliminate trial pool/institute keys as rapidly as possible by using the best card first. (In other words, find the card with the most known ciphertext, and when you guess a key, check it against that card first, to reduce the number of false positives as much as possible; only if it passes for that card should you try it against a second card.) Remember that you only need to have enough known plaintext/ciphertext pairs on the chip to reduce the off-chip I/O to a manageable level; therefore, two known texts from two cards should suffice (on the chip), because 2^{56 - 32} keys / 1 month ~= 4 keys / second should be easily manageable; handle the remaining keys that pass those two tests in software. >From - Mon Jul 07 08:06:30 1997 Path: news.ibm.net.il!ibm.net!platform.uoregon.edu!news.uoregon.edu!hookup!news.miracle.net!uunet!in2.uu.net!169.207.30.10!newspump.sol.net!howland.erols.net!gatech!purdue!mozo.cc.purdue.edu!news From: Markus Kuhn Newsgroups: sci.crypt Subject: Re: Break EC-Key Cards / PIN Numbers. Date: Tue, 01 Jul 1997 12:49:01 -0500 Organization: Purdue University Lines: 98 Message-ID: <33B9430D.4C06@cs.purdue.edu> References: <5p8dlh$egm$1@nz12.rz.uni-karlsruhe.de> <33B88085.6AA9@cs.purdue.edu> <5pao4b$qf$1@rzsun02.rrz.uni-hamburg.de> NNTP-Posting-Host: asgard.cs.purdue.edu Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Mailer: Mozilla 3.0 (X11; I; SunOS 5.5.1 sun4m) Xref: news.ibm.net.il sci.crypt:52606 X-Cache: nntpcache 1.0.6 (see ftp://suburbia.net/pub/nntpcache) X-Cache: nntpcache 1.0.6 (see ftp://suburbia.net/pub/nntpcache) Bodo Moeller wrote: > Why would you restrict the key search to the institute key? Just to be on the safe side. Are you sure that the pool keys are the same for all banks? My assumption was, that *every* bank generates one institute key KI and three pool keys KP1, KP2, KP3, and makes KP1 available to all other banks (and keeps KP2 and KP3 as backup keys in case of a KP1 compromise). The memory requirement of one key per bank is not that high for the transaction centers or even the off-line ATMs. In addition, as we are not sure whether all pool offsets are actually used and not filled with a dummy value optimized to confuse a Bayesian maximum likelihood estimation of the PIN, I would pick the institute key as here we can be sure about the DES output bits and do not have to trust on the validity of e.g. offset1. The amount of known bits is not that much lower for the output of the institute key encryption. That the institute key is actually used and that the bank itself does not also use an offset can be proofed by modifying the offsets on the card and check whether the PIN has changed on an institute ATM. This works nicely with offset1 on POS terminals, you can select your own PIN with a magnetic card writer there, modifications to offset2 and offset3 do not change the PIN on POS terminals today. Let's see, how many cards we would need: digit DES-output-nibble known bits frequency 0 x0x0 3 2/16 1 x0x1 3 2/16 2 xxX0 3 2/16 3 xxX1 3 2/16 4 x1x0 3 2/16 5 x1x1 3 2/16 6 0110 4 1/16 7 0111 4 1/16 8 1000 4 1/16 9 1001 4 1/16 (x is an unknown bit, but all x per nibble are the same and X is not x.) Expected number of known bits per digit for digits 2-4: 6*3*2/16 + 4*4*1/16 = 3.25 For the first digit, we have (due to the 0->1 transform) digit DES-output-nibble known bits frequency 0 - - 0/16 1 x0xy 2 4/16 ...(same as above) ... Expected number of known bits per digit for digit 1: 1*2*4/16 + 4*3*2/16 + 4*4*1/16 = 3 > If you > know the PIN and the offsets, it is possible to hunt for the pool > keys. They are easier targets because the 0 --> 1 rule at the first > PIN digit does not apply: Five cards (which need not be from the same > bank) should usually suffice to determine unique solutions. You see, you just loose a quarter of a bit per card for the institute key hunt. Who cares ... For an institute key hunt, you get 1*3 + 3*3.25 = 12.75 known ciphertext bits and 64 bit known plain text bits, therefore, the unicity distance is 56/12.75 = 4.4 cards if I haven't made any errors. Ok, the five cards you mentioned sound reasonable. For a sure hit, you probably want to double the number to get at least one bit per bit redundancy for the key that you have found. I could provide you with the plaintext/ciphertext for 9 cards, but they are from many different banks and therefore, I do not believe that these cards share all any same key. But getting a dozend cards from one target bank should be fairly trivial. Note for readers from outside Europe: We are talking about the EuroCheque debit card ATM system used in most European countries (where VISA and MasterCard are unlike in the U.S. not very widely used). The algorithmical weaknesses of the EC-PIN do NOT apply to VISA card (for Mastercard I do not know the algorithm). The weakness of the EC-PIN has been made aware to the broad public in a recent German court decision, where a bank had to refund the money that a thief obtained with a stolen EC card. The banks have announced to change the algorithm and replace all PINs soon. Markus -- Markus Kuhn, Computer Science grad student, Purdue University, Indiana, US, email: kuhn@cs.purdue.edu >From - Mon Jul 07 08:06:37 1997 Path: news.ibm.net.il!ibm.net!newsfeed.uk.ibm.net!ibm.net!nntp.uio.no!news.apfel.de!eerie.fr!news.maxwell.syr.edu!nntprelay.mathworks.com!news.mathworks.com!fu-berlin.de!news-ber1.dfn.de!news-ham1.dfn.de!news.dkrz.de!news.uni-hamburg.de!rzdspc5.informatik.uni-hamburg.de!3moeller From: 3moeller@rzdspc5.informatik.uni-hamburg.de (Bodo Moeller) Newsgroups: sci.crypt Subject: Re: Break EC-Key Cards / PIN Numbers. Date: 1 Jul 1997 11:02:35 GMT Organization: University of Hamburg -- Germany Lines: 23 Message-ID: <5pao4b$qf$1@rzsun02.rrz.uni-hamburg.de> References: <5p8dlh$egm$1@nz12.rz.uni-karlsruhe.de> <33B88085.6AA9@cs.purdue.edu> NNTP-Posting-Host: rzdspc5.informatik.uni-hamburg.de Xref: news.ibm.net.il sci.crypt:52576 X-Cache: nntpcache 1.0.6 (see ftp://suburbia.net/pub/nntpcache) X-Cache: nntpcache 1.0.6 (see ftp://suburbia.net/pub/nntpcache) Markus Kuhn : > Bernhard-Hermann Haak: >> I'd like to break the PIN number system of the EC Card. [...] > Without a modified DES brute force machine a la Wiener and at > least around 20 cards from the same bank (with the same > institute key) to reach key equivocation, this is a futile > effort. Why would you restrict the key search to the institute key? If you know the PIN and the offsets, it is possible to hunt for the pool keys. They are easier targets because the 0 --> 1 rule at the first PIN digit does not apply: Five cards (which need not be from the same bank) should usually suffice to determine unique solutions. Also, the expected time for a successful search is reduced by about 50 % if your goal is just to find any one of the three pool keys. (The three key searches can be done at the same time; the computational cost for working through the whole keyspace is not much higher than in the case of a search for only one key.) Bodo Moeller <3moeller@informatik.uni-hamburg.de> >From - Mon Jul 07 08:06:58 1997 Path: news.ibm.net.il!ibm.net!newsfeed.uk.ibm.net!ibm.net!news-feed.inet.tele.dk!news.maxwell.syr.edu!news-peer.sprintlink.net!news-pull.sprintlink.net!news-in-east.sprintlink.net!news.sprintlink.net!Sprint!130.207.244.18!gatech!purdue!mozo.cc.purdue.edu!news From: Markus Kuhn Newsgroups: sci.crypt Subject: Re: Break EC-Key Cards / PIN Numbers. Date: Mon, 30 Jun 1997 22:59:01 -0500 Organization: Purdue University Lines: 96 Message-ID: <33B88085.6AA9@cs.purdue.edu> References: <5p8dlh$egm$1@nz12.rz.uni-karlsruhe.de> NNTP-Posting-Host: asgard.cs.purdue.edu Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Mailer: Mozilla 3.0 (X11; I; SunOS 5.5.1 sun4m) Xref: news.ibm.net.il sci.crypt:52560 X-Cache: nntpcache 1.0.6 (see ftp://suburbia.net/pub/nntpcache) X-Cache: nntpcache 1.0.6 (see ftp://suburbia.net/pub/nntpcache) Bernhard-Hermann Haak wrote: > I'd like to break the PIN number system of the EC Card. As far as I know, > BLZ, Konto Number, Cardnumber are DES encrypted (1) with a bank-key; the n*64 > BIT output are (2) reduced to 16 BIT. Then (in hex) > you get 4 Charsout of { 0,..9,A,..,F} . > 0,..,9 are mapped onto 0,..,9 > A,..,F are mapped onto 0,..,5 > if the first number is a "0" it will be changed into a "1". > so to break the bank \ pool key, the exact procedure (1) and (2) are of > primary interest (e.g. How data is converted into n*64 BIT input, and how > the output is compressed). Without a modified DES brute force machine a la Wiener and at least around 20 cards from the same bank (with the same institute key) to reach key equivocation, this is a futile effort. If on the other hand, you have around 100 000 USD available in order to build such a DES brute-force search engine or can convince thousands of Internet users to join such a sinister attack, then ... ;-) Nevertheless: You take the digits 4-8 of the BLZ, followed by the 10 digit account number, followed by the 1 digit card sequence number, all as found in the fields 3 and field 19 of track 3 of the magnetic strip (see ISO 4909). This gives you a 16-digit BCD number, i.e. a 64-bit data block that is encrypted with DEA. From the result, you look at the hex representation of the second and third byte, and from there on, you have already described the rest accurately in order to get the PIN from the institute key. For getting the PIN from the pool key, you do not replace the 0 by a none and add to the pre-PIN obtained this way the offset found in field 13.2, 27.2 or 27.3 of track 3. This addition is a per-digit mod 10 addition, i.e. no carry. That's all. Here is the output of my EC-PIN analysis software. The track 3 input data and the known PIN given in this example are not related to any really existing card of course for purposes of this public demonstration. The numbers however are consistent and allow you to check whether you have understood the algorithm. raw track3 data: 015924358270=00121363996=28095401000100031600130127950100000 94123284410595==1=41066083286950000000000000 Format-ID: 01 (ISO 4909) Group-ID: 59 BLZ: 24358270 Kontonr: 0012136399/6 country: 280 (DE) currency: 954 (DEM) auth. amount: 1000e0 remaining: 1000e0 next cycle: [199]3-160 cycle len: 01 d retries left: 3 PIN alg: 01 (DES) offset1: 2795 offset2: 6083 offset3: 2869 DES input: 5827000121363993 interchange: 0 (unrestr.) TA/SR: 10/00/00 exp date: 94-12 card seq nr: 3 security number: 2/84410595 relay marker: 1 avail date: [199]4-106 language: 5 (de) rest: 0000000000000 A-priori PIN digit distribution estimate based on three valid offsets: 1:13.3% 2:13.3% 3:13.3% 4:13.3% 5:13.3% 6:13.3% 7:13.3% 8:03.3% 9:03.3% 0:00.0% 0:21.3% 1:21.3% 2:21.3% 3:10.7% 4:05.3% 5:05.3% 8:05.3% 9:05.3% 7:02.7% 6:01.3% 0:22.9% 1:22.9% 2:11.4% 3:11.4% 9:11.4% 4:05.7% 8:05.7% 5:02.9% 6:02.9% 7:02.9% 0:14.3% 3:14.3% 4:14.3% 5:14.3% 1:07.1% 2:07.1% 6:07.1% 7:07.1% 8:07.1% 9:07.1% Suggested PIN attempt order: 1000 (0.093%), 1003 (0.093%), 1004 (0.093%), 1005 (0.093%), 6000 (0.093%), 6004 (0.093%), 2003 (0.093%), 2004 (0.093%), 2005 (0.093%), 2010 (0.093%), 1010 (0.093%), 1013 (0.093%), 1014 (0.093%), 1015 (0.093%), ... known PIN: 1307 DES-output (2nd+3rd byte) Institute: x0x1/xxX1/x0x0/0111 P1: 1001/0110/x0x1/xxX0 P2: x1x1/xxX1/xxX0/x1x0 P3: 1001/x1x1/x1x0/1000 In the suggested PIN attempt order, the known PIN is on place 790. In the DES output, there are some unknown bits do to the decimalization. An x represents either a 0 or a 1 (but consistently within one nibble), and X represents "not x". I will probably not yet release the algorithm for the optimal PIN digit probability estimation used in this software before the banks have replaced this quite silly PIN algorithm by a new one as they have announced to do later this year. It is a quite trivial bayesian conditional probability, but someone who normally doesn't have the math background might use it to do bad things, and I don't want to support this. Markus -- Markus Kuhn, Computer Science grad student, Purdue University, Indiana, US, email: kuhn@cs.purdue.edu