Cryptography-Digest Digest #704, Volume #9 Sat, 12 Jun 99 16:13:03 EDT
Contents:
Caotic function ("ivana")
Re: Slide Attack on Scott19u.zip (David Wagner)
Re: Slide Attack on Scott19u.zip (David Wagner)
Re: Slide Attack on Scott19u.zip (fungus)
Re: Slide Attack on Scott19u.zip (fungus)
Re: OTP is it really ugly to use or not? (Erm Yankoil)
Re: Slide Attack on Scott19u.zip (David Wagner)
Re: Slide Attack on Scott19u.zip (David Wagner)
Re: OTP is it really ugly to use or not? (Jim Gillogly)
RSA example with small numbers (Gergo Barany)
Re: Slide Attack on Scott19u.zip (Horst Ossifrage)
RSA msg length... ("Particle")
Re: Does scott19u.zip make full use of it's large key size ? (SCOTT19U.ZIP_GUY)
----------------------------------------------------------------------------
From: "ivana" <[EMAIL PROTECTED]>
Subject: Caotic function
Date: Sat, 12 Jun 1999 18:38:38 +0200
I'm looking for documentation about caotic funcions. I 'm a student and
can't begin my work without it. Anyone can help me with some links ?
thanks
Alex
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Slide Attack on Scott19u.zip
Date: 12 Jun 1999 10:29:01 -0700
In article <7jtlms$ppm$[EMAIL PROTECTED]>,
SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote:
> In article <7jromi$7h3$[EMAIL PROTECTED]>,
>[EMAIL PROTECTED] (David Wagner) wrote:
> >I conclude that Scott's cipher seems to be thoroughly broken.
>
> Yes you would conclude that it could be broken with a hand
> wave and yet I think your full of shit. You make that statement up
> here at the top of the paper and then go on to say you have never
> looked at the code or even bothered to test it out. I think that you
> have tested it and could not break it with your TOY attack. At least
> have the decency to run an attack on it. Instead of pulling statements
> that it is broken out of your ass with out even trying to test it.
Fair enough. Ok, to be more precise, I should have said
``From what I've seen so far, I am led to the conclusion that
Scott's cipher appears to be broken.''
Sorry about that. Is that better?
It's certainly not conclusive, but it's enough for me to to conclude
that it's not worth any more of my time, unless some new information
becomes available. (Hint: You can be the one to provide that new
information, by posting a concise analysis of the attack and why you
think it can or cannot be made to work.)
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Slide Attack on Scott19u.zip
Date: 12 Jun 1999 10:48:22 -0700
In article <7jtsge$ba0$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
> I would like to break my simple
> cipher. It has no round dependant keys which is why I think a slide
> attack will work.
>
> It's at http://people.goplay.com/tomstdenis/simple.c
I took a quick look, and it looks as though the initial and final xor
with the "permutation" will make the slide attack somewhat more difficult.
Also, the 128-bit block width means that the known plaintext attacks will
need 2^64 texts or so.
Another complication is the key-dependent S-boxes and the fact that each
round modifies all of the block (unless Feistel ciphers, which only modify
half of the block; this makes slide attacks easier).
Therefore, this might be a bit of a difficult cipher for your first attempt
at building a slide attack, because there are a lot of details to juggle.
It might be easier going if you pick a different cipher without some of the
complicating factors.
But if you do want to play with this particular cipher, I suggest that you
omit the "permutation" xors, at least at first -- I think it will make your
life much easier.
Just for reference, the best slide attack I see on the cipher without the
"permutation" xors takes something like 512 chosen plaintexts. In comparison,
it's not at all clear to me (off the top of my head) how to build an attack
on the full cipher: I think you can do it with 2^66 chosen plaintexts or so,
but I'm not entirely sure.
P.S. Note that if table[0] = 0, then if (a,b,..,h) = (0,0,..,0) after the
initial xor, then (a,b,..,h) = (0,0,..,0) after all the rounds (before the
final xor). A similar property holds if table[0] = 128 or if table[128] = 0
or 128. Also, in the 64-bit cipher, if a=c and b=d after the initial xor,
then these equations still hold after all the rounds (before the final xor).
(You should check all of those, in case I made a mistake.)
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: Slide Attack on Scott19u.zip
Date: Sat, 12 Jun 1999 20:39:19 +0200
Horst Ossifrage wrote:
>
> SCOTT19U.ZIP_GUY wrote:
> >
> > > During the next 3 days, a Slide Attack will be discussed
> > > against the Scott19u.zip cryptographic algorism. The
> > > attack was introduced at the FSE-6 Conference in March,
> > > 1999, Rome.
> >
> > Keep me posted...
>
> read Mr. Wagner's paper about the Slide Attack.
> It is an easy way to attack some ciphers with simple round
> functions. While Mr. Wagner says that attack breaks Scott19u.zip
> I will study it for two more days to confirm or refute his
> claim.
Oh, no....
Does this mean we now have to start all over again with scott20?
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: Slide Attack on Scott19u.zip
Date: Sat, 12 Jun 1999 20:42:24 +0200
[EMAIL PROTECTED] wrote:
>
> If they clean it up and explain how they mounted the
> attack (what style) I think we can all rest calmly tonight :)
>
Dream on.
DS is no doubt planning scott20 as we speak...he's like (worse
than!) Freddy Kruger, he just won't give it a rest.
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: [EMAIL PROTECTED] (Erm Yankoil)
Subject: Re: OTP is it really ugly to use or not?
Date: Sat, 12 Jun 1999 18:20:51 GMT
Cyba Nonymous <[EMAIL PROTECTED]> wrote:
>I read in this group that the security of an OTP depends on the
>pad being random. Really random and not just pseudo-random.
I think it's more accurate to say that the absolute validity of the
mathematical proof that the OTP is secure depends on the true randomness of
the pad. It's perfectly possible to use a less than perfect random number
generator for your one time pad and still have message security that can
and will never be compromised.
--
"Erm Yankoil" better known as [EMAIL PROTECTED]
012 3456789 <- Use this key to decode my email address.
Fun & Free - http://www.5X5poker.com/
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Slide Attack on Scott19u.zip
Date: 12 Jun 1999 11:05:12 -0700
In article <[EMAIL PROTECTED]>, Horst Ossifrage <[EMAIL PROTECTED]> wrote:
> While Mr. Wagner says that attack breaks Scott19u.zip
> I will study it for two more days to confirm or refute his
> claim. In particular, I am studying closely how his paper
> uses KEY BITS in the first round and the last round to confirm that
> the Slid Pair is a correct one. In the DES example in the paper
> the subkeys in those two rounds have SHARED KEY BITS regardless
> of the data. In Scott19u.zip usually, those 2 rounds do not use
> the same S-Box entry, so they do not indicate any common Key bits.
> Without that common clue, Scott19u.zip is different than DES.
You might be right; maybe the attack I was thinking of doesn't
work. You certainly understand scott19u far better than I.
Why don't I explain in more detail the technique I was thinking
of to bypass the fact that scott19u uses a different S-box entry
in the first and last rounds? You can tell me whether you
think it will work, since you understand the cipher.
The primary equation is C[i] = S{(P[i] + P[i+1]) xor C[i-1]},
or something like that. I was thinking of looking at a pair of
plaintexts P[] and P'[] that satisfy
(*) P'[i] = P[i+1].
If I understand correctly, this should imply that
C'[i] = S{(P'[i] + P'[i+1]) xor C'[i-1]}
= S{(P[i+1] + P[i+2]) xor C[i]} = C[i+1],
if you let C'[] represent the encryption of P'[] by a round.
In other words,
(**) C'[i] = C[i+1].
Repeating this for multiple rounds, we see that (**) for round
j => (*) for round j+1, so you should get a slid pair, when the
(*) is satisfied by the plaintexts (except possibly for 19 bits
at the boundary, but if you just try enough pairs you should get
that to match too by dumb luck, I think). Slid pairs can be
recognized by the fact that the ciphertext satisfies (**) -- thus,
the two ciphertexts you get agree in all but about 19 bits (if
you rotate one by 19 bits).
Ok, that was the approach I had in mind. Comments?
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Slide Attack on Scott19u.zip
Date: 12 Jun 1999 11:21:50 -0700
In article <[EMAIL PROTECTED]>, Horst Ossifrage <[EMAIL PROTECTED]> wrote:
> In the DES example in the paper
> the subkeys in those two rounds have SHARED KEY BITS regardless
> of the data. In Scott19u.zip usually, those 2 rounds do not use
> the same S-Box entry, so they do not indicate any common Key bits.
Ahh, I thought of a maybe-better way to explain how I was thinking to
bypass this difficulty.
Consider a variant of Treyfer where one eliminates the key[] array and
uses a key-dependent S-box. (Treyfer is described in the slide paper.)
We can think of this as a cipher with 32 rounds, with 8 S-box lookups
per round. Or, we can think of this as a cipher with 32*8 = 256
"mini-rounds", with one S-box lookup per mini-round. I suggest to
view it as the latter. Note that there is no round dependence in the
mini-rounds (for the variant we're looking at). Thus, the cipher is
for (j=0; j<256; j++)
text[(j+1)&8] = (text[(j+1)&8] + Sbox[text[j&8]]) <<< 1;
I claim that there is a slide attack that needs just 256 chosen plaintexts
or so. (Do you see it?) The same idea seems to apply to scott19u.
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: OTP is it really ugly to use or not?
Date: Sat, 12 Jun 1999 11:34:17 -0700
Cyba Nonymous wrote:
> I read in this group that the security of an OTP depends on the
> pad being random. Really random and not just pseudo-random. OK so
> let's say that I buy that for the moment.
Your questions merge two concepts: the absolute provable security
of the theoretical one-time pad, versus practical security for a
particular threat model. For the first case, you do indeed need
actual physically random bits used only once; there have been a number
of long-running threads in this newsgroup over the years about whether
this is in fact achievable, and I'll gloss over them entirely. For
the second case, you need to identify your threat model: how
interesting are your secrets, who is the enemy, and to what lengths
are they willing to go to compromise your security?
> I can see how OTP security works because any message can be
> decoded into every possible message of its length using some
> "key". ...
> Ok that brings me to my first question which is.... even if the pad
> is not random it still seems to me that the message will decode
> into just as many messages with just as many keys? Yes? No?
No, not necessarily. It depends on how the pad is non-random. In
the degenerate case the non-random pad could be a short repeating
segment; for a given plaintext, many messages can't be obtained with
such a key. The pad could even be random, but over a different range
from the message being encrypted, which again eliminates many
possible plaintext messages.
> I'll assume that the answer is yes and that there is some mystery
> math that can determine hey this was encrypted with a key that
> was not random and therefore there must be only one message
> and this is it! If the answer to that is yes then I don't believe it.
You don't have to. Reality is what remains even when you've
stopped believing in it. If you've gone non-random, then
the precise nature of the non-randomness will eliminate some
proportion of the possible messages to which the ciphertext can
decrypt. If it's non-random enough, the number of possible
plaintext messages will shrink to one.
> And, if it is true (which is possible because I am a dummy) then
> why can't I exploit that and encrypt a (fake) message with a non random
> key to get a stream of ciphered text and then derive another key that
> gives me another message (the real one)? Now the mystery
> math will give the cracker the "wrong" message..right? I could
> go on and on but I think you experts will see the point I am trying to
> make and point out the error of my thinking.
You can produce a ciphertext and any number of keys that will
decrypt that ciphertext to the same number of plaintexts. You
would need to do it in advance, and deliver the right key to
your correspondent. That might be useful if you're trying to
establish plausible deniability, but not for straight communication,
since if you knew the message in advance you could use the secure
out-of-band mechanism you're using for the key to send the message
itself. However, if you're keeping child porn on your computer, you
could have the "emergency key" that decrypts it to digitized stills
from "Barry McKenzie Holds His Own" on a separate disk for the
edification of Judge Freeh and his merry band. But I wouldn't
recommend it -- it'll be a tricky sell for your public defender.
> The other thing that pops into my mind is random versus repeating.
>
> I guess I can see how a repeating key would be a problem. But , are all
> random keys non-repeating? Are all repeating keys non-random?
> If I have a pnr that repeats after a million numbers but I only use
> the first 100 thousand is that not ok?
All random keys are non-repeating, and all repeating keys are
non-random. If your 100K message is encrypted with all random
bits and you never re-use those bits for any purpose, then it
doesn't matter that they were part of a pad that repeated after
a million bits, since the rest of those bits aren't to be used.
> But, let's say I have a CD full of real random numbers for now and
> a program that uses a math formula and a codeword to compile a
> temporary pad for a particular message from that CD full of
> random numbers. Is this not secure as long as I never use the same
> codeword twice and the program will never generate the same pad
> for another codeword? Also, can't I now send that codeword in the
If your codeword says "Start at this point in the CD" and you
never touch any of the bits that were used in any other message,
no problem. If the bits on the CD are re-used with any other
codeword, then you have a problem, and the nature of the re-use
determines the extent of your problem.
> clear? What's the advantage you say over just using the CD full of
> randon numbers in the first place? Well, its because using this
> method from one CD of real randon numbers you can generate an
> infinite number of pads? Yes? No?
No. If you want perfect security, you can't re-use the bits on
that CD for anything else, ever, which means you get a finite
number of messages from the CD. Depending on the system and
formulas you're using, and for your particular threat model, it
may be good enough for practical security. It may also be that
another simpler system of symmetric-key cryptography that doesn't
involve exchanging a physical CD would also be good enough for
your particular threat model. As soon as you've lapsed from
perfect security, you need to evaluate what your most effective
imperfect system will be for your particular needs and threat
model.
> Oh yeah and what if I took a video CD and scrambled it and then
> if I took another video CD and scrambled it. And, then I scrambled
> the two of them together. And, then I used that CD with the program
> above to generate these temporary pads from codewords. How would
> you rate the ability of someone to crack a particular message using this
> OTP method? Easy, Moderate, Hard, Very Hard, Impossible ?
Depends -- can your opponent know what video CD's you've used
to select from, and how you mixed them, and how your codewords
are selected, and how they're used to select bits? The strength
of the system depends on these issues. It's not a OTP, but
depending on the details and your threat model it might be good
enough for your purposes.
--
Jim Gillogly
Hevensday, 22 Forelithe S.R. 1999, 17:53
12.19.6.4.17, 1 Caban 5 Zotz, Seventh Lord of Night
------------------------------
From: [EMAIL PROTECTED] (Gergo Barany)
Subject: RSA example with small numbers
Date: 12 Jun 1999 18:46:10 GMT
Delurking...
Hi. I recently got interested in the RSA algorithm and wanted to test it
by punching a few numbers in my calculator, but that is harder than I
thought, and I didn't find any examples of this on the WWW (and the
examples in Applied Cryptography are too big for my calculator).
Here's what I did:
I selected two primes, p=23 and q=37 (I could use any primes, but they
shouldn't be a lot bigger or smaller, I felt). Their product n=851,
(p-1)(q-1)=792. Then, I had the RSA Algorithm Javascript Page
[http://www.orst.edu/dept/honors/makmur/] generate my keys, d=317 and
e=5 (I would have done that myself, but neither AC nor the Cryptography
FAQ (question 6.5) gave me enough details on that).
Next, I tested those numbers to see whether those were valid keys:
317*5-1=1584, which is evenly divisible by 792. Also, e and (p-1)(q-1)
as well as d and n are relatively prime (since d and e are prime). So it
seems like those numbers are good keys.
I chose the number 10 as my plaintext and encrypted it:
C=M^e mod n=10^5 mod 851=433
Then I took the cyphertext 433 and decrypted it:
M=C^d mod n=433^{317} mod 851=499
Now, as you can see, my original plaintext is not the same as the result
of D(E(M)). My question is, could someone with more knowledge on this
subject explain to me what I did wrong or point me to a place where I
can find an example of RSA with numbers in about the same range?
Gergo
--
UFOs are for real: the Air Force doesn't exist.
GU d- s:+ a--- C++>$ UL+++ P>++ L+++ E>++ W+ N++ o? K- w--- !O !M !V
PS+ PE+ Y+ PGP+ t* 5+ X- R>+ tv++ b+>+++ DI+ D+ G>++ e* h! !r !y+
------------------------------
From: Horst Ossifrage <[EMAIL PROTECTED]>
Subject: Re: Slide Attack on Scott19u.zip
Date: Sat, 12 Jun 1999 12:08:29 -1000
Dear Mr. Wagner,
Thank you for spending some more time on this. I am preparing
a long post for tomorrow, but for now, I just want to point out
a possible misunderstanding on your part of the nomenclature:
David Wagner wrote:
> The primary equation is C[i] = S{(P[i] + P[i+1]) xor C[i-1]},
> or something like that. I was thinking of looking at a pair of
> plaintexts P[] and P'[] that satisfy
> (*) P'[i] = P[i+1].
> If I understand correctly, this should imply that
> C'[i] = S{(P'[i] + P'[i+1]) xor C'[i-1]}
> = S{(P[i+1] + P[i+2]) xor C[i]} = C[i+1],
> if you let C'[] represent the encryption of P'[] by a round.
i is not the Round number, it is the word address in a Block.
A block with 76 bits has four 19 bit words:
Plaintext Block = P[0]P[1]P[2]P[3] concatenated.
> In other words,
> (**) C'[i] = C[i+1].
> Repeating this for multiple rounds, we see that (**) for round
> j => (*) for round j+1, so you should get a slid pair, when the
> (*) is satisfied by the plaintexts (except possibly for 19 bits
> at the boundary, but if you just try enough pairs you should get
> that to match too by dumb luck, I think). Slid pairs can be
> recognized by the fact that the ciphertext satisfies (**) -- thus,
> the two ciphertexts you get agree in all but about 19 bits (if
> you rotate one by 19 bits).
>
> Ok, that was the approach I had in mind. Comments?
Your approach is educational for me. It helps to suppliment
the Paper. I expect that the Slide Attack will work, I am just
trying to write a perfectly clear document of how it is used
to break Scott19u.zip. I'll be back.
Horst Ossifrage, San Jose, California
------------------------------
From: "Particle" <[EMAIL PROTECTED]>
Subject: RSA msg length...
Date: Sat, 12 Jun 1999 14:43:39 -0400
how big can a msg (block) be?
for example: if p and q are each 512 bits, and n (which is
p*q) is 1024 bits... then I would guess the msg has to be
no more than 1024 bits long (since were doing a mod n )...
(or does it have to be no more than 512 bits long?)
thanks
--
Particle
[EMAIL PROTECTED]
http://www.geocities.com/SiliconValley/Way/7650
Home of the Java Data Structures 2nd Edition.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Does scott19u.zip make full use of it's large key size ?
Date: Sat, 12 Jun 1999 20:21:22 GMT
In article <7jtt29$bes$[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>
>> Due to the large key space it is possible to consturct a table such
>> that 2 messages that differ from each other from each other by a bit
>> to use completely different parts of the S-table so that the many
>> internal passes look different but that the final output is slightly
>> differrent however this is a very very rare case and to try to find
>> one by trying various keys and inputs. Would require the time
>> of the sun to burn out as people in this group like to point out.
>> however if you write a small message it is easy to change the
>> S-table on the last pass to make a ouput that is very similar to
>> the first input.
>
>Large or not similar messages are always possible. It is possible to
>have C=E(P) and C'=E(P') where the hamming distance of (C, C') is less
>then/greater then n/2 (n = bits per block). (hamming distance of (P,
>P') is biased too). If this is not possible your cipher is bad.
>(note: it may be improbable say one out of 2^128 messages will exhibit
>strong chars like this(.
>
>> For a given input message not all output messages are possible
>> if one varyes the key except for short messages then all outputs of
>> the same size are possible.
>
>Then your cipher is bad. For any n bit input (2^n possible messages)
>*ALL* 2^n outputs must be possible. This should be indepedant of the
>key (note when the key is larger then n, some messages will share
>mappings (from plain to cipher) but not for the entire set of messages).
>
>Tom
tommy I know your trying to act like a big boy but you have some growing
up to do because though you can throw big words around you really are making
very little sense. I will try to explain how foolish this last statement is in
terms your young mind can understand. Suppose I have a weak AES type
of cipher and I have a message of 256 bits all zero. Know if I vary the key
so all `128 bits of key space are used then at most it can only map to 2^128
different values. This falls far short of being able to map it to all possible
output message. Again i say
"For a given input message not all output messages are possible
if one varies the key except for short messages"
I hope this time you can read before you write and shoot your mouth off
again please little boy try to read it and think about it this time.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
------------------------------
** 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
******************************
