Cryptography-Digest Digest #456, Volume #14 Sun, 27 May 01 09:13:00 EDT
Contents:
Re: A generic feistel cipher with hash and gf(257) mixers (Tom St Denis)
Re: Good crypto or just good enough? (Stefan Lucks)
Re: To prove PGP can easily be misused... (Mok-Kong Shen)
Re: To prove PGP can easily be misused... (Tom St Denis)
Re: Good crypto or just good enough? (Tom St Denis)
Re: Newbie question about algo (Martin Kiewitz)
----------------------------------------------------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: A generic feistel cipher with hash and gf(257) mixers
Date: Sun, 27 May 2001 11:22:23 GMT
Jim Steuert wrote:
>
> Thanks David,
>
> I understand your proof. It is very clear. I now understand
> meet-in-the-middle
> attacks. I now ask whether one of these fixes is worthwhile:
>
> a) Use at least one more key part, and blend it in. The attack is thus
> on =>(xor k1)=>H=>(xor k2)=>J=>(xor k3)=>K=>(xor k4)=>
> The mitm attack would generate the set of k2(1 per k1) and
> the set of k3(1 per k4). However, the set after J would
> be of order k3(1 per (k1,k2)) or 2^48 And by breaking the key into
>
> more parts, the order could be made even higher.
>
> b) Re-use the parts of the key at the various stages, so that at each
> stage i, the key itself (ki) is a 32-bit wide hash si of the
> entire original key,
> but xor'ed with only one of the 3 digest-width variables.
> You had implied this in your statement "since you are only using
> each part of the key once"... This should prevent intersections.
>
> While the original specification of my cipher was flawed, is there
> anything fundamentally wrong with the methodology or recipe, given those
> (important) fixes, to generate a reasonable cipher? I''ll rephrase the
> methodology or recipe or class of ciphers as:
>
> A) Use multiple stages (at least 5) of invertible hashes H,J,K,L,M,...
> B) Form at least 5 different derived keys d1,d2,d3,d4,d5, using
> 5 "different" 32-bit-output compression hashes of the entire key.
> C) After each stage, blend in a part of a derived key mixed in via
> partial-width
> xor (or some other invertible mixer) in. By partial width is
> meant
> xoring with only one out of three of the full digest
> variable width (say, with just digest variable b out of (a,b,c)
> ).
> D) Shake, Stir and Serve (just kidding)
>
> My main point is that there can be simple recipes, this being one of the,
> that if followed, will provide a reasonable cipher, and still provide lots
>
> of room for creativity. I certainly erred, and got corrected on some
> of the recipe steps.
Do you mind if I make a suggestion? Why not look at how efficient block
ciphers are designed. You are just doing the muddle-security approach
here. Oh you broke 3 rounds, I will add 5 more and swap this, and add
that, and ...
Even if you resist David's attack nobody will care because a) It's
inefficient and b) It's too messy.
If you read up papers say of the Rijndael or RC6 you will see how
elegant designs are made.
This is not to say you can't design your own cipher, by all means go
ahead, but try to design a cipher you could imagine yourself actually
using.
Tom
------------------------------
From: Stefan Lucks <[EMAIL PROTECTED]>
Subject: Re: Good crypto or just good enough?
Date: Sun, 27 May 2001 13:32:45 +0200
On Fri, 25 May 2001, Tom St Denis wrote:
> Would you settle for crypto that is "just secure enough" or "is as
> secure as we know how to make it". Both within reason.
Neither. I would look at the following points:
1. The threat model. What do you want to protect against?
2. How would a minimal application look like which protects against the
threat model.
3. How expensive (in terms of money, speed, ...) would such a minimal
application be.
4. What can I do to make the application more secure without greatly
increasing the costs. (This is some "over-design", compared to the
initial threat model.)
5. How stable is the threat model? That means, if an application based
on the initial thread model is implemented, how soon may the point
come where users need an extended thread model.
(* Most of the time, users forget about the initial thread model and
continue to use an application when their security requirements
have changed.
*)
6. If the threat model is unstable, how can we extend the thread model
and provide an application at not too much additional costs?
I have recently seen an application where people encrypted their
plaintexts using triple DES in OFB mode. As it turned out, what they
really wanted was authentication, and they actually did not care much
about confidentiality. So using a single DES based CBC-MAC would have been
much better than encrypting under triple DES.
Higher security (under reasonable assumptions) is much cheaper in
cryptography than in almost all other areas of computer security. In
general, "over-design" is expensive and bad design. But, if you need a 64
bit block cipher, triple DES is only 3 times slower than single DES, and
nobody (in the open cryptographic community, at least) knows how to
practically break triple DES. If triple DES is really too slow, you may
consider using Blowfish, Cast, or IDEA (instead of single DES). All these
are 64-bit block ciphers which have been studied intensively for years,
and (public) cryptanalysis is far from breaking them.
Reconsidering the application mentioned above again, if they switch to
using a CBC-MAC, speed is not more an issue than before (or rather, speed
is a big issue, but it is the transmission speed of ciphertexts that
matters, not the speed of the block cipher), so using single DES instead
of triple DES (or perhaps Blowfish or ...) would be foolish.
Also, if speed constraints are not too hard, they should continue to
encrypt their plaintexts. Else, some time in the future, they may require
confidentiality too, and then they have a system running to "magically"
provide authenticity and sends the plaintexts un-encrypted over an
insecure channel. If their system was over-designed at first by using
encryption in addition to using a MAC, it may now continue to meed their
security requirements. Otherwise, they may have to modify their existing
system (this can be very expensive), or they continue to use a system
which is insecure with respect to their new security requirements.
> Of course I agree with him that block ciphers are not magical and can't
> prevent against all attacks, but does it not stand to reason to pick the
> best tools from each field? Why settle for lame tools that open doors
> to attacks that can easily be shut?
When it comes to using block ciphers, and assuming there are no very
limiting constraints about speed or (for hardware implementations) gate
count, a "good" block cipher ("good" as far as we know today) is not
significantly more expensive than a "bad" block cipher. So (with the above
exception) choosing a "bad" block cipher is bad engineering practice, even
if that "bad" block cipher seems to be just about "good enough" for the
current application.
--
Stefan Lucks Th. Informatik, Univ. Mannheim, 68131 Mannheim, Germany
e-mail: [EMAIL PROTECTED]
home: http://th.informatik.uni-mannheim.de/people/lucks/
====== I love the smell of Cryptanalysis in the morning! ======
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: To prove PGP can easily be misused...
Date: Sun, 27 May 2001 13:37:10 +0200
Tom St Denis wrote:
>
> Hmm might not be news to you, but think about this. What if some
> politician happened about this and decided to trust it without
> confirmation? Ouch... bad news...
High-ranking politicians are supposed to have people
knowledgeable in security working for them to take care
of the privacy of their communications.
M. K. Shen
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: To prove PGP can easily be misused...
Date: Sun, 27 May 2001 11:44:53 GMT
Mok-Kong Shen wrote:
>
> Tom St Denis wrote:
> >
> > Hmm might not be news to you, but think about this. What if some
> > politician happened about this and decided to trust it without
> > confirmation? Ouch... bad news...
>
> High-ranking politicians are supposed to have people
> knowledgeable in security working for them to take care
> of the privacy of their communications.
Ok what if something like E-SIGN becomes a common day law. Walk to your
local mall and honestly tell me you could picture all of those people
knowledgeable about how a digital signature works or can be exploited.
The problem is not with the techies... sure we may know how to use this
properly (that I doubt too now that I think of it) but the millions of
non-techies that explicitly trust others...
Tom
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Good crypto or just good enough?
Date: Sun, 27 May 2001 11:47:28 GMT
Stefan Lucks wrote:
>
> On Fri, 25 May 2001, Tom St Denis wrote:
>
> > Would you settle for crypto that is "just secure enough" or "is as
> > secure as we know how to make it". Both within reason.
>
> Neither. I would look at the following points:
> 1. The threat model. What do you want to protect against?
> 2. How would a minimal application look like which protects against the
> threat model.
> 3. How expensive (in terms of money, speed, ...) would such a minimal
> application be.
> 4. What can I do to make the application more secure without greatly
> increasing the costs. (This is some "over-design", compared to the
> initial threat model.)
> 5. How stable is the threat model? That means, if an application based
> on the initial thread model is implemented, how soon may the point
> come where users need an extended thread model.
> (* Most of the time, users forget about the initial thread model and
> continue to use an application when their security requirements
> have changed.
> *)
> 6. If the threat model is unstable, how can we extend the thread model
> and provide an application at not too much additional costs?
This sounds very reasonable. BTW Are you a pascal programmer?
> I have recently seen an application where people encrypted their
> plaintexts using triple DES in OFB mode. As it turned out, what they
> really wanted was authentication, and they actually did not care much
> about confidentiality. So using a single DES based CBC-MAC would have been
> much better than encrypting under triple DES.
For authentication I would have used a hash first ...
> Higher security (under reasonable assumptions) is much cheaper in
> cryptography than in almost all other areas of computer security. In
> general, "over-design" is expensive and bad design. But, if you need a 64
> bit block cipher, triple DES is only 3 times slower than single DES, and
> nobody (in the open cryptographic community, at least) knows how to
> practically break triple DES. If triple DES is really too slow, you may
> consider using Blowfish, Cast, or IDEA (instead of single DES). All these
> are 64-bit block ciphers which have been studied intensively for years,
> and (public) cryptanalysis is far from breaking them.
>
> Reconsidering the application mentioned above again, if they switch to
> using a CBC-MAC, speed is not more an issue than before (or rather, speed
> is a big issue, but it is the transmission speed of ciphertexts that
> matters, not the speed of the block cipher), so using single DES instead
> of triple DES (or perhaps Blowfish or ...) would be foolish.
>
> Also, if speed constraints are not too hard, they should continue to
> encrypt their plaintexts. Else, some time in the future, they may require
> confidentiality too, and then they have a system running to "magically"
> provide authenticity and sends the plaintexts un-encrypted over an
> insecure channel. If their system was over-designed at first by using
> encryption in addition to using a MAC, it may now continue to meed their
> security requirements. Otherwise, they may have to modify their existing
> system (this can be very expensive), or they continue to use a system
> which is insecure with respect to their new security requirements.
My original point was "within reason". If you had to pick between DES
and Rijndael which would you choose? (Assuming all else is equal which
admitedly doesn't happen ever)
> > Of course I agree with him that block ciphers are not magical and can't
> > prevent against all attacks, but does it not stand to reason to pick the
> > best tools from each field? Why settle for lame tools that open doors
> > to attacks that can easily be shut?
>
> When it comes to using block ciphers, and assuming there are no very
> limiting constraints about speed or (for hardware implementations) gate
> count, a "good" block cipher ("good" as far as we know today) is not
> significantly more expensive than a "bad" block cipher. So (with the above
> exception) choosing a "bad" block cipher is bad engineering practice, even
> if that "bad" block cipher seems to be just about "good enough" for the
> current application.
There are no "good" block ciphers, just "less badder". If we can break
cipher X and not Y then Y is not as bad as X.
Tom
------------------------------
From: [EMAIL PROTECTED] (Martin Kiewitz)
Subject: Re: Newbie question about algo
Date: 27 May 2001 05:59:30 -0700
[EMAIL PROTECTED] (Roger Fleming) wrote in message
news:<[EMAIL PROTECTED]>...
Hi Roger !
> [EMAIL PROTECTED] (Martin Kiewitz) wrote:
> >I'm somehow a newbie to cryptology and i'm just building some stream
> >encryption algorythmn.
> First, it's great fun to invent your own algorithms and try to attack them,
> but for serious purposes it is rarely a good idea. Even if someone on this
> group hadn't noticed any problems with your proposal, the 30 minutes of
> examination it received is hardly equivalent to the years of expert analysis
> that have gone into something like SSL.
I just wanted to show someone, who actually knows somethings about
cryptology.
> >I don't want flames, please. I'm posting this, so other people can
> >post their opinions about it.
> You won't get any flames - yet. Be aware, however, that there is a strange
[...]
> flame war, when in fact they are themselves the sole cause of the trouble.
That wasn't the reason for writing this. I wanted to show that i'm a newbie
and if I get something wrong, that I don't to make flame war either.
It's somehow like saying that I'm not knowing everything and perhaps
I'm thinking wrong.
> Also, as soon as you see some attacks on your system, your instinct will be to
> patch the algorithm and publish the new version, then repeat the process until
> the algorithm has become complicated enough no-one wants to examine it in
> their spare time, and the inventor claims to have produced a strong algorithm.
> Doing so is extremely dishonest, since others have done all the real work.
That wasn't my thought either. <g> That's probably Microsofts way of
doing things ;)
> >I want to encode a duplex-stream (named pipes, tcp-connection, etc.)
> >using a really fast and safe algorythmn.
> Not surprisingly, others have had this problem before, and already solved
> it. Look for the openssl library, and you will find nearly all the code
> already written for you.
Is OpenSSL available for PC-DOS, too ? I need an implementation for
IBM's TCP/IP for DOS Stack. Additionally I will need some ISDN/Modem
implementation and no, I don't use SLIP/PPP for those things.
I'm not being dumb, because I use special simplified protocols for
e.g. exchanging mail only from an "open-to-the-internet" system to
an isolated server. So there is no way for an intruder to enter.
It's not possible. I believe I will just use SMTP for transfer, but
use ISDN/Modem/whatever just for one "socket" without TCP/IP.
And that's my problem, too. I would need an SSL implementation on
various locations and I believe most of them are not available, so
I would have to do much, much work.
Is SSL really complex or is it an easy to use algo ?
Porting OpenSSL to some interfaces is almost impossible, because I
use a special interface for transmitting data and it's written in
100% assembly. (No flames about this, please)
> >Server decrypts LoginData & Crypto Hash with its own secret key.
> >Now server sends unencrypted (raw) success of login. (that's done, so
> >no byte guessing can take place).
> >Server sends terminal operations, till actual interactive use needs to
> >be done by client. (actually till Server thinks Crypt is needed).
> OK, there are a couple of problems with this.
Sh*t yeah. I know already ;)
I knew this method of attacking, when writing it and I had something
in mind to keep an attacker of it.
> table as the user's last session. I can repeat commands he sent last time
> (might be useful sometimes), send random commands (he will get blamed if it
> causes any damage), or - if I managed to break his last encryption table -
but, no. sending random commands is not possible, because the encryption
is not reset on every paket. I mean when connecting it starts on pos 0,
but that's it.
> control the machine using his ID. All this without even having to guess his
> password or username, never mind breaking the public key stuff.
The other thing I got my mind on was session hijacking.
But that's a problem to SSL, too ??!!
> Second, there is no verification of the server to the user. Anyone could send
> you the server's public key, and you won't know you're talking to an imposter
But that's okay, because the client encrypts its data with the public
key, so only the actual server is able to decrypt it.
I thought of man in the middle attack, too and got the idea of including
the MAC adress of the server in the IP-paket (for TCP/IP implementation).
Or how would you prevent it ? Is this a problem of SSL, too ?
I mean, I could get into an SSL session, too and send the data from
the client to the actual server and back. Is there some way to
circumvent it under SSL ?
> until the server is forced to encrypt some data and you notice that it's
No. The client encrypts data. The server just sends his key and decrypts
incoming data.
> gibberish. If the "user" is an automatic process, it might never notice. If
> the server can always choose not to encrypt data (which you suggest might be
> the case), even a human will never notice. So, it's a good idea to,
> immediately after the key exchange, do a transaction that proves each side
> knows the key.
But that's it. The server is only able to decrypt the data from the client.
I cannot do much more. The client would have to generate his own
public key on the fly, which is not acceptable on each session,
because it needs time. Using one key would be stupid, because
an attacker in-house could get the key and use it furthermore.
> Third, you've completely omitted the important detail of how all this data
> will be structured. This is quite an important detail as I can think of
[...]
I wanted to generate one PGP encrypted data paket and send it via
TCP/IP directly. (TCP/IP would split the paket in multiple IP subpakets)
> Finally, you don't discuss how you create the "Crypto Hash", which is pretty
> important. (Later you say 'both are "true" randomized numbers'. Do you mean
> you use a hardware random number generator to generate 2 kB (16, 384 bits) of
> truly random data for each logon? This would be incredibly slow, and is a
> wasted effort since Scott Fluhrer's attack shows that all the initial
> randomness quickly leaks away, and is replaced solely by randomness from the
> input stream.)
They will be generated by the keystrokes the user enters at begin
of the software (pre-login, perhaps). So everytime they will be
actually different. (same as PGP Public Key generating)
(not actually by the keystrokes, but by the time between them)
> There may be other problems; these are just a few I noticed straightaway.
> Designing authentication and key exchange potocols is quite tricky; you are
> well advised to use an existing, proven one - such as SSL!
I know, I should have mentioned more in my first mail.
> >In and Out Stream, both have 2Kbyte Hash, both are generated by client
> >and both are "true" randomized numbers.
> >I suppose: CurPos = 0 (at begin of en/decryption)
> >To encode:
> > 1. EncodedChar = OrgChar xor Hash[CurPos]
> > 2. Hash[CurPos] = Hash[CurPos] xor EncodedChar
> > 3. CurPos = CurPos+OrgChar
> > 4. CurPos is cut down to 2k range
> > 5. Encode further data
> >Decoding is performed accordingly.
> >Is this algo good ? Is it breakable ?[...]
> OK,Scott Fluhrer already pointed out a very serious problem, but I noticed a
> neat little demonstration that shows just how severe that problem is. Because
> of the problem that Scott noticed, if an input character is a 0, then the next
> character is always output in plaintext!
you mean the Hash-character ? Yes, that's typical for XOR.
But sending one char plain-text is not that problem, because a
listener would not know what char is plain-text. Having a hash full
of zeros would be stupid, but that's clear ;-)
> Suppose the input stream is in Unicode but the Latin character set. Then every
> second character is a 0, so all the significant characters are output in
> plaintext!!! Each plaintext character is separated by one completely exposed
> table value so after such a Unicode input is maintained for about 2kb, the
> attacker trivially can see the entire contents of the table, and continue
> decrypting even if further input is more irregular.
Hmmm, for fixing that I would do an additional table for incrementing
CurPos, instead of reusing Hash. Or using both, the additiona table
and the hash.
> I think you will agree that a cipher which, when given a plaintext with
> certain commonplace structures, does no encryption at all but instead outputs
> the plaintext _and_ the key, has a fatally serious flaw. Don't tell yourself
> "well, I just won't use Unicode"; the problem is much further reaching than
> that, this is just a nice demonstration of it.
You are right. I will just think it all over, but I will prefer using a really
simply algo, which is nearly good instead of using SSL.
That's not because I think SSL is not good, but implenting a simple
algo with about 4 assembler ops per char is faster and easier to
implement then SSL. I think of implementation errors, too.
> Have a look at RC4. It's unencumbered (except the name, which is trademarked),
> only about as complicated as your existing cipher, about as fast, uses less
> memory, and is much stronger. It is also built into - you guessed it,
> openssl.
That's a good idea. Where can I find some really good documentation ?
Could you please provide some link ?
Thanx
Perhaps I will use RC4, but staying with my method generating the hash
(which is actually good, i guess).
cu Kiewitz
------------------------------
** 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
******************************
