Cryptography-Digest Digest #725, Volume #9 Tue, 15 Jun 99 20:13:02 EDT
Contents:
Re: Cracking DES (David Wagner)
SLIDE ATTACK & large state SYSTEMS (SCOTT19U.ZIP_GUY)
Re: SLIDE ATTACK & large state SYSTEMS (David Wagner)
Re: Export restrictions question ([EMAIL PROTECTED])
Re: TEA vs Blowfish ([EMAIL PROTECTED])
Signing with two keys and verifying use one the key? (Yang Yang)
Test, please ignore (Yang Yang)
Re: Algorithm from easy spec please! ([EMAIL PROTECTED])
Challenge: signing with two keys, verifiable with one of the key, but can not fake
with one key? (Yang Yang)
Re: SLIDE ATTACK & large state SYSTEMS (SCOTT19U.ZIP_GUY)
Re: [Q]: Session key exchange ([EMAIL PROTECTED])
Re: DES and BPANN (James Pate Williams, Jr.)
Re: DES (Jerry Coffin)
Re: "Breaking" a cipher ("Steven Alexander")
Re: DES (Jim Gillogly)
Secret info for MACS (Casey Sybrandy)
Re: DES lifetime (was: being burnt by the NSA) (Jerry Coffin)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Cracking DES
Date: 15 Jun 1999 12:04:15 -0700
In article <7k5tfs$pui$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
> Let us suppose that 2^73 bytes of memory is actually feasible. I
> understand that for this attack to work we would need about 2^140
> memory accesses.
Not quite right; the naive MITM attack takes 2^73 bytes of memory
and 2^70 memory accesses. A considerable improvement over exhaustive
search, but still, as you say, not very practical due to the massive
memory requirements.
An improvement that drastically reduces the memory requirements
(at some modest cost in computational complexity) is van Oorschot
and Wiener's parallel collision search techniques. See e.g. their
paper on breaking double-DES; I think it was in a recent CRYPTO.
In general, I would argue that it would be prudent to assume that
a cleverer adversary might be able to find an algorithm that entirely
eliminates the memory requirements, leaving a MITM attack that takes
just 2^70 operations. I think it is entirely possible that such an
algorithm exists, given van Oorschot and Wiener's clever techniques.
> I think that the cryptanalytic community should agree on an attack cost
> function that is more appropriate than just counting encryptions. In an
> official comment to NIST I have proposed a simple metric towards that
> end.
Ooh! I agree: I think this is a very interesting research question.
I wonder whether you can approximate the cost pretty well as a linear
function of the resource requirements, at least for some resources.
For instance,
1 MB of fast memory ~ 100 MB of slow memory
~ 2^36 trial encryptions / year ~ 1 KB of known plaintext
(These are just examples, I don't know if they're reasonable estimates.)
I'll look forward to reading your comment to NIST. Is it available?
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: SLIDE ATTACK & large state SYSTEMS
Date: Tue, 15 Jun 1999 19:20:46 GMT
Lets look at the Slide Attack as it applies to a
large key system instead of a small key of a mere
few hundred bits or less. The problem with small
keyed systems is that after only a few dozen bytes
if the encrpyted message came from text there is generally
only one solution as to what that text is.
This weakness is also exploited by methods such as
the slide attack where one searchs for slide pairs
and then checks to see if the single round has a
has a solution. If it does then this solution is
the one that is assumed to be the one for the multi
round case. This is a good attack for small key
systems but lets look a theoritical large key system
where it fails. This is a theorictical system only
suppose I represent it by a large S box that is re
peated twice. Such the C0 = F ( F (P0) ) this is
just the S-box repeated twice in series. The method can
be such that instead of keeping the S box in memory
The entry is calculated on the fly as the data is
available. OF course it could have been respresent by
one S-box but is wasn't. The task is to find entries
in the S-box so that the function used can be found
lets assume that if all zeores goes in all zeros
come out. That is as simple a slide pair you can get
the all zero case. Know you look at the basic S box
and see of there is a entry where 0 gets mapped to
zero lets say there is a valid set of keys that produce
this as a solution actaully if your method almost allows
for all S-tables there are many such possible keys that
could lead to this. Kow you think you have part
of the soultion. But in realitiy 0 could map to 1 and
1in stage 1. In the second stage 1 could map to 0. So that both
the slide critea are meet in that over all 0 can map to
0 and in the single stage. But it was not in the one
used in the code. As the key space gets large these
false soultions get more common. This is just a simple
example to show how one can be mislead in trying to
find a solutiuon. As the key space grows as in this
example there can be many false soultions if the original
S-box could be almost any S-box depending on the key.
But since most people who write crypto come from the
same narrow school of thought this may be a good attack
for the kind of ciphers they design. Since if the
key is very short the odds of the right entries even
being availabe for a false solution go down.
I am not saying my scott19u is a large key sytem but
it is headed in the right direction and it has more than one
type of round so Slide Attack no available for it anyway.
I just want to see what happens if the slide attack was
used for very large key systems.
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] (David Wagner)
Subject: Re: SLIDE ATTACK & large state SYSTEMS
Date: 15 Jun 1999 12:12:06 -0700
For an example of how to apply the slide attack to at least one
large-key system, see the analysis of Blowfish near the end of the
FSE'99 slide attack paper.
The attack works for any choice of S-boxes, so if you imagine
keying Blowfish from a 2^8 * 4 * 32 = 32768 bit key by filling in
S-box entries using bits from the key, then the attack will break
this large-key system. The attack needs about 2^27 chosen
plaintexts to recover the entire 32768-bit key.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Export restrictions question
Date: Tue, 15 Jun 1999 17:09:53 GMT
<< As for gotchas: why go through a pile of legal expense and
bureaucratic hassle for a worthless "cipher" such as 8-byte at a time
XOR? >>
Absolutely. I just include it with my very small vertical market app to
provide a foil against office busybodies. Maybe I'll just forget about
the application. If I ever get "called on the mat" by the NSA I'll just
point out how simple it would be for them to "break".
Thanks.
Robert
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: TEA vs Blowfish
Date: Tue, 15 Jun 1999 18:20:36 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Dave Hazelwood) wrote:
> Thanks for all the feedback. It seems that Blowfish is a bit faster
> and perhaps also a bit more secure (but of course the latter is
> always a guess) but TEA is smaller and easier to code.
>
> This makes my choice difficult.
Not really. Do you have 4KB to spare and a little key setup time?
Then go for Blowfish. If not use something else (possibly xtea).
> Does anyone have x86 real mode assembler program code for
> blowfish? Something that will compile under masm 2.0?
Not me. Blowfish can be done in Turbo C++ 3.0 rather quickly though.
It will work in real mode as it needs 4KB only...
> I have maybe one more option and that is RC4. It is the fastest right?
> How does it stack up to TEA and Blowfish in terms of security and
> ease of coding?
RC4 is easy to code and is fast. It is not a block cipher however so
they don't really compare.
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Yang Yang <[EMAIL PROTECTED]>
Subject: Signing with two keys and verifying use one the key?
Date: Tue, 15 Jun 1999 15:03:46 -0500
In my project, I came up with following problem:
kb
A ------> B
\
------> C
kc
A will send a message M to both B and C. A shares a symmetric key kb
with
B. A also shares a symmetric key kc with C. A will broadcast the message
M
to both B and C. A also wants to add authenticity and integrity to the
message.
One obvious solution is a message containing (M, MAC(kb, M), MAC(kc, M))
Then both B and C can verify the message, and neigher B nor C can tamper
the message.
However, the above solution has two MACs in the message. Can we make it
down to only one MAC. Essentially, the message should looks like
(M, MAC'(kb, kc, M))
The MAC'(kb,kc,M) can be verified using either kb, or kc. But with kb,
or
kc only, B or C can not fake a MAC.
In the above question, we assumed kb, kc are not related. kb and kc can
be
related, as long as nobody can derive kb from kc or the other way
around.
There should be some smart algorithm around. Please enlight me.
Thanks
------------------------------
From: Yang Yang <[EMAIL PROTECTED]>
Subject: Test, please ignore
Date: Tue, 15 Jun 1999 14:50:51 -0500
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Algorithm from easy spec please!
Date: Tue, 15 Jun 1999 20:53:15 GMT
Ok, if you already have a RNG that is strong enough for you,
int table[93], table2[93];
for(i=0;i<93;i++)
table[i]=i;
table is now full of intergers 0-93.
assuming the nos in the key are 0-93 (ie your key -33) -- all of them,
no duplicates,
for(i=0;i<93;i++)
table2[i]=table[ key[i] ];
table2 is now randomly full of 0-93, keyed by your key. The code is
odd C (i am not a programmer really...), but i _think_ the principle
is sound and quick.
------------------------------
From: Yang Yang <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.research
Subject: Challenge: signing with two keys, verifiable with one of the key, but can not
fake with one key?
Date: 15 Jun 1999 20:55:38 -0000
[One obvious possibility is for A to sign the message with a public-key
digital signature scheme. Does that fill your needs? -Ed.]
Hi,
I am working on a project and come up with the following question:
A ----> B
\
----> C
A needs to send a message M to both B and C. A shares a key KB with B. A
also
shares a key KC with C. Now A wants to send the message M to B and C
with
authentication and integrity check. A wants to generate only one copy of
the message.
One obvious solution of the message will be (M, MAC(KA, M), MAC(KB,M))
But this way the message contain two copies of MAC.
My question then is: Is there a way A can generate one MAC using KA, and
KB.
A message something like (M, MAC'(KA, KB,M)), and both B and C can
verify
the message. But neither B, or C can fake a MAC the other guy will
accept.
In the above scenerio, KA and KB are irrelated. KA and KB are related is
also work.
But we must be sure no one can derive KA from KB, or the other way
around.
Any ideas?
Thanks.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: SLIDE ATTACK & large state SYSTEMS
Date: Tue, 15 Jun 1999 21:35:45 GMT
In article <7k68i6$e2e$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (David Wagner) wrote:
>For an example of how to apply the slide attack to at least one
>large-key system, see the analysis of Blowfish near the end of the
>FSE'99 slide attack paper.
>
>The attack works for any choice of S-boxes, so if you imagine
>keying Blowfish from a 2^8 * 4 * 32 = 32768 bit key by filling in
>S-box entries using bits from the key, then the attack will break
>this large-key system. The attack needs about 2^27 chosen
>plaintexts to recover the entire 32768-bit key.
Sorry Dave
But this does not change or effect the comments that
I wrote. For truely large key systems similar to the type
I mentioned the number of false slide pairs would increase
and the attack would not be reasonable. But I will take
your word that a Blowfish type of algorithm would be
susceptable to such an attack. I also think your defination
of a large key system is much smaller than mine. I am
not sure mine is large enough and the effective key lenght
is over a million bytes. (not bits) Though it is true I thought
you worked on ciphers of only a few hundred bits. Have you
actaully tested the attack out on the above blowfish or just
assumed it based on smaller models that it would take this
many steps. What do you do if the key system is large and
you have false slide pairs. In that you think they are correct
but they are not. Or have you even looked into this area since
they would not be common in the ciphers you tend to deal
with.
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: [Q]: Session key exchange
Date: Tue, 15 Jun 1999 18:58:22 GMT
In article <7k609m$co1$[EMAIL PROTECTED]>,
Jyrki O Saarinen <[EMAIL PROTECTED]> wrote:
> Is it feasible to implement a Diffie-Hellman key exchange
> where the other end is equipped with a 10MHz Hitachi H8/S CPU
> (2 cycles for simple operations) while the other end is a
> normal PC? How long this key exchange would take?
That would probably take about 1.5-2 minutes on average. I can't
imagine a 10Mhz cpu performing the DH exchange quickly.
> The need for a session key would be likely something
> like few times in a minute.
Not a good idea. You will spend most of the time calculating the key
and not actually sending data. that's why most servers are PIII
450mhzs...
> I read estimated of ~one second on a 20MHz 68030 which
> is probably ~2-3x faster than our target CPU.
>
> What other methods there are, a key distribution
> center doesn't sound too good for a dynamic environment.
If it's a closed network I would create the keys once a day and use
them. It depends on the use. Are you doing a dialup type thingy or
what? If it is then you must calc the key only once per connection,
etc...
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (James Pate Williams, Jr.)
Subject: Re: DES and BPANN
Date: Tue, 15 Jun 1999 22:05:17 GMT
On Tue, 15 Jun 1999 08:08:37 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
wrote:
>The big difference is that the XOR function is vastly simpler than
>the BPANN, but the DES encryption function is sufficiently complex
>that any "learning" process which does not model the actual DES
>structure fairly closely doesn't have an appreciable chance of
>converging to a *correct* model.
Conjectures are all well and good, but without a theoretical or
experimental basis they are merely guesses shrewd or otherwise.
Do you know of any research in the open literature that applies
various learning pardigms to DES? I have negative results with
a couple of genetic algorithms (GAs) that I have thrown at the
problem.
==Pate Williams==
[EMAIL PROTECTED]
http://www.mindspring.com/~pate
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: DES
Date: Tue, 15 Jun 1999 16:30:07 -0600
In article <7k51r0$gjr$[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
[ the initial permutation in DES being to support hardware
implementations ]
> I've heard and read this several times but while
> being from a hardware background I cannot see how
> the initial permutation could speed up the
> hardware implementation. Does anyone know how it
> helps the hardware?
I'm not sure it makes a hardware implementation any easier; it just
happens to be really trivial to implement in hardware. I suspect it
was added to make weak keys a bit less likely to happen by accident --
if you start with a key with a fairly obvious pattern, the pattern
will get scrambled before the key gets used. Since this is simply a
1:1 transformation, there are exactly as many weak keys afterwards as
before, so statistically the likelihood of a weak key is just as
great. People, however, don't follow statistics very well -- some
keys really ARE a lot more likely than others to be used if the person
chooses a key directly. The initial permutation simply makes keys
with obvious patterns a bit less likely to give disastrous results.
------------------------------
From: "Steven Alexander" <[EMAIL PROTECTED]>
Subject: Re: "Breaking" a cipher
Date: Tue, 15 Jun 1999 15:16:37 -0700
It is also said that someone can break a cipher if they can can recover the
key/plaintext in a reasonable amount of time whether it is by brute-force or
a faster attack. For example, EFF can break DES in a couple of days using
brute-force.
-steven
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: DES
Date: Tue, 15 Jun 1999 16:36:25 -0700
Jerry Coffin wrote:
> I'm not sure [the initial permuation] makes a hardware implementation
> any easier; it just
> happens to be really trivial to implement in hardware. I suspect it
> was added to make weak keys a bit less likely to happen by accident --
> if you start with a key with a fairly obvious pattern, the pattern
> will get scrambled before the key gets used.
The IP is applied to the data rather than to the key. In any case, it
seems to me it would have the opposite effect: it clumps all the
high-order bits (the 0-bits if it's ASCII) together, which seems like
it would be more likely to exacerbate problems than fix them -- if your
bytes have half of their bits in a constant position zeroed, then half of
the initial round could be zeroes for every encryption. I don't see
this as a particular problem, but I can't see how it could be considered
a plus.
The choice of the low bit of each key bit for the parity bit also
seems a bit disingenous to me... a naive user might feed the
mandated 8-byte key (DES gets its 56-bits as 8 byte with parity)
as 8 ASCII characters; it loses the low bit to parity, and the
high bit to ASCII, leaving 48 bits of real key. Fortunately most
implementations these days protect the user from having contact
this intimate with their chips.
--
Jim Gillogly
Sterday, 25 Forelithe S.R. 1999, 23:25
12.19.6.5.0, 4 Ahau 8 Zotz, First Lord of Night
------------------------------
From: Casey Sybrandy <[EMAIL PROTECTED]>
Subject: Secret info for MACS
Date: Tue, 15 Jun 1999 18:45:38 -0400
This may be a dumb question, but can the hash of a person's password be
a good piece of secret info for a MAC?
I was doing some research for a project and I was reading up on MACs. A
MAC needs some sort of secret info that is shared by both sides. One
scenario I was looking at was a client-server architecture where a
client needs to log into the server, but both sides want to verify each
other. If the password file is shadowed, or at least not world
readable, and the person had a good password, I figured that this could
represent the piece of shared info. Both sides know it. The client can
verify the server and the server can verify the client since you have to
know the password to even verify the server let alone send a MAC for the
server to verify. Let me know what you think.
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: DES lifetime (was: being burnt by the NSA)
Date: Tue, 15 Jun 1999 17:54:31 -0600
In article <7junie$iv1$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
[ ... ]
> > DES was specified as being suitable for sensitive but not classified
> > information. NOWHERE in the specification was it said to be suitable
> > for ALL sensitive information as long as it wasn't classified.
>
> Wrong. It appears on pages 1-2, where the standard says
> "This standard will be used by Federal departments and agencies
> for the cryptographic protection of computer data when the
> following conditions apply..."
What standard is THAT from? Here's what FIPS 46-2 says:
======= start of quote =========
6. Applicability. This standard may be used by Federal departments and
agencies when the following conditions
apply:
1.An authorized official or manager responsible for data security or
the security of any computer system decides that cryptographic
protection is required; and
2.2. The data is not classified according to the National Security
Act of 1947, as amended, or the Atomic Energy Act of 1954, as
amended.
Federal agencies or departments which use cryptographic devices for
protecting data classified according to either of these acts can use
those devices for protecting unclassified data in lieu of the
standard.
Other FIPS approved cryptographic algorithms may be used in addition
to, or in lieu of, this standard when implemented in accordance with
FIPS 140-1.
In addition, this standard may be adopted and used by non-Federal
Government organizations. Such use is encouraged when it provides the
desired security for commercial and private organizations.
========= end of quote =======
Anybody who wants to verify that is welcome to take a look at:
http://www.itl.nist.gov/fipspubs/fip46-2.htm
and they can easily verify that the standard clearly says that DES
"May be used" rather than "shall be used" as well as specifically
giving permission to use other methods of encryption in conformance
with FIPS 140-1.
> When a FIPS standard says "will be used", that is not a prediction
> that agencies will choose to use the standard; it's a ruling that
> this is the standard that they are to use.
IF it actually said that, you might have some point. It provably does
NOT say what you've claimed, rendering your entire point invalid.
> As Bruce Schneier wrote in /Applied Cryptography/ (page 267
> of the second edition), "the Data Encryption Standard was
> adopted as a federal standard on November 23, 1976 and
> authorized for use on all unclassified government
> communications."
Authorized, yes. Required, NO. FIPS 46-2 makes it entirely clear
that its use is NOT required, and that other methods may be used in
its stead. In addition, waivers from following FIPS at all are
granted on a relatively regular basis.
In case anybody cares, I'll point out that NIST is proposing to
replace FIPS 46-2 with FIPS 46-3. The "Applicability" section of FIPS
46-3 appears identical to that in 46-2 -- it specifies that the
standard MAY be used, NOT that it shall be used.
The basic thrust of FIPS 46-3 is to replace DES with tiple-DES, with
the note that "NIST can no longer support the use of single DES for
many applications. Therefore, Government agencies with legacy single
DES systems are encouraged to transition to Triple DES. Agencies are
advised to implement Triple DES when building new systems."
They also say they anticipate the the coexistence of 3DES and AES,
"allowing for a gradual transition to AES."
------------------------------
** 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
******************************
