Cryptography-Digest Digest #273, Volume #13 Tue, 5 Dec 00 08:13:01 EST
Contents:
Re: Crypto Proceedings ("John A. Malley")
Why Galois Fields in Cryptography? (John Savard)
Re: RC4 or Rijndael (Guy Macon)
Re: RC4 or Rijndael (Guy Macon)
cracking a char subst cypher (Frank Hsueh)
Re: RC4 or Rijndael ("Julian Morrison")
Re: MD5 byte order (Thomas Pornin)
Re: Logic of authentication (Erik-Oliver Blass)
Re: RC4 or Rijndael (Benjamin Goldberg)
Re: hardware RNG's (Tim Tyler)
----------------------------------------------------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: Crypto Proceedings
Date: Mon, 04 Dec 2000 19:20:51 -0800
Mark Harrop wrote:
>
>
> Does anyone know of an ONLINE source of the CRYPTO PROCEEDINGS from as far
> back as possible ?
>
> Also, are they still being held, and do they have a web site ?
>
> Once again, I thank all of you kind souls for helping.
>
Cryptography Research, Inc. keeps an index of papers from Eurocrypt'91
through Eurocrypt'97 and Crypto'92 through Crypto'97 at their web site:
http://www.cryptography.com/resources/papers/index.html
The indices list all of the papers from those conferences with links to
*some* of the actual papers.
Check into Counterpane's extensive on-line repository of papers at
http://www.counterpane.com/biblio/
for those papers listed yet link-less at Cryptography Research's site.
Hope this helps,
John A. Malley
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To: sci.math
Subject: Why Galois Fields in Cryptography?
Date: Tue, 05 Dec 2000 04:50:34 GMT
The new Advanced Encryption Standard, Rijndael, makes use of
arithmetic in GF(2^8). So did Twofish, one of the other finalists in
the AES process.
Not being terribly up on advanced math, I wondered why this relatively
unfamiliar type of operation was used in these block ciphers. I
realize that exotic math is needed for public-key algorithms, but
surely prosaic things like addition, XOR, table-lookup, and so on seem
to be enough for many block ciphers.
However, in a thread (on sci.crypt) titled "The Next Step After OTP",
I considered one intrinsic weakness of the one-time-pad and certain
other stream ciphers - those which simply XOR the output of a
pseudo-random number generator with the plaintext - the fact that one
can XOR a pattern of bits with the ciphertext, with the certain result
that one has changed the plaintext in the corresponding way. This is
called the "bit-flipping" attack, and essentially the same thing can
be done if modulo-n addition for n larger than 2 replaces XOR.
Naturally, there are other solutions to this problem, involving
one-way hash functions, that are used in practice, but I thought it
was interesting theoretically to see what would be the _minimum_
requirement to make a cipher that behaved like a stream cipher which
provided a different rearranged substitution alphabet for every symbol
enciphered. It is easy enough to produce a cipher like that if one is
willing to be elaborate and complicated; a rotor machine simulation is
one possibility, but what is the minimum condition?
It turns out that if the conditions are explicitly stated as follows:
the keystream symbols have to have the properties needed for a
one-time-pad, and furthermore
when a corresponding plaintext and ciphertext symbol are known,
changing the ciphertext symbol to any one of the other possible values
must have the result that all the plaintext symbols (except the known
one) must be equally likely
they can be met, for an alphabet of N symbols, if the keystream
consists of symbols from a set of N(N-1) symbols, that determine two
quantities, A (having N values) and B (having N-1 values) where the
encipherment operation is: (plain * B) + A = cipher, where * and + are
the operators for a finite field of order N.
And so, if one wishes to encrypt a binary data stream eight bits at a
time, this attractive property is therefore attained by means of
GF(2^8).
Which gives one reason _why_ one might see Galois Fields in use for
cryptographic purposes. I've now added a page to my web site at
http://home.ecn.ab.ca/~jsavard/crypto/co041103.htm
containing the material from that thread, at which people are invited
to look and tell me if I'm making sense or if I'm all wet.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: RC4 or Rijndael
Date: 05 Dec 2000 05:49:59 GMT
Bill Unruh wrote:
>Yes, RC4 is a stream cypher. The key can never be reused or the strength
>is essentially zero. It is very easy to code, and is much faster.
>However it is totally useless unless you can choose a random key each
>use. (eg, by sending the key via RSA).
Huh???
I use the ciphersaber [1] implementation of ARCFOUR [2] with the same
secret passphrase every time. There are additional random bytes that
are needed to avoid key reuse, but those are sent in the clear by
being prepended to the ciphertext. There is no need to send a key
via RSA or any other method.
Notes:
[1] http://www/ciphersaber.gurus.com
[2] Nobody here knows for sure what the internal details of RC4 are,
but ARCFOUR seems to give the same results in every case tested
so far, so it may be the same. The name "ARCFOUR" is probably
a better choice than "aRC4" because it is less likely to
violate the trademark laws.
s ame
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: RC4 or Rijndael
Date: 05 Dec 2000 06:03:03 GMT
Mats Lofkvist wrote:
>
>
>[EMAIL PROTECTED] (Bill Unruh) writes:
>
>> Yes, RC4 is a stream cypher. The key can never be reused or the strength
>> is essentially zero. It is very easy to code, and is much faster.
>> However it is totally useless unless you can choose a random key each
>> use. (eg, by sending the key via RSA).
>
>Isn't adding a cryptographically strong random part to the RC4 key
>and sending the random part in clear to the receiver considered a
>secure way to reuse RC4 keys?
>
>If it is secure, couldn't this be used with any stream cipher that
>allows at least twice the number of key bits compared to what is
>really needed? Just use half (or less) of the key bits for the
>real key and the other half (or less) for the random part.
Minor correction: it really isn't even necessary for the part sent
in the claer to be random. Any value that is unique for each
message can be used for the initialization vector. It's a Good
Thing if the added data is something like the output of a weak
system PRNG instead of something that has many bits that don't
change, but it's not really necessary.
Also, you don't have to use half of the space for the added data;
ciphersaber uses 54 bytes for the passphrase and 10 bytes for the
initialization vector.
------------------------------
From: Frank Hsueh <[EMAIL PROTECTED]>
Subject: cracking a char subst cypher
Date: Tue, 5 Dec 2000 07:29:34 GMT
I was just wondering... is there any code out there to crack a simple
character substitution cypher?
--
frank hsueh
EngSci 0T3
------------------------------
From: "Julian Morrison" <[EMAIL PROTECTED]>
Subject: Re: RC4 or Rijndael
Date: Tue, 05 Dec 2000 08:18:26 +0000
"Benjamin Goldberg" <[EMAIL PROTECTED]> wrote:
>> Wasted bytes is network churn sending cryptocrap when it could be
>> sending data. I begrudge the fat RSA results, so any wastage from the
>> symmetric cypher as well is annoying.
>
> Why not stick part of the symmetric stuff's data into the RSA
> encryption? Instead of, x bit key and 1024-x bits of random padding,
> send the x bit key, and the first 1024-x bits of symmetrically encrypted
> data. As long as your messages are longer than 1024-x-sizeof(iv) bits,
> then you aren't wasting any bandwidth at all.
Interesting... basically pad it out with the first part of the RC4
cyphertext.
You'd get something like:
RSA("IV", RC4("da")), RC4("tadatadata").
Is this secure? Specifically, is using non-garbage as padding secure?
------------------------------
From: [EMAIL PROTECTED] (Thomas Pornin)
Subject: Re: MD5 byte order
Date: 5 Dec 2000 09:22:47 GMT
According to Bob Luking <[EMAIL PROTECTED]>:
> But I cannot tell whether to seed A, for example, with the word 67452301 or
> the word 01234567.
The RFC 1321, which describes MD5, specifies the ordering of bytes; see
paragraph 3.3:
<<
A four-word buffer (A,B,C,D) is used to compute the message digest.
Here each of A, B, C, D is a 32-bit register. These registers are
initialized to the following values in hexadecimal, low-order bytes
first):
word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10
>>
"low-order bytes first" means that A is 0x67452301, B is 0xefcdab89, etc...
Those endianness things are infortunate, because in MD5 they are mixed:
bytes are represented with the low-order byte first, but, inside a byte,
the bits are in big-endian form: the most significant bit is first.
The SHA-1 and SHA-256/384/512 specs are more coherent: they use
big-endian everywhere.
--Thomas Pornin
------------------------------
From: Erik-Oliver Blass <[EMAIL PROTECTED]>
Subject: Re: Logic of authentication
Date: Tue, 05 Dec 2000 10:51:51 +0100
Reply-To: [EMAIL PROTECTED]
Mike Rosing wrote:
> Patience, persistence, truth,
Hm, is it that what I need to analyse my protocol ? :-)
Hey, all ! No softwarehelpers for me ?
Regards,
Erik
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: RC4 or Rijndael
Date: Tue, 05 Dec 2000 09:56:08 GMT
Guy Macon wrote:
>
> Bill Unruh wrote:
>
> >Yes, RC4 is a stream cypher. The key can never be reused or the
> >strength is essentially zero. It is very easy to code, and is much
> >faster. However it is totally useless unless you can choose a random
> >key each use. (eg, by sending the key via RSA).
>
> Huh???
>
> I use the ciphersaber [1] implementation of ARCFOUR [2] with the same
> secret passphrase every time. There are additional random bytes that
> are needed to avoid key reuse, but those are sent in the clear by
> being prepended to the ciphertext. There is no need to send a key
> via RSA or any other method.
Guy, you obviously don't know what Bill's trying to do. Bill's sending
a message, encrypted, to a person whose public key he knows, but with
whom he does not share a private key.
To do this with a combination of asymmetric and symmetric ciphers, one
encrypts a randomly symmetric generated key and the first part of the
message using the asymmetric method, and then the rest of the message,
using the symmetric cipher, with the key which was encrypted in the
asymmetric portion of the message.
Let's suppose you have an RSA key with 1024 bits (128 bytes) in the
public modulus. To encrypt with this key, and [for example] 128 bit AES,
the first 128 bytes would be the randomly generated key, the next 896
bits would be the first 896 bits of the plaintext, and then this would
be followed by the rest of the plaintext, encrypted with AES using the
randomly generated key, preferably in CBC mode. Since the key is
generated at random, there is no need for a random IV; however, since
CBC mode does require *something* as an IV, we can simply use a hash
(SHA1 will do fine) of the plaintext in the asymmetriccly encrypted
portion of the message.
If we are using ARC4 instead of AES, it is reasonable to use a 128 bit
key, which would of course be randomly generated. Because of this, we
don't need any kind of IV.
When do we need an IV with ARC4 (or need a random/unique IV with AES)?
Answer: When we're encrypting files, with *just* the symmetric key.
If two files are encrypted with ARC4, using the same key, and no IV,
this is insecure. If two files are encrypted with AES, in CBC mode with
a fixed IV (or worse, encrypted in ECB mode), there is a weakness that
is not present if a unique IV is used for each enciphered file.
--
There are three methods for writing code in which no bug can be found:
1) Make the code so straightforward that there are obviously no bugs.
2) Make the code so complicated that there are no obvious bugs.
3) Insist that any apparent bugs were really intentional features.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: hardware RNG's
Reply-To: [EMAIL PROTECTED]
Date: Tue, 5 Dec 2000 12:42:01 GMT
David Schwartz <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> : However, this really detracts us from what was the main point of this
:> : thread, which you've attempted to evade by resorting to "proof by
:> : definition". Not only is your definition flatly incorrect, but the
:> : argument you're trying to squeeze by through this perverse definition is
:> : incorrect as well.
:>
:> I'm at a loss to determine what you're talking about.
: In other words, everyone's completely forgot what this thread is about
: and it's degenerated into a definitional argument.
Those are indeed "other words" - but they don't seem to have the same
meaning as my sentence.
:> : I would submit that useful definition of "random" must be one that
:> : can't be increased by any determinstic process.
:>
:> Where does that leave you with your entropy-condensing hash function?
: The function does not increase the randomness, it simply 'massages' or
: concentrates it. The output is, arguably, slightly less random than the
: input.
If I substitute "total entropy" for "randomness" this sentence would make
perfect sense to me. However, I'm still having problems with your
describing any streams with some non-zero entropy content as "random".
Is there /any/ line beyond which you would no longer apply the term?
If 83% bias is acceptable, what about 99% bias? 99.99% bias? Is the
there some point beyond which you would regard describing a stream as
random as misleading?
If bias is acceptable, what about correlation? Usenet messages contain a
fair slab of entropy. Are usenet messages well characterised as "random"?
:> : I would also argue that randomness is the same as unpredictability and
:> : requires positing a hypothetical predictor with specific capabilities.
:>
:> Can you cope with leaving the "hypothetical predictor" role unfilled,
:> and positing *any* predictive - if, for example, they are only given a
:> stream - and not information about how it was generated?
: You can posit a predictor who has no knowledge of how the stream was
: generated. You can posit a predictor with full knowledge. You can posit
: a predictor with both knowledge of and access to some portions of the
: generator. When you think you are analyzing without any "hypothetical
: predictor", what you are really doing is positing a hypothetical
: predictor without realizing it.
It sounds as though you can cope with things like "computationally
unlimited predictors". OK - good.
: For example, are the digits of Pi random? I don't think anyone reading
: this would fail to accurately predict what comes after "3.1415". The
: digits are also, obviously, compressible. When a person asks if the
: digits of Pi are random, he (presumably) posits a hypothetical predictor
: who is barred from directly using the fact that the digits are the
: digits of Pi. In other words, he prohibits access to the algorithm.
I believe normal usage in this case *allows* access to the algorithm, but
denies knowledge of how far into the expansion of PI the digits come from,
and ensures that they come from far enough in that exhaustive search
has a minimal chance of locating the digits in question.
The challenge is then to make predictions of the next digit in the stream.
:> : If a stream is predictable, it's not random. If it's random, it can't
:> : be predicted. No determinstic process can make a something harder to
:> : predict to a predicter who knows the process.
:>
:> Now I believe you may be running afoul of the facts.
:>
:> What about catastrophic reseeding?
:>
:> Processes like Yarrow can take a low entropy stream and apply a
:> deterministic process to it. The process accululates entropy, and
:> applies catastrophic reseeding, to foil state-following attacks.
: Right. And absent unpredictable input, this process can only produce
: predictable output.
That's not the point. Catastrophic reseeding is employed while
the inputs have lower entropy than is desired. It doesn't help if
there's no entropy input at all. I'm assuming there's /some/ incoming
entropy.
:> Here it is clear that a determinitstic process is making an attacker's
:> life *vastly* more difficult - and knowledge of the process involved does
:> not help him one jot.
: His life is not more difficult. He would have at least as much
: difficulty predicting the input as the output.
No. This is the whole point of catastrophic reseeding. Your statement is
not true, at least not if we are dealing with any sort of human, or
computationally limited predictor. This is the point of catastrophic
reseeding - it makes prediction difficult.
In this example, say all the entropy rate is 1/100 bits/bit. In other
words a predictor of the input will guess right about 99 times out
of a 100.
However feed this through a accumulator/reseeding mechanism combined
with a secure cryptographic primitive. The arracker may predict up
to 100 bits out of 100 for a while, but is then reduced to a brete force
key search for the cryptographic primitive when reseeding occurs.
If this doesn't "make prediction harder", I don't know what does.
You would be right if you were discussing the entropy of the output.
This is unchanged (or perhaps slightly reduced). However, as soon as you
bring any sort of practical predicting agent onto the scene to measure
your randomness against, deterministic processing can have a big effect on
predictability - contrary to your thesis.
:> : In fact, the first thing someone analyzing that stream would do is to
:> : 'compress' it by converting it to "623434", thereby concentrating the
:> : entropy through a determinstic process. I don't think any sensible
:> : person would argue that the expanded stream is somehow more random than
:> : the original one.
:>
:> It is very likely that they would - *if* they were not told that
:> the streams were representations of the same information, and were
:> just given the streams.
:>
:> It appears that - by your definition - the randomness of something depends
:> on how much of it you are given.
: No. In that case, I'm assuming that the stream continues indefinitely
: 'the same way'. I thought that was clear. Obviously, if the stream then
: repeats from the beginning, it's not random. But please don't make a
: deliberate attempt to misunderstand me.
Sorry - no deliberate attempt was occurring. If I misunderstood,
communication problems or lack of applied intelligence was probably
involved.
I'm still a bit confused. If the streams are infinite, how can you
compress them? In what sense is the original version "expanded"
compared to the compressed version?
:> You appear to be using the term "randomness" for what would normally be
:> described as "entropy".
: Not at all. I'm using the term "random" to mean "unpredictable", which
: is reasonable because that's what it means. "Entropy" is much more of an
: absolute measure that is independent of the predictor assumed.
Well, we seem to differ there as well. I would say that measure of
entropy depends critically on the predictor's knowledge of the possible
states of the system in question.
Popularly entropy is a measure of information content.
In turn information content is a measure of "suprise value".
Thus information content - and so also entropy - are subjective measures.
As I've said, I think a number of your ideas would make much better sense
if you substituted "randomness" for "entropy". In particular, your notion
that this quantity can't be increased by a deterministic process would
then make more sense, IMO.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
** 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
******************************
