Cryptography-Digest Digest #676, Volume #9 Tue, 8 Jun 99 05:13:03 EDT
Contents:
Re: Challenge to SCOTT19U.ZIP_GUY ([EMAIL PROTECTED])
Re: CRC32 ([EMAIL PROTECTED])
Re: Scottu: I actually saw something usefull ([EMAIL PROTECTED])
Re: rc4 vs. rand() (fungus)
Re: SCOTT19U pass in nut shell ([EMAIL PROTECTED])
Re: rc4 vs. rand() ([EMAIL PROTECTED])
Re: Key lengths vs cracking time ([EMAIL PROTECTED])
Re: Annoying Newbie.... (Terry Ritter)
Re: Key lengths vs cracking time (Nicol So)
Re: Annoying Newbie....
Re: KRYPTOS ("Douglas A. Gwyn")
Re: KRYPTOS ("Douglas A. Gwyn")
Re: KRYPTOS ("Douglas A. Gwyn")
tomstdenis' simple.c ([EMAIL PROTECTED])
MD5 / RSA implementation in fortran (Carsten Tusk)
Re: Challenge to SCOTT19U.ZIP_GUY (Jerry Coffin)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Challenge to SCOTT19U.ZIP_GUY
Date: Mon, 07 Jun 1999 22:31:52 GMT
<snip>
<about the sbox, and CBC modes>
I cannot believe you said that. If I give you a 128 bit block of
ciphertext which was encrypted in CBC mode, it's true that it's will
not effect previous blocks, but that does not make it any easier to
break. If the cipher is a bijective process then any possible input
was the actual input.
It's easy to snap at the AES is it? Well Most of the AES ciphers do
not require 1MB of ram, in fact my cipher that I spent twenty minutes
designing takes less ram and is faster then yours. Of course my cipher
is a toy function right now, so let's not dicuss it. The point is that
the AES ciphers can run on a variety of platforms, and include actual
real descriptions and are much much faster. The fact that their blocks
are smaller makes them no less secure (unless you have 2^128 blocks of
cipher/plain text pairs). In your million bit key how much is actual
entropy? Can you compress the key? How do you find million bits of
entropy? A BBS generator would take about 30minutes to create the
key!!! That's the major concern with the key. A smaller key (say 128
to 256 bits) is adeaquete if the entire complexity of the key is
maintained. The round function has very little diffusion, it's mainly
local. It would be nice that if one entry was wrong the entire block
can be 'destroyed', however it takes '25' rounds? My toy function
requires 2 rounds (for real use I would think more) to 'destroy' the
block.
I think you should really spend more time looking at other ciphers and
see *why* they made the decisions they did. Also you compare your
cipher against block ciphers but it really is not. What is the fixed
size of the block? It's more like a CFB stream cipher (see that's
using your brain).
BTW if you want to peek at my toy cipher it's at
http://people.goplay.com/tomstdenis/simple.c
Tom
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: CRC32
Date: Mon, 07 Jun 1999 22:39:00 GMT
> Some people use CRC as an error detecting code. This is a
> Bad Idea, because the probability of miscorrection is rather high.
> If you need ECC, use a code designed for ECC.
The thing is if their are more 'random' bits in the message then the
correction code you are *always* going to miss an error. It's not
possible to detect all errors. Some codes however have nice properties
to detect smaller errors (single bit, byte or multiple bytes). Reed
solomon (?) can detect I think in (255,233) about 16 singlebit errors
in any message.
> About one in 2^(n/2) for n bit CRC by the birthday rule.
This applies to any hash or checksum though. And is not applicable to
error dectection (there is no reason).
> You may want to use SHA-1 or MD5, it's slower than CRC but the
> greater length will help, plus it's a secure hash.
MD5 is probably a better choice as it has 16 fewer rounds, uses less
registers and is quite simple. I heard Tiger is great for 64-bit
platforms (it has 3 64 bit registers...) so you may want to look up Eli
Biham for his algorithm.
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: Scottu: I actually saw something usefull
Date: Mon, 07 Jun 1999 22:44:11 GMT
> Were he not wrapping the chaining this would work. However he makes
> multiple passes over the data which will mess this attack up. Good
thought
> though.
The fact that the errors propagate in one direction only can be
exploited. I just don't know how. In reality you would want a single
bit to effect some 'random' half of the block. This is what they would
call resistance to differential analysis?
Let's not forget he has 25 rounds, requires 1.5MB ram and is about 3
times slower then most block ciphers. (had to get that in), he is
working backwords.
As a toy in the middle I wrote this
http://people.goplay.com/tomstdenis/simple.c
which requires 128kb ram (still bad) but doesn't have the
unidirectional diffusion. It's basically a sub cipher like his only it
works on a 128bit block in parallel. It still needs a bijective final
permutation (keyed) to be a complete block cipher though. BTW my
cipher is easier to understand, faster and requires less ram (had to
get that in too). Yes I know that there are 23 other ciphers which are
much faster and smaller, but I am just proving a point that large s-
boxes can be used, and used efficiently (unlike his cipher).
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: fungus <[EMAIL PROTECTED]>
Subject: Re: rc4 vs. rand()
Date: Tue, 08 Jun 1999 03:22:40 +0200
Particle wrote:
>
> just another tid-bit about RC4...
>
> would it make sense to use a block cipher (like DES) on the
> 8x8 box?
No. The box is a permutation of 256 bytes, not a random number.
> (or maybe the key, at the same time expanding it to
> 256 bytes?) It looks like it might prevent some bad keys from
> hurting the algorithm...
>
Well, it might, but what's the point? Weak keys are easy to
avoid anyway.
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: SCOTT19U pass in nut shell
Date: Tue, 08 Jun 1999 00:04:13 GMT
> I'm not sure why you think you can determine who I voted for based on
what
> I wrote (you're wrong by the way). Anyway, sorry for being a stuffed
shirt
> but encryption is serious business. Here at IBM we encrypt messages
and
> design data between sites and between other companies that we work
with. I
> can just imagine being the guy who convinces my group to use SCOTT19U
> encryption rather than 3DES and then having to explain to my manager
why
> our designs were stolen by a competitor. "But boss, I just can't
> understand why the encryption program wasn't secure. The author
carefully
> architected the algorithm based on hairs in his ass. He even choose
> certain parameters because he knew others would hate the choices. So
you
> see boss, it just *had* to work, right?"
I like your view :), it's the most realistic complaint to date.
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: rc4 vs. rand()
Date: Tue, 08 Jun 1999 00:00:31 GMT
> would it make sense to use a block cipher (like DES) on the
> 8x8 box? (or maybe the key, at the same time expanding it to
> 256 bytes?) It looks like it might prevent some bad keys from
> hurting the algorithm...
No the sbox must form a function. The shuffle algorithm is the
simplest method to form a highly non linear function.
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: Key lengths vs cracking time
Date: Tue, 08 Jun 1999 00:09:06 GMT
> It boils down to work, more is better however you manage to force it
to be done.
This being true would you use a 256 bit key (with implicit trust) if it
could be solved in only 2^64 effort anyways?
You are correct in assuming that even if it does require many many
trials (>2^64) then it's practically secure, but the ideal would be as
advertised (of course for any finite algorithm there will always exist
an algorithm to 'break' the cipher... regardless of effort).
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] (Terry Ritter)
Subject: Re: Annoying Newbie....
Date: Tue, 08 Jun 1999 01:42:52 GMT
On Mon, 07 Jun 1999 21:00:37 GMT, in <7jhbtf$1pn$[EMAIL PROTECTED]>, in
sci.crypt [EMAIL PROTECTED] wrote:
>Hi.
>I am pretty new to this, but I do have a good understanding of
>pen/paper ciphers vignere (sp), ceaser etc, and I have read+understood
>the sci.crypt faq. Unfortunately, all the info on the net is either
>cap'n crunch decoder rings, or quadratic number field seives; nothing
>inbetween, you know?
> Anyways, if anyone has any good files covering the transition between
>the basics and the good stuff, or is willing to explain some stuff to
>help me, i would be eternally grateful.
There is an introduction to cryptography and a crypto glossary on my
pages.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: Key lengths vs cracking time
Date: Mon, 07 Jun 1999 22:05:24 -0400
[EMAIL PROTECTED] wrote:
>
> [wtshaw wrote:]
> > It boils down to work, more is better however you manage to force it
> > to be done.
>
> This being true would you use a 256 bit key (with implicit trust) if it
> could be solved in only 2^64 effort anyways?
Maybe. Most ciphers regarded as secure are only widely believed to be
so. If somebody comes up with a 256-bit cipher that provably requires
at least 2^64 elementary operations (say trial encryptions) to break, it
has a lot of value. If nobody could figure out how to reduce the key
size to 64 bits while preserving the mathematical proof of security,
somebody might just want to use it with 256-bit keys.
> You are correct in assuming that even if it does require many many
> trials (>2^64) then it's practically secure, but the ideal would be as
> advertised (of course for any finite algorithm there will always exist
> an algorithm to 'break' the cipher... regardless of effort).
Let me play devil's advocate here. Breaking 1024-bit RSA certainly
requires fewer than 2^1024 operations. Would you call the cipher
insecure just for that reason?
Nicol
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: Annoying Newbie....
Date: 8 Jun 99 01:42:58 GMT
[EMAIL PROTECTED] wrote:
: Unfortunately, all the info on the net is either
: cap'n crunch decoder rings, or quadratic number field seives; nothing
: inbetween, you know?
There are a number of books worth reading, such as The Codebreakers by
David Kahn, and Bruce Schneier's Applied Cryptography.
But in this case, I think I can mention my web site. It starts with
pencil-and-paper ciphers of the decoder ring variety, and it goes on to
touch on the mathematics of public key systems, but it also deals with the
stuff in between: rotor machines, block ciphers, and so on. It isn't an
introduction to number theory, but it does cover ciphers between the
advanced and the elementary.
John Savard
http://members.xoom.com/quadibloc/index.html
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: KRYPTOS
Date: Tue, 08 Jun 1999 05:02:35 GMT
[EMAIL PROTECTED] wrote:
> Why does anybody care? It's a single message encoded with a unknown
> cipher (they have an idea on what it could be) with no way of
> detecting if they got the right message.
No, it appears to be several messages (separated by "?" characters)
encrypted in different systems, and some of them are long enough
that a correct decryption would be unambiguous. I.e., any two
competent cryptanalysts who found solutions would find the same one.
> ... If you are doing just a story on it... It was dropped off in
> front of the federal building by an unknown person some years back.
You're completely wrong. Kryptos was a commissioned work by local
sculptor James Sanborn. It's in the courtyard next to the CIA
cafeteria.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: KRYPTOS
Date: Tue, 08 Jun 1999 05:11:32 GMT
Jim Gillogly wrote:
> ... Given Scheidt's interest in key escrow, I'd expect the
> key to be hidden in there for somebody who knows what to look for.
I don't think it has anything to do with key escrow, but the solutions
(or at least the plaintext) were sealed in an envelope which was given
to the DCI.
One section of Kryptos is clearly a transposition cipher, which means
that it is solvable with enough trial and error by someone who knows
the general methodology. (I haven't had the time to work on it; my
main contribution so far was to post an accurate transcription several
years ago, which one sometimes finds floating around the Internet with
attribution and other notes removed.)
Another section shows sufficient pattern to make me think that it too
should be breakable.
I suppose if you get desperate, you could burgle the DCI's vault. ;-\
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: KRYPTOS
Date: Tue, 08 Jun 1999 05:03:06 GMT
[EMAIL PROTECTED] wrote:
> Do you have any idea where this bogus one is??
http://members.aol.com/ikaulins/expak/expak6.htm
------------------------------
From: [EMAIL PROTECTED]
Subject: tomstdenis' simple.c
Date: Tue, 08 Jun 1999 05:55:40 GMT
I like the algorithm in simple.c. It is, as its name suggests, simple.
:-)
But there are some points I like to have cleared up:
1) in function schedule(), you need to have
y = (y + key[x] + table[r]) & 0xFFFF;
2) The round function always works on pairs of bytes
(ab)->(a'b'), (cd)->(c'd'), etc.
Am I wrong in thinking that all I need is 65536 plain-cipher texts to
build a dictionary? Can't we modify substitution at the end of the
round to rotate bytes? (a=table[b], b=table[c], ...h=table[a])
3) I forgot. Something to do with key scheduling table. I cannot
convince myself that the table will be shuffled well enough for large
tables, but I cannot say why. Any extra info, ideas to convince me
otherwise?
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (Carsten Tusk)
Subject: MD5 / RSA implementation in fortran
Date: Tue, 8 Jun 1999 08:20:43 +0200
I am looking for implementations of MD5 and RSA routines
in plain old FORTRAN77. Has anyone seen anything like that
around anywhere? Or any other encryption routines?
thanks,
cat
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: Challenge to SCOTT19U.ZIP_GUY
Date: Tue, 8 Jun 1999 01:37:01 -0600
In article <7je27p$8r$[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
> According to Jerry Coffin <[EMAIL PROTECTED]>:
> > 1) A large enough key that not only is a brute-force attack
> > impractical, but breaks would have to be large to mean anything.
> > 2) Resistant to currently known attacks.
> > 3) Reasonable expectation of performance no worse than DES.
>
> This just looks like the AES. You might find the 15 candidates rather
> interesting.
I've looked -- some of them are certainly interesting to some degree
or other.
> (Although the speed requirement for AES was "it should be at least
> as efficient as 3DES", most candidates are in fact must faster than
> DES when properly implemented in software -- speed in hardware is a
> different beast which also involves some parameters such as the number
> of gates needed)
Of course, since DES (and by extension, 3DES) is faster in hardware,
it's a bit harder goal to meet there.
> > 4) A combination of at least two fundamentally different types of
> > encryption.
>
> If it helps you feel secure... I personnaly prefer really simple
> designs, that can be fully analyzed. Ad hoc add-ons are too close to
> obscurity for me to trust them.
I'm quite sure I didn't use "ad hoc" anywhere in my statement. I
agree that full analysis is necessary, but I don't think that using a
combination of at least two fundamentally different forms of
encryption precludes it.
> Moreover, merging two different designs means doubling development time,
> and the size of the specialized hardware that may implement it.
I don't agree. This only stands a chance of being true if the
hardware and/or design requirements of both forms of encryption are
identical, which seems (to me) rarely, if ever, the case. In the case
of hardware, it assumes that NONE of the hardware can be shared
between the two, which may happen, but is far from guaranteed.
> > I also kind of generally like Scott's idea that changing bits
> > anywhere in the message being encoded can have effects anywhere (and
> > everywhere) in the encoded text.
>
> This assumption is not realistic for on-the-fly encryption of a harddisk
> or a network.
Obviously not. The question is whether people really want to design
that form of encryption or not. If nobody really wants to do that,
IMO it would be a bit foolish to design for something nobody
particularly cares to do.
> Your cipher may have some memory of the past, but not of
> the future. There are situations where the beginning of the data should
> be transmitted, processed and answered before the rest of the data may
> even exist: think about enciphered web browsing for instance: you send a
> request for a document, and when you get it, you send requests for the
> sub-documents (pictures,...). Before getting the document, you cannot
> know what will be your next request, and therefore the enciphering of
> the first request must not depend on the future.
I think it's safe to say that no matter what design criteria are
chosen, a situation exists for what those criteria are wrong. Given
that the original thread was about a program that encrypted files, I
thought it was reasonable to design an algorithm with the same basic
idea in mind. The question is whether enough people care about doing
something different for it to be worthwhile to design for other
purposes or not. Are you saying that you'd be interested in
implementing an algorithm, but consider these applications important
enough that you'd plan on designing for them, or are you simply
pointing out a situation that's not addressed by the original design
criteria?
> > For the sake of comparison, linear cryptanalysis is considered quite
> > effective against DES. IIRC, "quite effective" in this case means that
> > it gives a reduction in difficulty on the order of 2^16 or so compared
> > to a brute-force attack. You need a MUCH bigger break than that to
> > begin a meaningful attack against a 256-bit key.
>
> Linear cryptanalysis is not practical for DES: it requires 2^43 known
> plaintexts, which is really many.
Yes, I wasn't trying to imply that it was useful (I think it's still
pretty well agreed that the most effective attack on DES is brute-
force), but that if you did collect sufficient data, it gives a fairly
large reduction in the number of keys you have to search.
> However, since the choice of an algorithm is a matter of trust, you may
> want even stricter requirements: for instance, for a block cipher with
> 128-bit blocks, there should exist no (theoretical) attack that would
> reveal 1 bit of the key with less than 2^128 known plaintexts.
I'd might consider loosening that a bit.
> DEAL has been considered broken because you could guess 1 bit with 2^120
> known plaintexts (the 'attack' turned out to be unconvincing: it is not
> clear whether this might work or not; and 2^120 is way out of reach
> anyway, so we cannot just try).
Right -- it's pretty clear that in many cases, such attacks are of
purely academic curiosity. For these kinds of attacks to become
practical, the rate of growth in exploration of space would have to
accelerate considerably, since I'm pretty sure there's not enough
silicon on earth to build 2^120 bits of storage. OTOH, based on
history, it appears that vulnerability to one attack seems to go along
with vulnerability to other attacks as well. It's hard to guess how
much of this really implies vulnerability of the algorithms involved,
and how much is simply the more people research things that appear to
be somewhat fruitful already.
------------------------------
** 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
******************************
