Cryptography-Digest Digest #451, Volume #14 Sat, 26 May 01 19:13:01 EDT
Contents:
Re: A generic feistel cipher with hash and gf(257) mixers (Jim Steuert)
Re: Good crypto or just good enough? (Bryan Olson)
Re: Good crypto or just good enough? (wtshaw)
Re: A generic feistel cipher with hash and gf(257) mixers (Jim Steuert)
Re: A generic feistel cipher with hash and gf(257) mixers (David Wagner)
Re: A generic feistel cipher with hash and gf(257) mixers (David Wagner)
Re: Getting back to the self-study Analysis ([EMAIL PROTECTED])
Re: Essay on "The need for a look at real life crypto" (Tom St Denis)
Re: DES Crypto Myth?? (Tom St Denis)
Re: A generic feistel cipher with hash and gf(257) mixers (SCOTT19U.ZIP_GUY)
Re: Good crypto or just good enough? (Tom St Denis)
----------------------------------------------------------------------------
From: Jim Steuert <[EMAIL PROTECTED]>
Subject: Re: A generic feistel cipher with hash and gf(257) mixers
Date: Sat, 26 May 2001 17:11:40 -0400
I completely disagree. I believe that it would take much more work to
break the "remedied" proposed cipher.
Think of "remedied" proposed cipher as the following:
plaintext=>sha1=>+key1=>sha1=>+key2=>sha1=>+key3=>sha1=>output
where sha1 means a fixed-input invertible hash, and where +key means xoring
the 32-bit key part with only one of the 96-bit (160-bit for sha1) digest
(or data) inputs to the subsequent invertible hash.
Can you tell me again how you would go about breaking this??
David Wagner wrote:
> Jim Steuert wrote:
> > My remedy, given three 32-bit digest vars (a,b,c) was to, after the
> >inital 30 rounds of mixing of (a,b,c) , to replace the
> >simple xor of all three key parts (key1,key2,key3) with the following:
> >Xor the first part key1 of the key with the "a", and then provide say, 8 rounds
> >of mixing mix(a,b,c) , then xor only the second part of the key with "b" ,
> >then 8 rounds of mix(a,b,c), then xor only the final part of the key with "c".
> >Then proceed with the second half of the cipher, with its 30-odd mixing
> >phases.
>
> Well, of course any unkeyed operations done at the beginning or end
> of the cipher are useless and might as well be omitted.
>
> Moreover, since you are only using each part of the key once, you have
> to worry about meet-in-the-middle attacks. I bet the design above can
> be broken with about 2^32 work, if I understood it correctly.
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Good crypto or just good enough?
Date: Sat, 26 May 2001 14:20:22 -0700
Tom St Denis wrote:
>
> Bryan Olson wrote:
[...]
> > Today, crypto has two serious problems:
> > 1. We don't really understand complexity.
> > 2. The world runs on cleartext.
> >
> > Sci.crypt is flooded with conjectural ideas for symmetric
> > encryption, and endless debate over 3DES vs Rijndael vs
> > combining 17 different ciphers. None of that addresses any
> > problem anyone actually has.
>
> Maybe Academia should swing vines over to more practical problems then?
Academia is doing reasonably well.
> After thinking about it I think alot of block ciphers are not too far
> away from "Security by Obscurity." If you think about it the only thing
> that makes Twofish (for example) secure is the requirement for us to
> mount a brute force attack. there is no proof of the inability to mount
> a shortcut attack though...
What does this thinking imply about inventing a flood of
new ciphers with even less security justification than
Twofish?
--Bryan
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Good crypto or just good enough?
Date: Sat, 26 May 2001 15:13:28 -0600
In article <[EMAIL PROTECTED]>, Tom St Denis
<[EMAIL PROTECTED]> wrote:
> "SCOTT19U.ZIP_GUY" wrote:
> >
> > [EMAIL PROTECTED] (Tom St Denis) wrote in
> > <[EMAIL PROTECTED]>:
>
> All AES ciphers have high error propagation within the block size. They
> were designed that way because real people asked for fixed block sized
> ciphers.
I am real and I asked for otherwise. I was right for security's sake.
>
> > Hiding of input output pairs to the
> > underlying block encryption.
>
> This is impossible and you know it. You can't possibly hide the input
> and output in a chosen plaintext attack (for example).
>
If you get away from the above constraint I objected to, any useful pairs
can be as elusive and wild okra in the artic.
...
>
> No, I agree with Schneier that smaller key/block sized ciphers are
> easier to design and easier to make secure. The problem with large key
> ciphers is that you have to ensure proper key diffusion (and block data
> diffusion) to avoid attacks. Look at the original SAFER+ it had key
> problems because it didn't mix the 256 bit key quickly enough. However,
> SAFER+ with a 192 bit key is secure against the same attack....
>
> Tom
Schneier is usually right, but an oversimplification of a complex problem
is an exhibition of the same sort of problem that those words seem to
address.
--
Suppose California quit sending food back East.
Would Gerorge be ready to barter with energy?
------------------------------
From: Jim Steuert <[EMAIL PROTECTED]>
Subject: Re: A generic feistel cipher with hash and gf(257) mixers
Date: Sat, 26 May 2001 18:01:42 -0400
The statement, "Designing ciphers as a hobbyist is a Really Bad Idea",
really depends of your definition of a hobbyist. If you mean one who
is not really skilled in the math, then I heartily disagree. In fact, I
consider
that a challenge. I am now motivated to write a paper on "design
principles of cryptographic hash functions and ciphers", which should put the
design of these things in the hands of us "ignorant" hobbyists. I am
now motivated.
Of course, I will not try to have it reviewed. I think that it might get
killed in review because a) it isn't "better" than some existing ciphers or
b) it's "slower" than some existing cipher. While I think those are
valid objections, I disagree that custom ciphers are always a bad
idea.
Concepts of cryptographic hash functions are useful in designing
custom hash table algorithms, which is a real problem in things like
routers, etc, with which I am employed as a principal software engineer.
Knowing about things like OAEP(AONT) has direct commercial value.
Two jobs ago, I worked with a variety of pc encryption schemes
(related to driver-level encryption of files. The concepts of cryptography are
really useful thoughout the computer programming field.
In general, we cannot use pre-packaged algorithms unless we
understand them, especially when designing low-level encryption
schemes. However, the concepts, like salt, hashes, etc. are
necessary and used all over for design. Bruce Schneier's book is a
bible in the last three encryption jobs I've had.
My point is that, when you strip away the jargon, the concepts
of cryptography are really quite simple. They are simply presented in
a "cryptic" fashion, generally without the aid of diagrams. Of
course, many of the papers could benefit from more examples
and diagrams. I have keyed in on some important concepts, such
as bijectivity, multipermutation, etc. which are missing from the books.
As for the contributions of hobbyist, well, I just invented
a novel public key method, posted on this newsgroup, which has
garnered feedback from related proven methods being studied in Europe.
Perhaps it may be used some day. Who knows? Again hobbyists
can certainly learn from experts, but it is folly to think that experts cannot
learn from hobbyists.
As for my math skills, as a freshman at Princeton ( many years ago),
I took graduate all-graduate math courses, and advanced-placed
a year. I have published in a couple of reviewed journals (years ago).
Would any of the designers of ciphers and/or hash functions share their
design methodology/rationales. I know that some of the AES candidate
papers did this, and I've found a few college lectures on the web which
go more into the rationales, but certainly not in any books. There is a lot
of accumulated lore, which is not repeated in papers, which could
be assembled. (I've actually found a couple of good theses, one on
sboxes, which are very comprehensive and tutorial)
David Wagner wrote:
> Jim Steuert wrote:
> > What I am getting at, in general, though,
> >is a methodology which would take designing ciphers out of the hands
> >of the "experts" (no disrespect intended) and put it into the hands
> >of hobbyists, who could still come up with creative ideas, but based
> >on well-understood design principles.
>
> Why? Designing ciphers as a hobbyist is a Really Bad Idea, if you want to
> deploy the result in a real system: most such ciphers end up being weak.
> Read Bruce Schneier's Memo to an Amateur Cryptographer for details
> (see the Cryptograms at www.counterpane.com).
>
> In any case, such a methodology does not exist today. You are much
> better off to use a trusted, well-understood cipher, such as 3DES
> (which has seen tens or hundreds of person-years of analysis) or AES
> (which soon will see an equivalent amount of analysis).
>
> I don't want to discourage you, but if you want to maximize the odds
> of making a contribution to the science of cryptography as a hobbyist,
> block cipher design is not exactly the area I'd pick.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: A generic feistel cipher with hash and gf(257) mixers
Date: 26 May 2001 22:25:31 GMT
Jim Steuert wrote:
>The statement, "Designing ciphers as a hobbyist is a Really Bad Idea",
>really depends of your definition of a hobbyist. If you mean one who
>is not really skilled in the math, then I heartily disagree.
I mean "skilled and experienced in design and/or cryptanalysis of
block ciphers".
Note what I did and didn't say. I did not suggest that learning
about principles of block cipher design is a bad thing. I did not
suggest that understanding or explaining or studying design principles
or other designs is a bad thing. Nor did I suggest that experts
cannot learn from hobbyists. I do not believe any of those things.
Rather, I suggested that trying to design a cipher yourself *and
deploying it in a practical system* is a route that has historically
been strewn with the corpses of many broken systems. If you want your
system to be secure, you would do well to avoid this pitfall.
I certainly agree that that the concepts of cryptography are worth
knowing. I am just disputing that the "designing a new cipher and
deploying it in a real system" is the best way to learn about them!
Again, I don't want to discourage you. I merely want to caution you
against *deploying homemade ciphers in real systems*: doing so is
very dangerous.
Don't get the wrong opinion: I'm not saying this out of some kind
of snobbery. Perhaps it would help if I mentioned that I don't
really trust myself to design new ciphers, and I've tried to avoid
it whereever possible. The one time that I did give it a try was
when I had a team of many other folks experienced at cryptanalysis,
and we had a great deal of time to thoroughly study our choices,
*and* we published the design and knew that others would give it
a great deal of study as well. It is easy to get this stuff wrong,
no matter how much experience you have in this field.
By the way, have you read Bruce Schneier's "Memo to the Amateur
Cipher Designer"? If you haven't, you really should. It is worth
reading, and relevant to the topic.
http://www.counterpane.com/crypto-gram-9810.html#cipherdesign
> Concepts of cryptographic hash functions are useful in designing
>custom hash table algorithms, which is a real problem in things like
>routers, etc, with which I am employed as a principal software engineer.
But are you designing custom *cryptographic* hash functions?
I doubt it (and if you are, I'm skeptical that it is a good idea).
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: A generic feistel cipher with hash and gf(257) mixers
Date: 26 May 2001 22:35:23 GMT
Jim Steuert wrote:
>Can you tell me again how you would go about breaking this??
In my preferred notation, the cipher is
E_{k1,k2,k3}(x) = I(H(G(F(x) xor k1) xor k2) xor k3))
where F,G,H,I are fixed invertible non-key-dependent operations.
First, note that F and I are irrelevant. Given a known plaintext
pair (x,y), we can strip them off to produce a known plaintext pair
(x',y') [where x=F(x), y'=I^{-1}(y)] for the following reduced cipher:
E'_{k1,k2,k3}(x) = H(G(x xor k1) xor k2) xor k3
For simplicity of description, I'll describe the attack as an attack
on E', but of course any such attack can be converted into an
attack on the full cipher E (the description gets wordier, but
the complexity of the attack does not increase appreciably).
We can break E' with a meet-in-the-middle attack, as follows.
Suppose we have two pairs of known plaintext, (p,c) and (p',c').
Define functions f and g by f(k1) = G(p xor k1) xor G(p' xor k1),
g(k3) = H^{-1}(c xor k3) xor H^{-1}(c' xor k3). Note that
f(k1) = g(k3).
(Do you see why?) Therefore, the attack can proceed as follows.
Compute g(k3) for every value of k3, and store the result in a
lookup table keyed on the result, so that given z we can quickly
find k3 such that g(k3) = z, if such a k3 exists. This can be done
with 2^32 operations, and the resulting table consumes 2^32 units
of storage. Next, compute f(k1) for each k1 and check whether there
is a solution to f(k1) = g(k3) by looking up f(k1) in the table you
just computed. You expect that when k1 is guessed wrongly, f(k1)
will not exist in the table. Certainly when k1 is guessed correctly,
it will appear in the table, and the correctness of the guess can
be confirmed with a few more trial decryptions (one can recover
k2 via the equation k2 = G(p xor k1) xor H^{-1}(c xor k3)).
So this completely breaks the cipher with 2^32 time and space.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Getting back to the self-study Analysis
Date: 26 May 2001 22:39:24 GMT
In article <[EMAIL PROTECTED]>, Tom St Denis
<[EMAIL PROTECTED]> writes:
>Anyways, not like my original thread didn't go down hill...
>
>Any hints or tips? I am gonna work it out on paper a bit more later
>on... I can't figure out how to exploit the linear relationship
>
>A xor K = B
>A' xor K = B'
>
>(Dave you are not invited into this thread).
>
>Tom
To recover key material, you usually do two things. First, you build a
"distinguisher" for some number of rounds. A distinguisher is a pattern in
the output of the cipher that you wouldn't expect to see in a random
function.
For example, in the original square attack on Rijndael, you would choose 256
plaintexts that differed in only one byte, and then some number of rounds
later (six, I think), you could xor all the plaintexts together and get zero.
This is a six-round distinguisher. One round later that property
disappears.
Second, you recover key material. You go one round later, guess some key
material, compute backwards to the point where the property should hold, and
test the property. When it holds, you know you've guessed right.
In your case, the distinguishing property *never* disappears, so you can
calculate the key directly. Xor the plaintext A with the ciphertext B and
you get the key K.
--
Mike Stay
Programmer / Crypto Guy
AccessData Corp
----- Posted via NewsOne.Net: Free (anonymous) Usenet News via the Web -----
http://newsone.net/ -- Free reading and anonymous posting to 60,000+ groups
NewsOne.Net prohibits users from posting spam. If this or other posts
made through NewsOne.Net violate posting guidelines, email [EMAIL PROTECTED]
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Essay on "The need for a look at real life crypto"
Date: Sat, 26 May 2001 22:47:33 GMT
Ryan Phillips wrote:
>
> "Tom St Denis" <[EMAIL PROTECTED]> wrote in
> news:vGSP6.46752$[EMAIL PROTECTED]:
>
> >
> > "Ryan Phillips" <[EMAIL PROTECTED]> wrote in message
> > news:3b0ff375$1_4@newsfeeds...
> >> Tom St Denis <[EMAIL PROTECTED]> wrote in news:3B0F9EFE.907F2A73
> >> @yahoo.com:
> >>
> >> > Based on my turn about look at computer security...
> >> >
> >> > http://tomstdenis.home.dhs.org/on.pdf
> >> >
> >> > Please comment if possible. Does this hit the mark with what you
> >> > guys are thinking?
> >> >
> >> > Tom
> >> >
> >>
> >> I thought it was a decent essay. The only complaint I have is related
> >> to the PGP paragraph, it is just not about PGP; all public key
> >> algorithms have the problem of identifying and verifying public keys
> >> and certficates issued by users and the CA's.
> >>
> >> If you create a key that has the same username and email of one my
> >> friends keys, and I already know that I have a verified public key on
> >> my keyring (by calling them up and verifying the fingerprint, or them
> >> giving it to me in person), then I'm going to know that the message
> >> sent was with a bogus key and is fradulent.
> >>
> >> There are ways to minimize your risk, but any PKI algorithm has this
> >> drawback.
> >
> > True, I was focusing on PGP because it's a buzzword. Sure there are
> > other PK programs out there that have the same flaws..
> >
> > Tom
>
> Any PK algorithm is potentially insecure. Even SSL can be insecure if
> certificates are issued to the wrong people (ie: microsoft), or rerouting a
> secure connection to a hostile host.
Again you're missing the point. The essay is about trusting buzzwords.
I picked on PGP because it's a buzzword. Nobody says "I use the
AcornSoft PK to sign my message".
And yes I pick on SSL (indirectly) in my essay too.
Tom
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: DES Crypto Myth??
Date: Sat, 26 May 2001 22:48:31 GMT
[EMAIL PROTECTED] wrote:
>
> Tom St Denis wrote:
> >
> > "Mok-Kong Shen" <[EMAIL PROTECTED]> wrote in message
> > news:[EMAIL PROTECTED]...
> > >
> > >
>
> > Bingo. Schneier said it well in AC2. [paraphrasing now since AC2 is all
> > the way on the bookshelf...] "Anyone can design a secure block cipher with
> > 128 rounds and a 512-bit key ...".
>
> > Tom
>
> It's funny how many Schneier quotes I've seen since I've been following
> this
> newsgroup. (BTW, ever read what he said about USENET crypto posts? )
> :)
>
> Of course, I'm not qualified to make a judgment since he is a
> professional
> cryptographer and I am not, but I'm curious as to why he seems to speak
> for
> the entire crypto community (ok, I'm exaggerating a bit but look at how
> many
> times he gets quoted in this newsgroup). AC is a very good and easy to
> read
> overview of many different aspects of crypto, but if you'll look
> carefully at
> the number of references in the back of the book you'll realize that AC
> is
> just a summary of the work of a LOT of researchers. Plus, there's very
> little
> mathematical meat in it. AC was fun to read and its a popular crypto
> book, but
> I think my reading time was better spent with HAC. Why is Schneier such
> a
> popular cryptographer? Is it charisma or is he a real innovator
> (compared
> to other professional cryptographers)?
>
> Before posting any flames re-read the line "...I'm not qualified to make
> a
> judgment..." :) Just curious...
I paraphrase what he says alot because it just makes sense...
Tom
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: A generic feistel cipher with hash and gf(257) mixers
Date: 26 May 2001 21:01:41 GMT
[EMAIL PROTECTED] (David Wagner) wrote in
<9ep5an$omc$[EMAIL PROTECTED]>:
>SCOTT19U.ZIP_GUY wrote:
>> This GGR you've been talking about. Does it add information to
>>the encryption that could help an attacker.
>
>No.
>
>>Can any file be considered a possible valid output.
>
>Yes.
>
Well then I would have to test it. Many at first think
they have a fully bijective program but they don't.
Do you have a place where the source code can be down loaded.
You can find a link to BICOM at my site. I would not mind
testing your GGR to see if its fully bijective.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged or
something..
No I'm not paranoid. You all think I'm paranoid, don't you!
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Good crypto or just good enough?
Date: Sat, 26 May 2001 22:51:20 GMT
Bryan Olson wrote:
>
> Tom St Denis wrote:
> >
> > Bryan Olson wrote:
> [...]
> > > Today, crypto has two serious problems:
> > > 1. We don't really understand complexity.
> > > 2. The world runs on cleartext.
> > >
> > > Sci.crypt is flooded with conjectural ideas for symmetric
> > > encryption, and endless debate over 3DES vs Rijndael vs
> > > combining 17 different ciphers. None of that addresses any
> > > problem anyone actually has.
> >
> > Maybe Academia should swing vines over to more practical problems then?
>
> Academia is doing reasonably well.
>
> > After thinking about it I think alot of block ciphers are not too far
> > away from "Security by Obscurity." If you think about it the only thing
> > that makes Twofish (for example) secure is the requirement for us to
> > mount a brute force attack. there is no proof of the inability to mount
> > a shortcut attack though...
>
> What does this thinking imply about inventing a flood of
> new ciphers with even less security justification than
> Twofish?
What are you talking about?
Tom
------------------------------
** 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
******************************
