Cryptography-Digest Digest #119, Volume #10 Fri, 27 Aug 99 09:13:03 EDT
Contents:
Handbook of Applied Crypto & security of GQ signature (Francois Grieu)
receiving a piece of message ("Alessandro Guarino")
Re: How does RC5 work? (Tom St Denis)
512-bit RSA key factored (second attempt to post) (Herman J.J. te Riele)
Re: Key to Ciphertext Ratio's (Tom St Denis)
Re: NIST AES FInalists are.... (Helger Lipmaa)
Re: RSA and Microcontroller (Tom St Denis)
Re: btw (Tom St Denis)
Re: CryptoAPI (Tom St Denis)
Re: Key to Ciphertext Ratio's (Frank Gifford)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Francois Grieu)
Subject: Handbook of Applied Crypto & security of GQ signature
Date: Fri, 27 Aug 1999 12:23:55 +0200
In the Handbook of Applied Cryptography (1st ed.) by Alfred J. Menezes,
Paul C. van Oorschot and Scott A. Vanstone, paragraph 11.50 page 451,
there is a note on the security of the Guillou-Quisquater
signature scheme. An attack is suggested where
"The adversary selects a message m and computes
l = h(m||JA^t) for sufficiently many values of t
until l = t (mod e); this is expected to occur
within O(sqrt(e)) trials."
To me it appears the attack suggested requires O(e) trials.
I do understand that, by the birthday paradox, one can find
distincts t and u such that h(m||JA^t) = h(m||JA^u) with
O(sqrt(e)) trials and memory. But I fail to see how it helps,
and/or to find a O(sqrt(e)) attack.
So what ? How does e influence the security of GQ signatures ?
Francois Grieu
------------------------------
From: "Alessandro Guarino" <[EMAIL PROTECTED]>
Subject: receiving a piece of message
Date: Fri, 27 Aug 1999 12:52:22 +0200
Hello to everybody, this is my first mail in this newsgroup and then nice to
meet everybody.
My question is : if I want to decrypt a message encrypt with a private key
algorithm do I have to receive the message from the beginning?
I mean, if I start to receive the encrypted message by the middle, am I
able to decrypt the remaining message?
thanks to everybody
Alex
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: How does RC5 work?
Date: Fri, 27 Aug 1999 11:30:55 GMT
In article <7q4dvv$mok$[EMAIL PROTECTED]>,
"Brian Mullen" <[EMAIL PROTECTED]> wrote:
> I've read RSA's FAQ on it, but I don't understand it completely. Is
there
> another source of information on this protocol? My main problem is
the key
> expansion step. When the key is copied into array L[0...c-1] it says
that
> c=[b/u]. b=bytes in the secret key, and u=(word size in bits)/8.
What
> about a basic RC5-32/12/5? There, u=32/8 so c=(5/4). How does that
work?
> How can you have a fraction as a location in the array? Any
tutorials on
> RC5 would be appreciated...
>
The key schedule stumped me at first as well (funny cuz it's really
easy). Here is a snippet of code from CDLL (for RC6 but it's the same
anyways).
---
/* copy user key into L array and find c */
memset(L, 0, 32);
for (i = 0; i < keysize; i++)
L[i >> 2] = (L[i >> 2] << 8) | Key[i];
c = (keysize / 4) + !(!(keysize % 4));
---
So first I zero the entire array (cuz you have to zero extend words and
this was a simple way todo it). Then you copy a byte from Key (the
user key), shift the current 32-bit word left 8, or them together. So
basically if your key is 'abcdefgh' your key is abcd efgh (msb first).
The 'i >> 2' is picking the 'i / 4' word at the time, so you only pack
4 octets into each 32-bit word. The last line calculates (hehehe) the
number of 32-bit words in the key. It also add on any little
incomplete words (say 72-bit keys...).
BTW checkout RC5's cool source if you want some good info.
---
/* RC5REF.C -- Reference implementation of RC5-32/12/16 in C. */
/* Copyright (C) 1995 RSA Data Security, Inc. */
typedef unsigned long WORD; /* Should be 32-bit = 4 bytes
*/
#define w 32 /* word size in bits */
#define r 12 /* number of rounds */
#define b 16 /* number of bytes in key */
#define c 4 /* number words in key = ceil(8*b/w)*/
#define t 26 /* size of table S = 2*(r+1) words */
WORD S[t]; /* expanded key table */
WORD P = 0xb7e15163, Q = 0x9e3779b9; /* magic constants */
/* Rotation operators. x must be unsigned, to get logical right shift*/
#define ROTL(x,y) (((x)<<(y&(w-1))) | ((x)>>(w-(y&(w-1)))))
#define ROTR(x,y) (((x)>>(y&(w-1))) | ((x)<<(w-(y&(w-1)))))
void RC5_ENCRYPT(WORD *pt, WORD *ct) /* 2 WORD input pt/output ct */
{ WORD i, A=pt[0]+S[0], B=pt[1]+S[1];
for (i=1; i<=r; i++)
{ A = ROTL(A^B,B)+S[2*i];
B = ROTL(B^A,A)+S[2*i+1];
}
ct[0] = A; ct[1] = B;
}
void RC5_DECRYPT(WORD *ct, WORD *pt) /* 2 WORD input ct/output pt */
{ WORD i, B=ct[1], A=ct[0];
for (i=r; i>0; i--)
{ B = ROTR(B-S[2*i+1],A)^A;
A = ROTR(A-S[2*i],B)^B;
}
pt[1] = B-S[1]; pt[0] = A-S[0];
}
void RC5_SETUP(unsigned char *K) /* secret input key K[0...b-1] */
{ WORD i, j, k, u=w/8, A, B, L[c];
/* Initialize L, then S, then mix key into S */
for (i=b-1,L[c-1]=0; i!=-1; i--) L[i/u] = (L[i/u]<<8)+K[i];
for (S[0]=P,i=1; i<t; i++) S[i] = S[i-1]+Q;
for (A=B=i=j=k=0; k<3*t; k++,i=(i+1)%t,j=(j+1)%c) /* 3*t > 3*c */
{ A = S[i] = ROTL(S[i]+(A+B),3);
B = L[j] = ROTL(L[j]+(A+B),(A+B));
}
}
---
Tom
--
PGP 6.5.1 Key
http://mypage.goplay.com/tomstdenis/key.pgp
PGP 2.6.2 Key
http://mypage.goplay.com/tomstdenis/key_rsa.pgp
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (Herman J.J. te Riele)
Subject: 512-bit RSA key factored (second attempt to post)
Date: Fri, 27 Aug 1999 11:37:46 GMT
Factorization of a 512-bits RSA key using the Number Field Sieve
================================================================
On August 22, 1999, we found that the 512-bits number
RSA-155 =
1094173864157052742180970732204035761200373294544920599091384213147634\
9984288934784717997257891267332497625752899781833797076537244027146743\
531593354333897
can be written as the product of two 78-digit primes:
102639592829741105772054196573991675900716567808038066803341933521790711307779
*
106603488380168454820927220360012878679207958575989291522270608237193062808643
Primality of the factors was proved with the help of two different primality
proving codes. An Appendix gives the prime decompositions of p +- 1.
The number RSA-155 is taken from the RSA Challenge list
(see http://www.rsa.com/rsalabs/html/factoring.html).
This factorization was found using the Number Field Sieve (NFS) factoring
algorithm, and beats the 140-digit record RSA-140 that was set on
February 2, 1999, also with the help of NFS [RSA140].
The amount of computer time spent on this new factoring world record is
estimated to be equivalent to 8000 mips years.
For the old 140-digit NFS-record, this effort was estimated to be
2000 mips years. Extrapolation using the asymptotic complexity formula
for NFS would predict approximately 14000 mips years for RSA-155. The gain
is caused by an improved application of the polynomial search method used
for RSA-140.
For information about NFS, see [LL]. For additional information,
implementations and previous large NFS factorizations, see [DL, E1, E2, GLM].
Polynomial selection
====================
The following two polynomials
F_1(x,y) = 11 93771 38320 x^5
- 80 16893 72849 97582 y *x^4
- 66269 85223 41185 74445 y^2*x^3
+ 1 18168 48430 07952 18803 56852 y^3*x^2
+ 745 96615 80071 78644 39197 43056 y^4*x
- 40 67984 35423 62159 36191 37084 05064 y^5
F_2(x,y) = x - 3912 30797 21168 00077 13134 49081 y
were selected with the help of a polynomial search method developed by
Peter Montgomery (Microsoft Research, USA and CWI) and Brian Murphy
(The Australian National University, Canberra), which was applied already
to RSA-140, and now, even more successfully, to RSA-155.
The polynomial F_1(x,y) was chosen to have a good combination of
two properties: being unusually small over its sieving region and
having unusually many roots modulo small primes (and prime powers).
The effect of the second property alone gives F_1(x,y) a smoothness
yield comparable to that of a polynomial chosen at random for an
integer of 137 decimal digits.
Measured in a different way: the pair (F_1, F_2) has a yield of relations
approximately 13.5 times that of a random polynomial selection for
RSA-155 (the corresponding figure for the polynomial selected for the
RSA-140 factorisation is 8).
The polynomial selection took approximately 100 MIPS years,
which is equivalent to 0.40 CPU years on a 250 MHz SGI Origin 2000
processor (most of the searches were done on such processors).
The original polynomial selection code was ported by Arjen Lenstra
to use his multiple precision arithmetic package LIP.
Brian Murphy, Peter Montgomery, Arjen Lenstra and Bruce Dodson
ran the polynomial searches for RSA-155 with this code. The above
polynomial emerged from Bruce Dodson's search.
Calendar time for the polynomial selection was approximately nine
weeks.
The Sieving
===========
Sieving was done on about 160 175-400 MHz SGI and Sun workstations,
on 8 300 MHz SGI Origin 2000 processors, on about 120 300-450 MHz
Pentium II PCs, and on 4 500 MHz Digital/Compaq boxes.
The total amount of CPU-time spent on sieving was 35.7 CPU years
estimated to be equivalent to approximately 8000 mips years.
Calendar time for sieving was 3 1/2 months.
For the purpose of comparison, both lattice sieving and line sieving were used.
Lattice sieving was introduced by Pollard [P] and the code used is based
on the implementation described in [GLM, Cetal].
For the lattice sieve, a factor base bound of 16 777 216 (2^24) was chosen,
both for the rational and for the algebraic side. Two large primes were
allowed on both sides.
Most of the line sieve was carried out with two large primes on both the
rational and the algebraic side. The rational factor base consisted of the
primes < 44 000 000 and the algebraic factor base of the primes < 110 000 000.
Some line sieving allowed three large primes instead of two on the algebraic
side. In that case the rational factor base consisted of the primes < 8 000 000
and the algebraic factor base of the primes < 25 000 000.
For both sieves the large prime bound 1 000 000 000 was used both
for the rational and for the algebraic primes.
A total of 124 722 179 relations were generated, 71% of them with lattice
sieving (L), 29% with line sieving (C). Among them, there were 39 187 441
duplicates, partially because of the simultaneous use of the two sievers.
Sieving was done at eleven different locations with the following contributions:
(L: using lattice sieving code from Arjen K. Lenstra
C: using line sieving code from CWI)
20.1 % (3057 CPU days) Alec Muffett (L at Sun Microsystems Professional
Services, Camberley, UK)
17.5 % (2092 CPU days) Paul Leyland (L,C at Microsoft, Cambridge, UK)
14.6 % (1819) Peter L. Montgomery, Stefania Cavallar (C,L at CWI, Amsterdam)
13.6 % (2222) Bruce Dodson (L,C at Lehigh University, Bethlehem, PA, USA)
13.0 % (1801) Francois Morain and Gerard Guillerm
(L,C at Ecole Polytechnique, Palaiseau, France)
6.4 % (576) Joel Marchand (L,C at Ecole Polytechnique/CNRS, Palaiseau, France)
5.0 % (737) Arjen K. Lenstra (L at Citibank, Parsippany, NJ, USA
and Univ. of Sydney, Australia)
4.5 % (252) Paul Zimmermann (C at Inria Lorraine and Loria, Nancy, France)
4.0 % (366) Jeff Gilchrist (L at Entrust Technologies Ltd., Ottawa, Canada)
0.65 % (62) Karen Aardal (L at Utrecht University, The Netherlands)
0.56 % (47) Chris and Craig Putnam (L at ?)
Calendar time for the sieving was 3.7 months.
The relations were collected at CWI and required 3.7 Gbytes of disk space.
^^^
Filtering and linear algebra
============================
The filtering of the data and the building of the matrix were carried out
at CWI and took one month.
The resulting matrix had 6 699 191 rows, 6 711 336 columns, and weight
417 132 631 (62.27 nonzeros per row).
With the help of Peter Montgomery's Cray implementation of the blocked
Lanczos algorithm (cf. [M95]) it took 224 CPU hours and 2 Gbytes of central
memory on the Cray C916 at the SARA Amsterdam Academic Computer Center to find
64 dependencies among the rows of this matrix.
Calendar time for this job was 9 1/2 days.
Square root
===========
On August 20-21, 1999, four different square root (cf. [M93]) jobs were
started in parallel on four different 300 MHz processors of CWI's SGI Origin
2000, each handling one dependency.
One job found the factorisation after 39.4 CPU-hours, the other three jobs
found the trivial factorization after 38.3, 41.9, and 61.6 CPU-hours (different
CPU times are due to the use of different parameters in the four jobs).
Herman te Riele, CWI, August 26, 1999
with the algorithmic and sieving contributors:
Stefania Cavallar
Bruce Dodson
Arjen Lenstra
Walter Lioen
Peter L. Montgomery
Brian Murphy
and the sieving contributors:
Karen Aardal
Jeff Gilchrist
Gerard Guillerm
Paul Leyland
Joel Marchand
Francois Morain
Alec Muffett
Craig and Chris Putnam
Paul Zimmermann
Acknowledgements are due to the contributors of idle PC and workstation cycles,
to the Dutch National Computing Facilities Foundation (NCF) for the use of
the Cray-C916 supercomputer at SARA and (in alphabetical order) to
Centre Charles Hermite (Nancy, France),
Citibank (Parsippany, NJ, USA),
CWI (Amsterdam, The Netherlands),
Ecole Polytechnique/CNRS (Palaiseau, France),
Entrust Technologies Ltd. (Ottawa, Canada),
Lehigh University (Bethlehem, PA, USA),
the Magma Group of John Cannon at the University of Sydney,
the Medicis Center at Ecole Polytechnique (Palaiseau, France),
Microsoft Research (Cambridge, UK),
Sun Microsystems Professional Services (Camberley, UK), and
The Australian National University (Canberra, Australia)
for the use of their computing resources.
References:
===========
[RSA140]Stefania Cavallar, Bruce Dodson, Arjen Lenstra, Paul Leyland,
Walter Lioen, Peter L. Montgomery, Brian Murphy, Herman te Riele,
and Paul Zimmermann,
Factorization of RSA-140 using the Number Field Sieve, to appear in:
Lam Kwok Yan, Eiji Okamoto, and Xing Chaoping, editors,
Advances in Cryptology -- Asiacrypt '99,
Lecture Notes in Computer Science # xxxx,
Springer--Verlag, Berlin, etc., 1999.
[Cetal] James Cowie, Bruce Dodson, R.-Marije Elkenbracht-Huizing,
Arjen K. Lenstra, Peter L. Montgomery and Joerg Zayer,
A world wide number field sieve factoring record: on to 512 bits,
pp. 382-394 in: Kwangjo Kim and Tsutomu Matsumoto (editors),
Advances in Cryptology - Asiacrypt '96, Lecture Notes in
Computer Science # 1163, Springer-Verlag, Berlin, 1996.
[DL] B. Dodson, A.K. Lenstra, NFS with four large primes: an
explosive experiment, Proceedings Crypto 95, Lecture Notes
in Comput. Sci. 963, (1995) 372-385.
[E1] R.-M. Elkenbracht-Huizing, Factoring integers with the
Number Field Sieve, Doctor's Thesis, Leiden University,
1997.
[E2] R.-M. Elkenbracht-Huizing, An implementation of the number
field sieve, Exp. Math. 5, (1996) 231-253.
[GLM] R. Golliver, A.K. Lenstra, K.S. McCurley, Lattice sieving
and trial division, Algorithmic number theory symposium,
Proceedings, Lecture Notes in Comput. Sci. 877, (1994) 18-27.
[LL] A.K. Lenstra, H.W. Lenstra, Jr., The development of the
number field sieve, Lecture Notes in Math. 1554, Springer-
Verlag, Berlin, 1993
[M93] Peter L. Montgomery, Square roots of products of algebraic
numbers, in Proceedings of Symposia in Applied Mathematics,
Mathematics of Computation 1943-1993, Vancouver, 1993,
Walter Gautschi, ed.
[M95] Peter L. Montgomery, A block Lanczos algorithm for finding
dependencies over GF(2), Proceedings Eurocrypt 1995,
Lecture Notes in Comput. Sci. 921, (1995) 106-120.
[P] J.M. Pollard, The lattice sieve, pages 43-49 in [LL].
Appendix
Here are the P+-1 factorizations of the factors:
102639592829741105772054196573991675900716567808038066803341933521790711307779
p78
102639592829741105772054196573991675900716567808038066803341933521790711307778
2.607.305999.
276297036357806107796483997979900139708537040550885894355659143575473
102639592829741105772054196573991675900716567808038066803341933521790711307780
2.2.3.5.5253077241827.
325649100849833342436871870477394634879398067295372095291531269
106603488380168454820927220360012878679207958575989291522270608237193062808643
p78
106603488380168454820927220360012878679207958575989291522270608237193062808642
2.241.430028152261281581326171.
514312985943800777534375166399250129284222855975011
106603488380168454820927220360012878679207958575989291522270608237193062808644
2.2.3.130637011.237126941204057.10200242155298917871797
28114641748343531603533667478173
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Key to Ciphertext Ratio's
Date: Fri, 27 Aug 1999 11:25:09 GMT
In article <7q4kqj$h1f$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
>
> 1. Could it be possible that two different key's for a given
ciphertext
> produce two legitimate plaintexts? This does not necessarily assume
> alpha-numeric text.
Well yes, cause each key defines one permutation of 2^64 to 2^64.
There are in fact 2^64! possible keys which is what I think you are
looking for. It is possible that some keys decrypt one ciphertext to
ascii plaintext (anything with the 8th bit zeroed), because there are
in fact 2^56 different ascii blocks out (i.e you have a 1 in 256 chance
of getting ascii as the output). So try 128 random keys and you should
find one ascii block, try another 128 random keys and you should find
another (128 is avg over 2^(8-1))
> 2. What are the chances that two or more key's can encrypt the same
> plaintext to identicle ciphertexts?
Same thing. Depends on the cipher though. Basically asking encrypt-
>decrypt or decrypt->plaintext collisions is the same question.
Obviously with any cipher there are going to be collisions, they are
hopefully non-linear (i.e cannot find relationships behind collisions)
I dunno exact numbers here, but generally it's very low or zero. You
could easily perform a 'mini-empiracle' test running two copies of a
cipher, passing random inputs (I would not use a binary counter for the
plaintext since that will skew the test). Then test 2^40 input blocks
and see how many match. You can then extrapolate the results to 2^64.
Use a 64-bit LFSR for the input block, so you know you don't repeat
any, and they won't be skewed.
> 3. Can this be exploited? Certainly it could make a brute-force
attack
> much easier if one gets lucky.
Well sometimes this can be exploited. If you have a known-plaintext
pair and you find a key that works, you can search thru that
keys 'family' if you can find a relationship (say there are 2^20
classes defined by the top twenty bits of the key ...).
> Anyway, food for thought, or in this case thought over food.
Hmm food.
Tom
--
PGP 6.5.1 Key
http://mypage.goplay.com/tomstdenis/key.pgp
PGP 2.6.2 Key
http://mypage.goplay.com/tomstdenis/key_rsa.pgp
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Helger Lipmaa <[EMAIL PROTECTED]>
Subject: Re: NIST AES FInalists are....
Date: Fri, 27 Aug 1999 11:44:42 +0000
rosi wrote:
> Memory is not just memory for practical purposes, am I right?
>
> Still the basics. We've got to put stuff in memory. I doubt if we could
> fill up '2^n memory' in less time in the general case, or in particular
> cases that interest us. I favor the view that complexity is in that of the
> description. If the description does not 'allow' parallelism or speed
> up (in the conventional manner), I doubt if we can do any more.
>
> Trade-off up to a point, IMO. Still the same thing.
>
> --- (My Signature)
>
> >
> >If you arrange the memory as a binary tree -- or as a butterfly -- then
> >the time cost to access memory goes as O(log Memory), which suggests that
> >the right formula is Cost = Time * Memory * log Memory.
Very much depends on the machine model and on the desiderata... On the other
hand, most of the calculations in the VLSI industry are made in units AT,
where A is area (space) and T is time complexity. There's several good
reasons for it. For example, it is somewhat simpler to prove lower bounds on
AT than on AT*log A (proofs from communication complexity carry naturally
over, cf the book of Kushilevitz and Nisan, "Communication
Complexity"). E.g., any VLSI computing the equality function EQ(x,y) of two
n-bit strings x and y has AT>=n^2.
Helger
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: RSA and Microcontroller
Date: Fri, 27 Aug 1999 11:39:10 GMT
In article <[EMAIL PROTECTED]>,
Ryan Phillips <[EMAIL PROTECTED]> wrote:
> This is just a research project (for now), but is it possible to put
RSA
> Encryption and Decryption into an Intel compatible 8031 or 8051
> microcontroller?
Use a 8032 or 8052 and get 128 extra bytes ram... good idea! Use
DALLAS 8052 chips cuz they are cooler. Plus invest in a math co-
processor for crypto (they are out there) if you want todo anything
realtime. If the 8032/8052 is just a core for a ASIC get a co-pro
inlined in the ASIC if possible.
> Also, if it is possible is there any sourcecode freely available?
Haven't a clue. sorry.
Tom
--
PGP 6.5.1 Key
http://mypage.goplay.com/tomstdenis/key.pgp
PGP 2.6.2 Key
http://mypage.goplay.com/tomstdenis/key_rsa.pgp
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: btw
Date: Fri, 27 Aug 1999 11:41:39 GMT
In article <7q3i07$gnf$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Keith A Monahan) wrote:
> FYI - it sucks trying to brute force your own password. When I came
up
> with the password, I had no idea its biggest enemy would be me.
Use a 32-bit salt, SHA-1 and a 20 char password (from a-z, A-Z, 0-9 and
symbols, or about 94 chars) and you get a keyspace of 94^20 or
2^131.091 ..... (could use a bigger salt, but you don't really need it)
Tom
--
PGP 6.5.1 Key
http://mypage.goplay.com/tomstdenis/key.pgp
PGP 2.6.2 Key
http://mypage.goplay.com/tomstdenis/key_rsa.pgp
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: CryptoAPI
Date: Fri, 27 Aug 1999 11:37:03 GMT
In article <01beefde$4c0a1560$0164640a@server>,
"Gary Partis" <[EMAIL PROTECTED]> wrote:
> Hi,
>
> Does any one know of any Win32 applications or any OS code which uses
the
> CryptoAPIs in Windows?
>
> For example, on NT, does the local and network login use it's own
code or
> does it make calls the the CryptoAPI DLL?
Want my opinion? Don't use MS crypto libs, I doubt they ever got
beyond 40-bit keys in anything... Plus from what I see they only have
RC4 anyways.... really simple cipher do you need a crypto lib?
Look up cryptlib for a good library, or if you just want RC4 code it
yourself...
Tom
--
PGP 6.5.1 Key
http://mypage.goplay.com/tomstdenis/key.pgp
PGP 2.6.2 Key
http://mypage.goplay.com/tomstdenis/key_rsa.pgp
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (Frank Gifford)
Subject: Re: Key to Ciphertext Ratio's
Date: 27 Aug 1999 07:50:47 -0400
In article <7q4kqj$h1f$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
>Here's a little thought provoker. Assuming we're using a block cipher,
>IDEA for example, and we keep the plaintext constant.
>...
>
>Now, there are 2^64 different ciphertext permutations. Since we are
>assuming that there are only good keys, there are somewhat less than
>that. With these assumptions, is it possible that two or more key's
>encrypt the same plaintext to identicle ciphertext's? Also, in this
>example there are 2^128 different permutations of the key, thus the
>problem is further compounded.
You can apply the pigeon-hole principle:
- Assume your input is (say) all 0's
There are only (*cough*) 2^64 outputs, but you have 2^128 selectors.
Trying to have exactly one output for each key leaves a lot left over.
(2^128 - 2^64) =~ 2^128
So somewhere there will be duplicate outputs. In fact, there should be a lot.
If you assume your block cipher behaves like a random function, there would
be about (2^128 / 2^64) number of each output.
So the answer to the first part is yes, there will be multiple keys which
encrypt a particular plaintext block to the same ciphertext.
But the work gets harder when you want multiple plaintext blocks. You would
find that the probability drops quickly as you add more blocks. I'm not sure
where the cut-off is where you could have two ciphertexts decrypting to two
different and reasonable plaintexts (reasonable by some particular definition).
>3. Can this be exploited? Certainly it could make a brute-force attack
>much easier if one gets lucky.
If anything, it can be exploited by the person encrypting if the messages are
128 bits or shorter, since the attacker has no way to be sure he's found
the right answer.
Part of it also would depend on the final key used in the decryption. Suppose
that 'they' determine that you could have used two possible keys (and they have
two different but seemingly 'valid' plaintexts). One key is just a string of
1's and 0's, the other is the phrase "A stitch in time". They are going to
believe the second key and whatever output it has as opposed to the
random-looking other candidate key.
-Giff
--
Too busy for a .sig
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
