Cryptography-Digest Digest #420, Volume #13 Thu, 4 Jan 01 16:13:00 EST
Contents:
Birthday Paradox (Tom St Denis)
Re: Differential Analysis (Benjamin Goldberg)
Re: Differential Analysis (Benjamin Goldberg)
Re: Differential Analysis (Tom St Denis)
Re: Birthday Paradox (Steve Portly)
Crypt-X. ([EMAIL PROTECTED])
Re: Birthday Paradox (John Myre)
Re: Differential Analysis (John Myre)
Re: Any Ziplip Users Here???? (Paul Rubin)
Re: Simple Sublimibimbimal Exercise (Mok-Kong Shen)
looking for threshold cryptography implementation + source code ("Richard Brosseau")
Re: Differential Analysis (Bryan Olson)
Re: computing RSA keys (Bill Unruh)
Quadratic Residuosity Problem ("Medvedev Michael")
Re: Intel holding back because of security issues! (John Savard)
Re: ---- Which comes first? Posting or the Egg? (Mok-Kong Shen)
Re: Differential Analysis (Simon Johnson)
Re: Quadratic Residuosity Problem (Mok-Kong Shen)
Re: ---- Which comes first? Posting or the Egg? ("Paul Pires")
random seed ([EMAIL PROTECTED])
Multi-precision arithmetic in C (was AES in optimized x86 assembler?) (David Hopwood)
Re: Quadratic Residuosity Problem (Bob Silverman)
Re: Differential Analysis (Tom St Denis)
Re: Differential Analysis ("M.S. Bob")
----------------------------------------------------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Birthday Paradox
Date: Thu, 04 Jan 2001 15:59:24 GMT
We know given a class of 'r' people and 'n' days the birthday paradox
is given by
p = 1 - P(n,r)/n^r
Then why for a hash is it given by
p = sqrt(n)?
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Differential Analysis
Date: Thu, 04 Jan 2001 16:16:03 GMT
Ross Anderson wrote:
>
> >In article <[EMAIL PROTECTED]>,
> > Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> >> Could anyone point me to an _online_ resource which describes
> >> exactly how to do differential analysis?
>
> In article <93006j$kpe$[EMAIL PROTECTED]>,
> Simon Johnson <[EMAIL PROTECTED]> writes:
> >
> >Yeah, i'd like to see a consise description to. I wonder wether one
> >of the experts would like to create such a document
>
> I append the relevant page from my forthcoming book on security
> engineering <http://www.cl.cam.ac.uk/~rja14/book.html>.
Umm, nice, I suppose, but the only thing online is the table of contents
and the forward. Also, the page you quoted in your post only contained
a general description of differential analysis, not a tutorial and
step-by-step walk through. Such things are available online for
Vigenere an monoalphabetic substitution, but not for differential
cryptanalysis.
> If you want more detail (and exercises to work on), I'd suggest Doug
> Stinson's textbook, which is at
> <http://www.cacr.math.uwaterloo.ca/~dstinson/CTAP.html>, for
> differential cryptanalysis (see chapter 3). I don't know of any good
> teaching material on linear attacks, I'm afraid
<sarcasm>Hmm, yes, an online table of contents provides an *enormous*
amount of information on how to do differential cryptanalysis</sarcasm>
[snip rough description of various attacks]
I asked for something which "describes exactly how to do differential
analysis." Which part of "exactly" don't you understand?
--
Power interrupts. Uninterruptable power interrupts absolutely.
[Stolen from Vincent Seifert's web page]
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Differential Analysis
Date: Thu, 04 Jan 2001 16:44:33 GMT
Tom St Denis wrote:
>
> In article <[EMAIL PROTECTED]>,
> Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> > Could anyone point me to an _online_ resource which describes
> > exactly how to do differential analysis? Most of the stuff I've
> > found is much to vague to go from their description to something
> > resembling an attack.
>
> Differential attacks work like this. You have a finite function F(x),
> you know that a difference i.e F(x) - F(x - a) = b will occur with
> probability p (p <> 1), thus there are pairs of inputs (x, x-a) that
> will cause the output difference 'b'.
Ok, I understand this part, sorta. But how do I find a, b, and p?
Also, why do you use integer subtraction, rather than XOR? Wouldn't XOR
make more sense for most ciphers? That would make it:
F(x) ^ F(x^a) = b
With some probability p.
> In your attack you sends random pairs of inputs (that differ by 'a')
> and look for an output difference of 'b'. If it occurs then your
> inputs may have been right.
Huh? I don't get it. You mean that if ENC(x) ^ ENC(x^a) = b, then the
key byte is b?
> Given most F(x) will be used as F(x + k) (i.e a key is added) it's a
> simple matter of linear algebra to find the right key.
>
> For example if for the inputs (1,2,3) and a ionput difference of 2, an
> output difference of 4 is likely. Then if you send (5,7) as an input
> and find '2' as the difference the key may have been -4,-3 or -2 (i.e
> 5 - 4 = 1, 5 - 3 = 2....).
>
> Hope this helps.
A little, but not as much as I'd like it to.
How about this: here's what I want to analyse:
function encr( uint8 txt[2], uint8 k[rounds] ) {
for i in 0 to rounds/2-1 {
txt[0] ^= AES_sbox[ txt[1] ^ *k++ ];
txt[1] ^= AES_sbox[ txt[0] ^ *k++ ];
}
}
How do I go about finding differences and probabilities, and how does
that let me get k? Of equal importance, what do I have to set rounds to
to thwart differential analysis?
--
Power interrupts. Uninterruptable power interrupts absolutely.
[Stolen from Vincent Seifert's web page]
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Differential Analysis
Date: Thu, 04 Jan 2001 16:44:43 GMT
In article <[EMAIL PROTECTED]>,
Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> Ross Anderson wrote:
> >
> > >In article <[EMAIL PROTECTED]>,
> > > Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> > >> Could anyone point me to an _online_ resource which describes
> > >> exactly how to do differential analysis?
> >
> > In article <93006j$kpe$[EMAIL PROTECTED]>,
> > Simon Johnson <[EMAIL PROTECTED]> writes:
> > >
> > >Yeah, i'd like to see a consise description to. I wonder wether one
> > >of the experts would like to create such a document
> >
> > I append the relevant page from my forthcoming book on security
> > engineering <http://www.cl.cam.ac.uk/~rja14/book.html>.
>
> Umm, nice, I suppose, but the only thing online is the table of
contents
> and the forward. Also, the page you quoted in your post only
contained
> a general description of differential analysis, not a tutorial and
> step-by-step walk through. Such things are available online for
> Vigenere an monoalphabetic substitution, but not for differential
> cryptanalysis.
>
> > If you want more detail (and exercises to work on), I'd suggest Doug
> > Stinson's textbook, which is at
> > <http://www.cacr.math.uwaterloo.ca/~dstinson/CTAP.html>, for
> > differential cryptanalysis (see chapter 3). I don't know of any good
> > teaching material on linear attacks, I'm afraid
>
> <sarcasm>Hmm, yes, an online table of contents provides an *enormous*
> amount of information on how to do differential
cryptanalysis</sarcasm>
>
> [snip rough description of various attacks]
>
> I asked for something which "describes exactly how to do differential
> analysis." Which part of "exactly" don't you understand?
There is a method of applying it but the general rule of thumb is that
each cipher is different so the best method of attack is different.
Read Eli Bihams online papers (or his book if you can find it) for more
information on differential cryptanlysis (he co-invented it publicly
with Adi Shamir)
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Steve Portly <[EMAIL PROTECTED]>
Subject: Re: Birthday Paradox
Date: Thu, 04 Jan 2001 12:37:21 -0500
Tom St Denis wrote:
> We know given a class of 'r' people and 'n' days the birthday paradox
> is given by
>
> p = 1 - P(n,r)/n^r
>
> Then why for a hash is it given by
>
> p = sqrt(n)?
>
> Tom
>
> Sent via Deja.com
> http://www.deja.com/
Probably due to the popular belief that crack attempts are carried out
against individuals possessing a single key.
------------------------------
From: [EMAIL PROTECTED]
Subject: Crypt-X.
Date: Thu, 04 Jan 2001 17:42:12 GMT
There is an Australian software package called 'Crypt-X', for
testing both stream ciphers and block ciphers.
( http://www.isrc.qut.edu.au/cryptx/ )
Does anyone know more about this, and when testing a RNG, does
this offer more than 'Diehard' ?
Thanks,
Rudy.
Sent via Deja.com
http://www.deja.com/
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Birthday Paradox
Date: Thu, 04 Jan 2001 11:11:14 -0700
Tom St Denis wrote:
>
> We know given a class of 'r' people and 'n' days the birthday paradox
> is given by
>
> p = 1 - P(n,r)/n^r
Right, where 'p' is the "probability of a collision".
>
> Then why for a hash is it given by
>
> p = sqrt(n)?
It isn't: p is a probability, not a count.
The usual statement is that when r = sqrt(n),
then p = 0.5, approximately.
JM
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Differential Analysis
Date: Thu, 04 Jan 2001 11:17:11 -0700
Have you read Biham's paper? If not, you should.
If so, and you don't understand it, then I don't
think any "tutorial" is going to help; it would
be better to get pointers when you get stuck
reading the paper.
JM
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Crossposted-To: alt.privacy.anon-server,alt.privacy
Subject: Re: Any Ziplip Users Here????
Date: 04 Jan 2001 10:30:03 -0800
"Norm G." <[EMAIL PROTECTED]> writes:
> Team Hush is battling the fact that if an account is subpoenaed that they
> only have to hand over the encrypted data, their TOS statement says this as
> well, but they are being told that THEY SHALL hand over the data DE-CRYPTED.
> TeamHush has stated that their system has no back door, and even they cannot
> decrypt any encrypted message sent between users. They are being instructed
> that they will have to correct that so that any message can be decrypted.
> They have said "NO WAY IN HELL" and who knows where this is going to lead.
>
> It is a private legal matter at this time, but it looks like it could get
> really nasty.
This story does not check out. It appears to be fiction.
> As for me, I have been using the C source code for the Static Huffman
> encoding that is used in PkZip, and I export the CRC rebuild key, and keep
> that seperate from my secure data. My data cannot be recovered without the
> CRC key. Old tech, but very secure. You can purchase the source code from
> the Pkzip web site cheap, very fun to play with.
You're better off using conventional encryption. There's no reason to
think your scheme is secure.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Simple Sublimibimbimal Exercise
Date: Thu, 04 Jan 2001 19:35:36 +0100
wtshaw wrote:
>
> Pull up www.radiofreetexas.com/wts/pix/text.GIF.
>
> Save it and see if you can find the process to see the contents. I left a
> few clues to egg you on, the confined spaces is some letters, but they
> could be eliminated.
>
> Whereever there are black areas in a graphic, the same technique is good
> for hiding content and most probably already have what you need to read
> it, the Gates Secret Decoder Ring, otherwise known as MS Photo Editor.
I am unable to discern the hidden content you claimed but I
am also not sure whether your scheme passes as steganography,
since it seems to be simply a sequence of symbols (the white
ones) in a particular alphabet which can also be an encryption
in the normal sense. Another quesiton: Could your scheme be
sensitive to the quality of the monitor that displays the
picture?
M. K. Shen
------------------------------
From: "Richard Brosseau" <[EMAIL PROTECTED]>
Subject: looking for threshold cryptography implementation + source code
Date: Thu, 04 Jan 2001 14:02:06 GMT
If anyone can forward me source code that implements threshold crypto I'd
appreciate it.
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Differential Analysis
Date: Thu, 04 Jan 2001 19:29:08 GMT
Benjamin Goldberg wrote:
> Ross Anderson wrote:
[...]
> > I append the relevant page from my forthcoming book on security
> > engineering <http://www.cl.cam.ac.uk/~rja14/book.html>.
>
> Umm, nice, I suppose, but the only thing online is the
> table of contents and the forward. Also, the page you quoted
> in your post only contained a general description of differential
> analysis, not a tutorial and step-by-step walk through.
[...]
> <sarcasm>Hmm, yes, an online table of contents provides an
> *enormous* amount of information on how to do differential
> cryptanalysis</sarcasm>
<sarcasm> Consider the possibility that someone attacking your
cipher may go to such extreme measures as reading papers.
</sarcasm>
One good on-line reference to mostly off-line sources is Bruce
Schneier's self-study course in block cipher cryptanalysis.
See:
http://www.counterpane.com/self-study.html
--Bryan
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: computing RSA keys
Date: 4 Jan 2001 19:56:55 GMT
In <92u04j$ju$[EMAIL PROTECTED]> [EMAIL PROTECTED] writes:
>If e is 3, I'd think one could simply add the public modulo (pq) until
>you find a total which can be cube-rooted evenly. I suppose there might
Uh, you have to add about (pq)^2 of them, assuming that the number which
you are cubing is of the same size as pq ( an absolute requirement).
This is even more expensive a break method than is factoring!
------------------------------
From: "Medvedev Michael" <[EMAIL PROTECTED]>
Subject: Quadratic Residuosity Problem
Date: Thu, 4 Jan 2001 18:38:49 +0200
Hi everybody!
I would like to find out, is it possible to decrease redundancy in Rabin
public - key encryption?
If somebody is new in this field, I'll try to expain the problem:
If Allice wants to encode the message X, she computes Y = X^2 mod n (n = p *
q, where p, q - are prime numbers) and sends Y to Bob. Bob knows n, p, q. He
tries to find the square roots of Y. As n is a product of two primes, he
evaluates four square roots: x1, x2, x3, x4. But how to recognize, what xi
was encoded? As a rule, if Allice wants to encrypt message M, she duplicates
the message and encrypts X = MM. So Bob must finds out, which xi is
duplicated.
Is it possible not to duplicate M, but to add 1 bit or 2 bits or some bits
of information to the message (the MINIMUM number of information)?
If somebody knows web sites about quadratic residuosity problem, or Rabin -
Public key encryption, please, give me them.
Thank you.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To: comp.sys.laptops
Subject: Re: Intel holding back because of security issues!
Date: Thu, 04 Jan 2001 19:48:29 GMT
On 03 Jan 2001 23:54:17 -0800, Paul Rubin <[EMAIL PROTECTED]>
wrote, in part:
>[EMAIL PROTECTED] writes:
>> To make a long story short, I'm a senior in college and recently a
>> sweet consulting job after graduation. My friend recently in the job
>> hunting process went over to Sacramento to interview with Intel. Among
>> things that he was told was this gem: "We can't release the Itanium (
>> IA-64 ) processor because it can crack 128-bit SSL encryption in less
>> than a day." LOL. If that's true, that's some sick CPU.
>> -Boucher
>Funniest thing I've heard all day... (crosspost for amusement of
>sci.crypt).
I think there was a typo, though.
If that _were_ true of it, even for a large multi-processor
configuration, that would be some _slick_ CPU.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: ---- Which comes first? Posting or the Egg?
Date: Thu, 04 Jan 2001 21:15:45 +0100
Steve Portly wrote:
>
> Greggy wrote:
[snip]
> something like the old four in one cipher on their own? Unless you have
> done a patent search chances are good that your cipher has been thought of
> before and posting it in a public forum may be disclosing someone elses
> trade secrets.
Is it a question of moral that you meant?
M. K. Shen
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: Differential Analysis
Date: Thu, 04 Jan 2001 20:05:09 GMT
In article <932itm$qj0$[EMAIL PROTECTED]>,
Bryan Olson <[EMAIL PROTECTED]> wrote:
> Benjamin Goldberg wrote:
> > Ross Anderson wrote:
> [...]
> > > I append the relevant page from my forthcoming book on security
> > > engineering <http://www.cl.cam.ac.uk/~rja14/book.html>.
> >
> > Umm, nice, I suppose, but the only thing online is the
> > table of contents and the forward. Also, the page you quoted
> > in your post only contained a general description of differential
> > analysis, not a tutorial and step-by-step walk through.
>
> [...]
> > <sarcasm>Hmm, yes, an online table of contents provides an
> > *enormous* amount of information on how to do differential
> > cryptanalysis</sarcasm>
>
> <sarcasm> Consider the possibility that someone attacking your
> cipher may go to such extreme measures as reading papers.
> </sarcasm>
>
> One good on-line reference to mostly off-line sources is Bruce
> Schneier's self-study course in block cipher cryptanalysis.
> See:
>
> http://www.counterpane.com/self-study.html
>
> --Bryan
>
> Sent via Deja.com
> http://www.deja.com/
>
I've looked at this, and its only any good if you know how to do/how to
work the attacks :)
Simon.
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Quadratic Residuosity Problem
Date: Thu, 04 Jan 2001 21:29:13 +0100
Medvedev Michael wrote:
>
> I would like to find out, is it possible to decrease redundancy in Rabin
> public - key encryption?
>
> If somebody is new in this field, I'll try to expain the problem:
>
> If Allice wants to encode the message X, she computes Y = X^2 mod n (n = p *
> q, where p, q - are prime numbers) and sends Y to Bob. Bob knows n, p, q. He
> tries to find the square roots of Y. As n is a product of two primes, he
> evaluates four square roots: x1, x2, x3, x4. But how to recognize, what xi
> was encoded? As a rule, if Allice wants to encrypt message M, she duplicates
> the message and encrypts X = MM. So Bob must finds out, which xi is
> duplicated.
>
> Is it possible not to duplicate M, but to add 1 bit or 2 bits or some bits
> of information to the message (the MINIMUM number of information)?
The four values have an order as binary numbers. If one
appends 2 bits, that would resolve the ambiguity. Or
am I missing something?
M. K. Shen
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: ---- Which comes first? Posting or the Egg?
Date: Thu, 4 Jan 2001 12:37:12 -0800
Steve Portly <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> Greggy wrote:
>
> > In article <91uvb8$m3a$[EMAIL PROTECTED]>,
> > Greggy <[EMAIL PROTECTED]> wrote:
<Snip>
> Well if you posted the source code for a strong algorithm to this newsgroup
> it would probably get buried quite quickly. There are enough people
> selling commercial products here that would love to take on any
> competition. Besides a lot of the best ciphers were written years ago.
> What programmer if asked to write a strong cipher would not think up
> something like the old four in one cipher on their own? Unless you have
> done a patent search chances are good that your cipher has been thought of
> before and posting it in a public forum may be disclosing someone elses
> trade secrets.
I hate to nit pick here but.....
If it is patented it is public. You cannot further disclose something that is
by definition, "disclosed".
Trade secrets only control those who have a contractual obligation not
to disclose or for information that was obtained illegaly. If you obtain the
"secret information" throught some independent process such as re-inventing
it, then there is no justifiable leagal action someone can take against you for
disclosing it any way you see fit. You should avoid coincedences though.
If you are under non disclosure with someone, serious thought should be
given to disclosing their information regardless of any
independent provenance you might have for it.
They can bluster and puff "RSA-PKP" ala RC-4 But there isn't a legal basis for
pestering you in any way.
Not a lawyer, disclaimer ad-nauseum.
Paul
====== Posted via Newsfeeds.Com, Uncensored Usenet News ======
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
======= Over 80,000 Newsgroups = 16 Different Servers! ======
------------------------------
From: [EMAIL PROTECTED]
Subject: random seed
Date: Thu, 04 Jan 2001 20:41:37 GMT
Hi, any ones knows how to generate a random seed to use
with ElGamal algorithm.
I'm writting a program that encrypts data using this
algorithm under NT 4.0. But I have no idea how to
generate a real random number to seed the algorithm.
thanks
Jorge
Sent via Deja.com
http://www.deja.com/
------------------------------
Date: Thu, 04 Jan 2001 20:44:03 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Multi-precision arithmetic in C (was AES in optimized x86 assembler?)
=====BEGIN PGP SIGNED MESSAGE=====
Thomas Pornin wrote:
> According to Paul Rubin <[EMAIL PROTECTED]>:
> > because there's no portable way to do multi-precision arithmetic in C
> > that uses the full capability of the PC architecture (specifically,
> > multiplication instructions that give double-width products).
>
> Actually there is one : unsigned long long. This type is at least 64-bit
> wide (and usually is that wide in PC common compilers) and is standard
> (since ISO 9899:1999, aka C99).
unsigned long long still does not allow direct 32 x 32 -> 64 or
64 x 64 -> 128 bit multiplications, either of which will be more efficient
than 64 x 64 -> 64.
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOlOuVTkCAxeYt5gVAQEsiQgAzknNINSshPJb2VuMdjwIq3R7f/kh0TTC
Mwr5pbBepD90XfCvEZyUANLbUG4OkW1MoSVQz3zijw7D+/r69G0wcVsj8mr/WGF6
0m4d76oGOIvboCHe6im1l+NjM+owVx8nB6Rb8bYR6k8+K2CJ7JS9Mp/P1dmFatDl
2GV7KhlTBqekr7UoK5z/nUmC4tIE3QFt6EKE3pTF39fJc9x1NYRZs3dgosbQ/s+B
sZKm3XZVNI7ltdps1B5T5i6FfvvBHM5rp41fzrb54BOOF7RI2sA35w1JQtztGYgq
jgS71e2vPXizvFotJFGTkhEbUyuczbVws/5IM6QzEp93TBapa+54Jw==
=bmRe
=====END PGP SIGNATURE=====
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Quadratic Residuosity Problem
Date: Thu, 04 Jan 2001 20:45:33 GMT
In article <932l88$mls$[EMAIL PROTECTED]>,
"Medvedev Michael" <[EMAIL PROTECTED]> wrote:
> Hi everybody!
>
> I would like to find out, is it possible to decrease redundancy in
Rabin
> public - key encryption?
<snip> Let one of the primes be 3 mod 8, the other -1 mod 8.
Look at the message mod 12....
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Differential Analysis
Date: Thu, 04 Jan 2001 20:48:32 GMT
In article <[EMAIL PROTECTED]>,
Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> Tom St Denis wrote:
> >
> > In article <[EMAIL PROTECTED]>,
> > Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> > > Could anyone point me to an _online_ resource which describes
> > > exactly how to do differential analysis? Most of the stuff I've
> > > found is much to vague to go from their description to something
> > > resembling an attack.
> >
> > Differential attacks work like this. You have a finite function F
(x),
> > you know that a difference i.e F(x) - F(x - a) = b will occur with
> > probability p (p <> 1), thus there are pairs of inputs (x, x-a) that
> > will cause the output difference 'b'.
>
> Ok, I understand this part, sorta. But how do I find a, b, and p?
> Also, why do you use integer subtraction, rather than XOR? Wouldn't
XOR
> make more sense for most ciphers? That would make it:
> F(x) ^ F(x^a) = b
> With some probability p.
Xor is addition/subtraction in GF(2) so the math is the same. And you
find 'a', 'b' by looking for them.
> > In your attack you sends random pairs of inputs (that differ by 'a')
> > and look for an output difference of 'b'. If it occurs then your
> > inputs may have been right.
>
> Huh? I don't get it. You mean that if ENC(x) ^ ENC(x^a) = b, then
the
> key byte is b?
No if you send 'x' in and 'y' was what is suppose to cause the
difference then x+k=y or x-y=k :-)
> > Given most F(x) will be used as F(x + k) (i.e a key is added) it's a
> > simple matter of linear algebra to find the right key.
> >
> > For example if for the inputs (1,2,3) and a ionput difference of 2,
an
> > output difference of 4 is likely. Then if you send (5,7) as an
input
> > and find '2' as the difference the key may have been -4,-3 or -2
(i.e
> > 5 - 4 = 1, 5 - 3 = 2....).
> >
> > Hope this helps.
>
> A little, but not as much as I'd like it to.
>
> How about this: here's what I want to analyse:
>
> function encr( uint8 txt[2], uint8 k[rounds] ) {
> for i in 0 to rounds/2-1 {
> txt[0] ^= AES_sbox[ txt[1] ^ *k++ ];
> txt[1] ^= AES_sbox[ txt[0] ^ *k++ ];
> }
> }
>
> How do I go about finding differences and probabilities, and how does
> that let me get k? Of equal importance, what do I have to set rounds
to
> to thwart differential analysis?
Well look at the xor-pair table of the sbox and see if any high prob
difference can propagate easily in your function. (Hint your above
function is a simple feistel so just look for high probability output
differences that have inputs of high prob as well (i.e if you chain the
differences they are always high probability)).
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "M.S. Bob" <[EMAIL PROTECTED]>
Subject: Re: Differential Analysis
Date: Thu, 04 Jan 2001 21:02:08 +0000
Benjamin Goldberg wrote:
>
> > >In article <[EMAIL PROTECTED]>,
> > > Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> > >> Could anyone point me to an _online_ resource which describes
> > >> exactly how to do differential analysis?
>
> <sarcasm>Hmm, yes, an online table of contents provides an *enormous*
> amount of information on how to do differential cryptanalysis</sarcasm>
>
> I asked for something which "describes exactly how to do differential
> analysis." Which part of "exactly" don't you understand?
http://www.amazon.com/exec/obidos/ASIN/0387979301
Differential Cryptanalysis of the Data Encryption Standard
by Eli Biham, Adi Shamir (Contributor)
http://www.amazon.com/exec/obidos/ASIN/0849385210
Cryptography : Theory and Practice
by Douglas R. Stinson
http://www.amazon.com/exec/obidos/ASIN/3540650695
Advances in Cryptology, 1981-1997: Electronic Proceedings and
Index of the Crypto and Eurocrypt Conferences 1981-1997
by Kevin S. McCurley (Editor), Claus Dieter Ziegler (Editor)
http://citeseer.nj.nec.com/biham93differential.html
http://www.cs.technion.ac.il/~biham/publications.html
Differential Cryptanalysis of the Full 16-round DES
by Eli Biham, Adi Shamir
http://citeseer.nj.nec.com/biham91differential.html
http://www.cs.technion.ac.il/~biham/publications.html
Differential cryptanalysis of DES-like cryptosystems
by Eli Biham, Adi Shamir
http://citeseer.nj.nec.com/86579.html
http://www.cs.technion.ac.il/~biham/publications.html
Differential cryptanalysis of Feal and N-Hash
by Eli Biham, Adi Shamir
These resources describe differential cryptanalysis in detail. Not all
of them are free, but those ones in particular are the most recommended
resources. The first book expands on Biham and Shamir's papers, which
give you more details but is out unfortunately out-of-print, try
inter-library loans (might even be a free service). Stinson's book is a
good textbook to cryptography, period. The CD is essential to have if
you are serious about cryptography.
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
