Cryptography-Digest Digest #957, Volume #8 Sat, 23 Jan 99 22:13:03 EST
Contents:
Re: Strong Encryption for 8086 (16 bit) (fungus)
Re: UK TV programme on Enigma (Withheld)
Re: Metaphysics Of Randomness (R. Knauer)
Re: Please help. Need protocol advice. (Dale R Worley)
Re: Cryptanalysis of Simple Block Ciphers (Dale R Worley)
Re: The Performance of Meet-in-the-Middle (Bryan G. Olson; CMSC (G))
Re: Who will win in AES contest ?? (John Savard)
Re: 3DES in EDE mode versus EEE mode ([EMAIL PROTECTED])
All 8 modes, was Re: 3DES in EDE mode versus EEE mode ([EMAIL PROTECTED])
Re: Please help. Need protocol advice. ([EMAIL PROTECTED])
Re: Metaphysics Of Randomness (Phillipe Guapo)
Re: Please help. Need protocol advice. ([EMAIL PROTECTED])
Re: 3DES cracked in 22 hours ??? (Was: Re: (fwd) DES Challenge III Broken in Record
22 Hours !) (Brad Templeton)
----------------------------------------------------------------------------
From: fungus <[EMAIL PROTECTED]>
Crossposted-To: comp.lang.asm.x86
Subject: Re: Strong Encryption for 8086 (16 bit)
Date: 23 Jan 1999 23:55:09 GMT
"Arthur N. Klassen" wrote:
>
> Andrew Lord wrote:
> >
> > I'm looking for a *strong* encryption algorithm...
> > ...
> > Or [it would be nice if someone] can recommend an
> > algorithm that is the easiest to implement on a 16bit processor.
>
> Consider using the CipherSaber algorithm, described at
> http://ciphersaber.gurus.com
I'll second that. It'll be a cinch to do it in 8086 assembler.
> It's biggest drawback for your situation would be that it leaves the
> generation of the 10 random bytes up to you. But that shouldn't be too
> hard. I believe there are a number of random number generation algorithms
> documented and rated for relative strength at counterpane.com.
>
The ten random bytes don't have to very random, just different for every
file. Even two bytes of randomness will work good (but your chances of
reusing the same two numbers is only 1 in 65536). In a program I wrote
I used a hash of the current time and the name of the file being
encrypted. If you want a cheap hash algorithm (reusing your existing
code), feed this info into the RC4 generator, then use the first ten
bytes of output as the IV for the actual encryption.
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: Withheld <[EMAIL PROTECTED]>
Subject: Re: UK TV programme on Enigma
Date: Fri, 22 Jan 1999 21:05:41 +0000
Reply-To: Withheld <[EMAIL PROTECTED]>
In article <[EMAIL PROTECTED]>, Michael Josefsson
<[EMAIL PROTECTED]> writes
[headers cut]
I found the book "Between Silk and Cyanide" a very interesting read too
- it's about the code war with Nazi Germany. It's more autobiographical
than technical but very well written - I went to bed almost expecting
the Gestapo to kick down my door!
>>>UK TV Channel 4 is showing 'Station X' on Tuesday 19th January at 9:00pm.
>>>It's about breaking the Enigma code which was done, according to the trailer,
>>>by chess champions and crossword fanatics.
>
>>You might also find the book to accompany the series of interest:
>
>>Station X, The codebreakers of Bletchley Park.
>>by Michael Smith,
>>Pub. 1998 by Channel 4 books (an imprint of Macmillan books)
>>ISBN 0-7522-2189-2 (Hbk, UKP 14.99)
>
>And David Kahn's book on ENIGMA. That was a fascinating read!
>
>>p.s.
>>Just a happy reader - having no connection with Channel4, the author, or
>>the publishers ;-) but looking forward to the series.
>>--
--
Withheld
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Metaphysics Of Randomness
Date: Sat, 23 Jan 1999 23:30:53 GMT
Reply-To: [EMAIL PROTECTED]
On Sat, 23 Jan 1999 05:59:09 -1000, Boson <[EMAIL PROTECTED]> wrote:
>Too bad you came up with bullshit.
Every once in a while some cretin like this butthead leaves cyberpunks
and ventures into sci.crypt.
Bugger off, moron.
<plonk>
Bob Knauer
"It is not the function of our government to keep the citizen from
falling into error; it is the function of the citizen to keep the
government from falling into error."
--Justice Robert H. Jackson
------------------------------
From: [EMAIL PROTECTED] (Dale R Worley)
Subject: Re: Please help. Need protocol advice.
Date: Sun, 24 Jan 1999 01:14:17 GMT
As far as I can tell, your problem is that (1) you want the server to
dispense sensitive data to legitimate clients, but (2) the adversary
can completely reverse-engineer clients, e.g., produce pseudo-clients
that behave (w.r.t. the protocol) *in every way* like a legitimate
client.
Under these conditions, there is no solution. After all, in what
manner is the client going to authenticate itself to the server?
Authentication can be done by something that one has, that one knows,
or that one is, but you've assumed that the adversary can duplicate
all that.
The only solutions that I know of are ones that contain
self-destructing hardware that contains both a key of some sort and
the crypto processor that uses that key to produce the authenticating
messages. Attempts to open the box cause the key to be destroyed. In
this way, the client knows something that the adversary cannot obtain.
Dale
Dale Worley [EMAIL PROTECTED]
--
Miss Manners starts from the idea that all society is potentially
cruel, as it depends on personal and therefore capricious tastes; that
society involving courtship is doubly so, and society involving
adolescents is unspeakably so.
------------------------------
From: [EMAIL PROTECTED] (Dale R Worley)
Subject: Re: Cryptanalysis of Simple Block Ciphers
Date: Sun, 24 Jan 1999 01:17:58 GMT
In article <78d1hk$4id$[EMAIL PROTECTED]> [EMAIL PROTECTED] (James Pate
Williams, Jr.) writes:
Does anyone have any simple 8-bit
block ciphers that are marginally (or perhaps) better than the
simple xor cipher
Try addition mod 256, it's just slightly nonlinear when viewed
bitwise. After that, you can (I think) use multiplication mod 257 of
the integers 1...256, a la IDEA.
Dale
Dale Worley [EMAIL PROTECTED]
--
If there are no Platonic ideals, then what did we fight for?
-- a Spanish Republican
------------------------------
From: [EMAIL PROTECTED] (Bryan G. Olson; CMSC (G))
Subject: Re: The Performance of Meet-in-the-Middle
Date: 24 Jan 1999 01:21:59 GMT
[EMAIL PROTECTED] wrote:
: The meet-in-the-middle attack (MITM) provides an important time-memory
: tradeoff when attacking a product cipher. As it is commonly described, it
: is based on a tacit assumption which fails in the general case. While it
: is *still* true that for DES and similar ciphers, only O(2^(k+1)) time
: complexity is required to determine the key, certain conditions need to be
: met for this to happen. The two most comprehensive crypto references, HAC
: [1] and AC [2] seem to gloss over this subtlety (or perhaps did not
: anticipated it at all).
: Counterexamples are presented in [3] and [4], where even granting the
: storage requirements of MITM, nearly O(2^(2k)) time complexity is required
: to determine key. In other words, after buying all that memory, you may
: still end up with an exhaustive key search.
: I refer readers to [4] for further detail, but let me state what the
: subtlety boils down to. Here is MITM for an attack against product XY
: where the adversary has a plaintext-ciphertext pairs (p,c):
: FOR Ky in the keyspace of Y DO
: Write (Ky, E(Ky,p)) to a table indexed by E(Ky,p).
: DONE
: FOR Kx in the keyspace of X DO
: Use D(Kx,c) as an index to retrieve (Ky', D(Kx,c)).
: IF E(Kx,E(Ky', *)) is the correct product THEN
: return (Kx,Ky').
: ENDIF
: DONE
: The problem is that there may be multiple Ky in the keyspace of Y which
: encrypt p to the same intermediate message block.
To solve for the key at all, we must have sufficient pairs to
cover the unicity distance. Instead of filling the table with
single blocks we could use enough blocks to cover the unicity
distance. We then expect the procedure to return only the
correct key. Of course we expect the unicity distance for
double encryption is twice to be twice that for single
encryption, so we need another factor of two in work and
memory.
In practice, that's probably not the best way. If the table
entries are just enough text to cover the single-encryption
unicity distance (which for a random cipher and known plaintext
is about the size of K), then the expected number of false
matches for each key is one.
: This situation is far
: from a pathological case, and in fact can be proven to be desirable for
: secure block ciphers [3]. When it happens, one must add an additional
: for-loop nested within the second for-loop to check the multiplicity of
: candidates, Ky'. Of course, inserting this additional for-loop will change
: the expected performance of the attack. This new expected time complexity
: T can be shown to be bounded by
: W(XY|c,p) <= T < 2^(2k),
: where W(XY|c,p) is the conditional guesswork of the product (conditional
: ``guessing entropy'' if you like), and where each component has k key
: bits.
Under the random cipher model, we expect to suffer by only a small
constant, around 2. I'm not familiar with all the notation used
on the web site, but I understand it presents an example cipher
for which which meet-in-the-middle really would take about 2^(2K).
The example is unsatisfying because it seems that the structure
makes it vulnerable to much better attacks.
Can anyone suggest a cipher that slows down meet-in-the-middle by
by making the inner for loop long, that does not also induce
weaknesses?
: [3] John Pliam, Ciphers and their Products: Group Theory in Private Key
: Cryptography, PhD in preparation, 1999.
: URL: http://www.ima.umn.edu/~pliam/doc
: [4] ___, section 6.5 of [3], "About the MITM Attack".
: URL: http://www.ima.umn.edu/~pliam/doc/mitm.ps.Z
--Bryan
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Who will win in AES contest ??
Date: Sun, 24 Jan 1999 00:16:18 GMT
Robert Harley <[EMAIL PROTECTED]> wrote, in part:
>Why do you think it would be Twofish? Because Bruce Schneier wrote a
>very popular book? Twofish is quite a complex, non-obvious cypher. No
>offense intended to its inventors, but I don't think it is a
>"front-runner".
Myself, I see Twofish and MARS as among the front-runners. Twofish was
*very* carefully thought out for efficiency on a wide variety of
platforms, including smart cards, and that is its ticket.
Serpent has its inventor's academic reputation behind it. There are
quite a few other good designs, and I'm not at all sure which other
ones will be front-runners.
I think, though, that it is a pity that they must choose one
algorithm...because each of the algorithms could be improved with
ideas from other algorithms. (Have a peek at my "Quadibloc II" design
which was formed, magpie-like, from ideas found in several AES
candidates - although it was also based on the original Quadibloc,
which predated the AES process.)
Also, a crack was found for Magenta in short order - but its
weaknesses stem from its key schedule, and possibly its S-boxes (which
are about the simplest possible nonlinear ones) - which could be
corrected without affecting its efficiency. Its basic design seems
quite strong.
John Savard
http://www.freenet.edmonton.ab.ca/~jsavard/index.html
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: 3DES in EDE mode versus EEE mode
Date: Sun, 24 Jan 1999 01:34:01 GMT
In article <78b7b0$tmg$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> [EMAIL PROTECTED] wrote:
>
>> When just one key is used in 3-DES EDE, key schedule cannot be simply
>> repeated 3x in exaustive key search, which affords a slightly higher workload
>> per searched key than EEE in specialized hardware (and in software, of
>> course) that could pre-compute the key schedule just once for all 3x.
>
> Did I miss something? One key encrypt-decrypt-encrypt is equivalent
> to a single encrypt. If I'm testing keys to break 1-key EDE, of course
> I'm going to run encrypt, not encrypt-decrypt-encrypt.
>
Bryan:
You are correct -- however *if* the attacker knows it is a one-key 3-DES that
can be attacked as a 1-DES.
But, as NIST proposes, 1-DES will be phased out and 3-DES will coexist with
AES -- for a long time. However, if Bob and Alice negotiate a 3-DES protocol
and Alice receives 3x the same key from Bob (encoded with AOEP-RSA under
different seeds, so the three ciphertexts are different) then there is no way
for an attacker to know that Bob and Alice can be attacked just with one-key
1-DES (as you suppose). Effectively, the attacker must suppose that either
one, two or three keys may be in use -- and devise an attack that is general
enough to the perceived threat that 3-keys may be used. Then, the mentioned
"slightly higher workload" would have an influence.
Cheers,
Ed Gerck
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED]
Subject: All 8 modes, was Re: 3DES in EDE mode versus EEE mode
Date: Sun, 24 Jan 1999 01:28:47 GMT
In article <78ask9$ker$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> In article <788ill$kuu$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
> >...
> >When just one key is used in 3-DES EDE, key schedule cannot be simply
> >repeated 3x in exaustive key search, which affords a slightly higher workload
> >per searched key than EEE in specialized hardware (and in software, of
> >course) that could pre-compute the key schedule just once for all 3x.
>
> I think this incorrect. Each bit of the key expansion of DES has the value of
> one bit of the key. This means that in hardware the workload for computing
> the key expansion of DES is zero (you connect a wire to a position of the
> key). The fastest implementations of DES in software use bit-slice where the
> same is true.
>
Dianelos:
DES takes one 56-bit encryption key K and generates sixteen 48-bit subkeys Ki,
one for each DES round. For decryption, either the sixteen Ki are used in
reverse order or they are directly generated in reverse. The ordering reversal
is the slight overhead I mentioned. However, please see Bryan Olson's comment
and my reply to him.
This "slight overhead" can be exemplified in a perhaps typical near-future
scenario. As NIST proposes, 3-DES will coexist with AES -- for a long time.
However, if Bob and Alice negotiate a 3-DES protocol and Alice receives 3x
the same key from Bob (encoded with AOEP-RSA under different seeds, so the
three ciphertexts are different) then there is no way for an attacker to know
that Bob and Alice can be attacked just with one-key 1-DES (as Bryan
supposed). Effectively, the attacker must suppose that either one, two or
three keys may be in use -- and devise an attack that is general enough to
the perceived threat that 3-keys may be used. Then, the mentioned "slight
overhead" would have an influence.
This reminds me of strategy in chess, where most of the threats are not
carried out -- but surely influence the game and make the opponent lose time.
In this sense, it would be perhaps useful to consider an alternative 3-DES
Standard, where all 8 combinations (EEE, EED, DDE ... DDD) would be allowed
and *post-selected* by the sender, Bob, after algorithm negotiation (3-DES).
So, Alice would have the right key(s) from Bob (eg, send by AOEP-RSA), but
she would have to test the first DES block to see which scheme was randomly
chosen by Bob -- for which she may need to try out one block at most eight
times, to be sure. An attacker, however, would need to try out an average of
four blocks but each one with an average of half the corresponding key-space,
for each possibility of one, two and three keys. Which would at least
multiply by 4x the average attack workload for 1-DES due to the combination
uncertainty of EEE .. DDD.
Comments?
Cheers,
Ed Gerck
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Please help. Need protocol advice.
Date: Sun, 24 Jan 1999 02:50:55 GMT
> You stated that you wanted to keep the encrypted data froma
malicious
> client. I suspect you meant the unencrypted data. The question is, what do
you
> want friendly clients to do that malicious clients cannot do?
I want my friendly clients to be able to generate session keys or other such
computations, while malicious clients should not be able to generate valid
keys.
Don't ask me .. I'm still trying to figure out what standards I'm
dedicated to as a nonconformist.
...by the way, where are we going? And why am I in this handbasket?
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: Phillipe Guapo <[EMAIL PROTECTED]>
Subject: Re: Metaphysics Of Randomness
Date: Sat, 23 Jan 1999 18:51:36 -1000
You can get random numbers at the following website:
http://www.fourmilab.ch/hotbits/
Here is an example of their donation:
"Here are your HotBits!
The following hexadecimal data are the random bytes you requested.
These data were generated by the Fourmilab HotBits
radioactive random number generator.
331FCD7F49136C3F6359B50BDA5FED8FB11053FC22B65D74C0E248E71BA24727
1C9AC186D7C20CD930E0E9CB1CE66C6FFF73DA8A0DA202C7D3FA1079BE3CCFFA
0A72450A1E5C20B9F8B7F845C6C34A69A4B3950B959EA2362E5FB020872D0587
F81A33A9202E23C959D0714E0C4A9FED3DBE63AA34C0BF3492739EC92C21EE27"
They use radioactive decay, and they do not call them "True" random
numbers. The word true is not needed, except by armchair "experts" who
exaggerate their own levels of expertise by emphasizing this erroneous
distinction. Or should I say "true" expertise? Please show independent
couterexamples to bolster your case, or else try to be articulate in the
future.
Boson
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Please help. Need protocol advice.
Date: Sun, 24 Jan 1999 03:02:05 GMT
> As stated the only answer is a serious piece of hardware.
I've considered tamper-proof boxes, but they would increase cost overheads
dramatically, for a number of reasons. Also, being that I know only basic
circuit design, I would have much less control over the product; whereas a
software implementation would allow me to do the work, since I'm a decent
programmer.
Don't ask me .. I'm still trying to figure out what standards I'm
dedicated to as a nonconformist.
...by the way, where are we going? And why am I in this handbasket?
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (Brad Templeton)
Subject: Re: 3DES cracked in 22 hours ??? (Was: Re: (fwd) DES Challenge III Broken in
Record 22 Hours !)
Date: 23 Jan 1999 19:10:32 PST
In article <[EMAIL PROTECTED]>,
Reuben Sumner <[EMAIL PROTECTED]> wrote:
>2^111 is the average number of keys you need to search. Thus the total number
>of years is 329,076,927,259,548. That is 329 trillion not 329 million.
>Even just searching 64 bits (ie the RC5-64 search) would take 1.17 years.
>The real threaght is not distributed.net. It is amusing and a demonstration
>that there are lots of wasted CPU cycles out there, but not a real threaght.
>In the paper by Matt Blaze et al it is estimated that a $10 custom ASIC
>can test about 200M keys/second. At that rate a $10M computer could break
>64 bits in an average of 12.8 hours. Compare that to 1.17 years.
>Even only 80 bits of something like skipjack (assuming brute force is your
>best attack) would take a $1B attack 1 year (on average) to crack.
The difference between 128 bits and 64 bits is indeed this vast. That
we built a machine cheaply that can crack 56 bits does mean that with more
money you can break 64 bits quickly, but 128 bits or more is another story.
Add enough bits and you reach the point where if every atom on earth were
a processor that could check a key every microsecond you still couldn't break
by brute force. Add a few more bits and it's every atom in the universe.
Suffice to say that this means that sufficiently long keys are unbreakable
by brute force based on current understanding, even with things like DNA
computers. Only a breakthrough in physics, like quantum computing can
break a long key with brute force. Or a breakthrough in discrete
math -- which is no longer brute force.
--
Brad Templeton http://www.templetons.com/brad/
------------------------------
** 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
******************************
