Cryptography-Digest Digest #711, Volume #9 Sun, 13 Jun 99 07:13:05 EDT
Contents:
Re: Slide Attack on Scott19u.zip (SCOTT19U.ZIP_GUY)
Re: Slide Attack on Scott19u.zip ([EMAIL PROTECTED])
Re: Challenge to SCOTT19U.ZIP_GUY (Thomas Pornin)
Re: RSA example with small numbers ([EMAIL PROTECTED])
Re: DES ([EMAIL PROTECTED])
Re: Slide Attack on Scott19u.zip ([EMAIL PROTECTED])
Re: Slide Attack on Scott19u.zip (SCOTT19U.ZIP_GUY)
Re: Yet another simplecipher (YASC) ([EMAIL PROTECTED])
Re: cant have your cake and eat it too ("Douglas A. Gwyn")
Re: Caotic function ("Douglas A. Gwyn")
Re: DES ("Douglas A. Gwyn")
--- sci.crypt charter: read before you post (weekly notice) (D. J. Bernstein)
Re: RSA msg length... (Eric Young)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Slide Attack on Scott19u.zip
Date: Sun, 13 Jun 1999 01:25:44 GMT
In article <7jumfq$b1m$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (David Wagner) wrote:
>In article <7jue3a$2ci0$[EMAIL PROTECTED]>,
>SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote:
>> Just what do you mean bypass the fact the first and last round
>> are different. DO you mean your attacking a reduced version
>> of Scott19u. I think that reduced version attack was kind of what
>> Paul Onions did a long time ago?
>
>I'm not suggesting to attack a reduced version.
Then you have to face the fact of the two other passes
front and back and also the fact that 8 bytes is the smallest
file. so there can be no attack less than 64 bits.
>
>I'm referring to the earlier comment that the same S-box entry
>will not be used in the first and last round, since in all likelihood
>the 19-bit input to the S-box will be different.
>This fact was claimed to make slide attacks impossible.
>
>I was suggesting that this fact might not be so bad (for the attacker)
>as it seems; that you can still make slide attacks work, even though
>different S-box entries are used.
>
>> >
>> >The primary equation is C[i] = S{(P[i] + P[i+1]) xor C[i-1]},
>>
>> Actually in your notation it is C[i]=S{(C[i-1] xor P[i]) + P[i+1]
>> where if the first 19 bits of Pass call P[0] then C[-1] is the last
>> nineteen bits used in the file. The min file length is 64 bits.
>
>Oops, serves me right for not looking it up. Anyhow my point below it
>is still valid (I think), you just have to change the equations slightly.
>
>> THe complete file is rotated 9 bits up so the the top 9 bits of C[0] go to
>> bottom of the file. Also there is a first and last round the Paul function
>> that is different from the 23 rounds that are represented by the
>> equations above. When one gets to the end of file it borrows for the top
>> of file rest of C[0] and C[1] so that the most C[m] is such that parts of the
>> last P[n] and P[n+1] could be using parts od C[0] and C[1] The Paul function
>> named after Paul Onions is very short and you can see the code to see
>> how that interacts with things.
>
>Ok, I have to admit you lost me here. Sorry.
Then lets do one pass of these 23 repeated center passes for scott19u.zip
You lay the file out in memory so you have 64 bits.
then define the last 19 bits is C[-1] then one you
do C[0]= S{ (C[-1] xor P[0] ) + P[1]}
know copy the contents of C[0] to the bottom of the file
you know have 83 bits.
note P[0] the first 19 bits P[1] the next 19 bits.
know comes the hard part replace the top 10 bits of P[0]
with the last 10 bits of C[0]. We have just calculated
the first 10 bits out for the pass.
Do C[1]= S{(C[0] xor P[1]) + P[2]} place C[1] right after the
loction in memory where C[0] is. That way know all of P[0]
is rewritten this pass and the first 10 bits of P[1]
Do C[2]= S{(C[1] xor P[2])+ P[3]) place C[2] right after C[1]
you know have from the top replaced 10 + 19 + 19 for 48 bits
at this point P[3] has 7 bits of itself and the top 12 bits of C[0]
Since 48 + 19 = 67 is greater than 64 the original lenght of
file you are done this pass calling the main equatiion
but there is 64-48 16 bits left
so you shift up the file from the bottom so that P[3] is placed next
to C[2] This is a 9 bit shfit. Notice that when you calulated C[0]
at front of pass and added this to bottom of file. You end up having
the nine bits lost from the first C[0] now at the bottom. This means
that for the 64 bit file only 3*19 57 bits are replaced so that 7 bits
are not changed this pass but are rotated in the file up 9 bit positions.
this means that those 7 bits which have not changed get changed
during the next pass since they are part of P[2] on the next pass.
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
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Slide Attack on Scott19u.zip
Date: Sun, 13 Jun 1999 00:06:01 GMT
<snip>
I added the round keys like we agreed on. The new copy is at
http://people.goplay.com/tomstdenis/simple.c
BTW if the code is not clear enough I could be motivated to document it
(I probably will anyways...)
Anyways I would like to break the following variations
1. No permutations (final/initial), no round keys
2. No permutations, with round keys
3. permutations, no round keys
4. Full thing.
I am willing to take the initial steps into the first one, but would
appreciate some newbie tips. I will have to get back to the group if I
can actually document an attack on #1.
#1, a one round attack could retrieve the entire table in 2^13 blocks.
This is a naive attack though. One two rounds I would try to find
patterns like (x, y, x, y) -> (a, b, a, b). I don't know how to
exploit this though. This would mean that the input to the sboxes for
the first and third was equal and likewise for the second and fourth.
I think it would require a lot of chosen plaintext since you would have
to cycle... I don't know. This is what I mean. I have the idea in my
head but I don't know how to push it.
You know that the output was
(x, y, x, y)
You know the last inputs must have been (a, b, a, b) From this you can
calc that the outputs of the first table was
a' = a - b
b' = 2b - a
c' = c - d
d' = 2d - c
If I am not mistaken. We still don't know a' .. d' though. Would this
be an example of soling using linear expressions? (I.e build a huge
matrix with all the expressions and try to plug in the s-box values
which make all the statements true?, this would be faster then
searching the entire key space as many solutions can be eliminated at
first glance)...
Geez... I am really lost.
Tom
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (Thomas Pornin)
Subject: Re: Challenge to SCOTT19U.ZIP_GUY
Date: 7 Jun 1999 11:37:31 GMT
According to SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]>:
> So do you really want to understand the routine or thoughts behind it
> or what?
The routine is irrelevant. Only the algorithm is; the implementation
problems have no implication on security. It is useless to ask oneself
how to implement an algorithm when the algorithm is not yet specified.
It can be done, that is all that matters for the moment.
I do not want hints about your code. You know the algorithm, if you want
people to review it (which they will insist on doing before using it),
you should tell them "the algorithm is the following" instead of "the
implementation is the following, guess the algorithm".
Many people said that they cannot read your C code, which is close to
mean that your C code is unreadable (by definition). You might also say
"these people cannot read C, this is their problem" but you will feel
very alone real quick.
--Thomas Pornin
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: RSA example with small numbers
Date: Sun, 13 Jun 1999 00:31:33 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Gergo Barany) wrote:
> Yes, I know dc, but I haven't used it much since I don't know more
than
> the basics of reverse-polish notation (but I'll get around to learning
> it someday).
Polish notation is where dyadic terms go first then the operator. For
example 'a + b' becomes 'a b +'. It is really simple to code this
way. Of course most calcs use standard notation. I like the new one
in Win98, it has way more precision then the one in Win95.
BTW does polish notation specify how monadic (what is the singular of
dyadic?) like unary ops (not, compliment, negate).
Tom
--
PGP public keys. SPARE key is for daily work, WORK key is for
published work. The spare is at
'http://members.tripod.com/~tomstdenis/key_s.pgp'. Work key is at
'http://members.tripod.com/~tomstdenis/key.pgp'. Try SPARE first!
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: DES
Date: Sun, 13 Jun 1999 01:26:07 GMT
In article <[EMAIL PROTECTED]>,
Hideo Shimizu <[EMAIL PROTECTED]> wrote:
> In some special case, IP affects security of DES. At least
> in case of linear cryptanalysis of 32bit-MAC using DES, Sakurai,
et.al.
> pointed out above result.
I would like to have that one explained. If the IP is a known
permutation then it cannot be secure can it?
Tom
--
PGP public keys. SPARE key is for daily work, WORK key is for
published work. The spare is at
'http://members.tripod.com/~tomstdenis/key_s.pgp'. Work key is at
'http://members.tripod.com/~tomstdenis/key.pgp'. Try SPARE first!
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Slide Attack on Scott19u.zip
Date: Sun, 13 Jun 1999 01:30:16 GMT
> You lay the file out in memory so you have 64 bits.
> then define the last 19 bits is C[-1] then one you
> do C[0]= S{ (C[-1] xor P[0] ) + P[1]}
> know copy the contents of C[0] to the bottom of the file
> you know have 83 bits.
> note P[0] the first 19 bits P[1] the next 19 bits.
I am not attacking you but as a suggestion, lets review a more orthdox
cipher first. Will you entertain the notion of reviewing scottu16? If
it doesn't have the wierd bit field manipulations (well bit vectors is
ok...) then I think we can just review the operations. Anything we
come up with will most likely apply to scottu19 proportionally.
BTW splitting bits (10 bits here, 9 bits there) is not hard to program
(shift and mask), it is however slow in software.
Tom
--
PGP public keys. SPARE key is for daily work, WORK key is for
published work. The spare is at
'http://members.tripod.com/~tomstdenis/key_s.pgp'. Work key is at
'http://members.tripod.com/~tomstdenis/key.pgp'. Try SPARE first!
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Slide Attack on Scott19u.zip
Date: Sun, 13 Jun 1999 04:35:27 GMT
In article <7jv1j9$lhm$[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>
>> You lay the file out in memory so you have 64 bits.
>> then define the last 19 bits is C[-1] then one you
>> do C[0]= S{ (C[-1] xor P[0] ) + P[1]}
>> know copy the contents of C[0] to the bottom of the file
>> you know have 83 bits.
>> note P[0] the first 19 bits P[1] the next 19 bits.
>
>I am not attacking you but as a suggestion, lets review a more orthdox
>cipher first. Will you entertain the notion of reviewing scottu16? If
I don't have a method called scottu16 could you have meant scott16u
>it doesn't have the wierd bit field manipulations (well bit vectors is
>ok...) then I think we can just review the operations. Anything we
>come up with will most likely apply to scottu19 proportionally.
>
>BTW splitting bits (10 bits here, 9 bits there) is not hard to program
>(shift and mask), it is however slow in software.
One could use shift and mask or one could use marcos in C with
the proper structures which is what I choose to do.
You could look at the scott16u version if you wish. I assume it would
be much easier to examin however it is a much older product.
but it is what the 1000 dollar contest that I have running is all about.
You could even win the money if your first to solve it for the changes
that I have. But time is running out you only have till Nov 11 1999
>
>Tom
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
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Yet another simplecipher (YASC)
Date: Sun, 13 Jun 1999 03:43:54 GMT
I rewrote the example because I was not pleased with it. The new
example (which is faster and includes a key schedule) is at
http://people.goplay.com/tomstdenis/simple2.c
It is much simpler then my first simple cipher, takes less memory and
is faster. It uses the sboxes from CAST to achieve avalanche effect
and resistant to differential/linear analysis. Currently it is set to
12 rounds however that is just a guess. I would really estimate the
usefull amount of rounds at 20 or so.
Anyways since David Wagner broke the first simple cipher (without the
round keys) I don't know how usefull it could be. The new one is much
simpler to read, and I invite people to comment on it.
I am still working on the first simple.c but I think it's too
cumbersome. Maybe the first cipher can be simplified? I was thinking
of trying something like
a = a ^ table[((b + c) ^ d) + rkey]
(64 bit cipher)
a = a ^ table[(((((b + c) ^ d) + e) ^ f) + g) ^ h + rkey]
(128 bit)
Where rkey is a round key. This would not be a substitution therefore
the key schedule would not have to calc the inverse. Now the PHT is
not required making the cipher slightly faster.
Any thoughts (about either)? I know I shouldn't be proposing so much
but I have so many ideas. Some of them work, some don't but heck I
learn a bunch that's all that matters right?
Tah,
Tom
--
PGP public keys. SPARE key is for daily work, WORK key is for
published work. The spare is at
'http://members.tripod.com/~tomstdenis/key_s.pgp'. Work key is at
'http://members.tripod.com/~tomstdenis/key.pgp'. Try SPARE first!
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: cant have your cake and eat it too
Date: Sun, 13 Jun 1999 08:03:28 GMT
[EMAIL PROTECTED] wrote:
> Large keys *do not* equal automatic security, ...
That is true, and probably some people are confusing that notion
with the *correct* notion that a sufficiently *small* key means
automatic *in*security. (Sufficiently small is currently around
56 bits for typical block cipher systems.) Treating the converse
of a truth as necessarily also true is a very common logic error.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Caotic function
Date: Sun, 13 Jun 1999 08:38:02 GMT
ivana wrote:
> 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 ?
The keywords to search for (using any standard Web search engine,
e.g. Lycos or Google) are "chaos" (note the spelling!), "fractal",
and "dynamical systems". If you have access to a decent library,
see if you can find the four-volume set by Abraham & Shaw,
"Dynamics - the Geometry of Behavior" (Aerial Press), which is a
very nice introduction to the subject with lots of illustrations
and very few equations. There are also numerous popular books
such as "Chaos: Making a New Science" by Gleick, and if you're
interested in fractal images, there are lots of books on that, too.
By the way, the first two responses I've seen to your query,
by tomstdenis and Jim_101, were both wrong -- chaos has nothing
to do with cellular automata, nor with complex numbers.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: DES
Date: Sun, 13 Jun 1999 08:57:48 GMT
[EMAIL PROTECTED] wrote:
> I would like to have that one explained. If the IP is a known
> permutation then it cannot be secure can it?
It is of no value against a known-plaintext attack, but it could
(slightly) affect some other forms of attack.
------------------------------
From: [EMAIL PROTECTED] (D. J. Bernstein)
Crossposted-To: talk.politics.crypto
Subject: --- sci.crypt charter: read before you post (weekly notice)
Date: 13 Jun 1999 05:00:34 GMT
sci.crypt Different methods of data en/decryption.
sci.crypt.research Cryptography, cryptanalysis, and related issues.
talk.politics.crypto The relation between cryptography and government.
The Cryptography FAQ is posted to sci.crypt and talk.politics.crypto
every three weeks. You should read it before posting to either group.
A common myth is that sci.crypt is USENET's catch-all crypto newsgroup.
It is not. It is reserved for discussion of the _science_ of cryptology,
including cryptography, cryptanalysis, and related topics such as
one-way hash functions.
Use talk.politics.crypto for the _politics_ of cryptography, including
Clipper, Digital Telephony, NSA, RSADSI, the distribution of RC4, and
export controls.
What if you want to post an article which is neither pure science nor
pure politics? Go for talk.politics.crypto. Political discussions are
naturally free-ranging, and can easily include scientific articles. But
sci.crypt is much more limited: it has no room for politics.
It's appropriate to post (or at least cross-post) Clipper discussions to
alt.privacy.clipper, which should become talk.politics.crypto.clipper at
some point.
There are now several PGP newsgroups. Try comp.security.pgp.resources if
you want to find PGP, c.s.pgp.tech if you want to set it up and use it,
and c.s.pgp.discuss for other PGP-related questions.
Questions about microfilm and smuggling and other non-cryptographic
``spy stuff'' don't belong in sci.crypt. Try alt.security.
Other relevant newsgroups: misc.legal.computing, comp.org.eff.talk,
comp.org.cpsr.talk, alt.politics.org.nsa, comp.patents, sci.math,
comp.compression, comp.security.misc.
Here's the sci.crypt.research charter: ``The discussion of cryptography,
cryptanalysis, and related issues, in a more civilised environment than
is currently provided by sci.crypt.'' If you want to submit something to
the moderators, try [EMAIL PROTECTED]
---Dan
------------------------------
From: Eric Young <[EMAIL PROTECTED]>
Subject: Re: RSA msg length...
Date: Sun, 13 Jun 1999 20:14:19 +1000
Particle wrote:
>
> 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?)
The message needs to be smaller than the modulus size.
For a 1024 bit key, you need to be less than n.
If you are going to use a standard padding system like
PKCS#1 (very very strongly recommended), the number will be smaller.
For PKCS#1 there are a minimum of 11 padding bytes defined.
So for a 1024 bit key, you can encode 53 byes of information.
eric
--
[EMAIL PROTECTED] or [EMAIL PROTECTED]
------------------------------
** 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
******************************
