Cryptography-Digest Digest #605, Volume #14 Wed, 13 Jun 01 13:13:01 EDT
Contents:
Re: IV (Tim Tyler)
Re: IV (Volker Hetzer)
Re: Yarrow PRNG (Mark Wooding)
Re: IV (Tim Tyler)
Re: The 94 cycle cipher (Phil Carmody)
Re: Yarrow PRNG (Tim Tyler)
Re: IV (Volker Hetzer)
Re: Best, Strongest Algorithm (gone from any reasonable topic) - VERY (Mok-Kong Shen)
Re: Best, Strongest Algorithm (gone from any reasonable topic) - VERY (Mok-Kong Shen)
Re: IV (Tim Tyler)
Re: One last bijection question (Mok-Kong Shen)
Re: When the signer is trusted do birthdays matter? (Phil Carmody)
Re: IV (Volker Hetzer)
Re: Best, Strongest Algorithm (gone from any reasonable topic) - VERY
([EMAIL PROTECTED])
Re: Notion of perfect secrecy (Mark Wooding)
----------------------------------------------------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: IV
Reply-To: [EMAIL PROTECTED]
Date: Wed, 13 Jun 2001 14:18:39 GMT
Mark Wooding <[EMAIL PROTECTED]> wrote:
: Tim Tyler <[EMAIL PROTECTED]> wrote:
:> Not really. We've already discussed weaknesses in CTR mode when
:> cyphertexts are small. The idea that CTR mode is as secure as the
:> underlying block cypher is essentially a myth - despite the supposed
:> proof to this effect - because of this.
: I think you've misunderstood the security notions behind the proof.
I don't think so.
I have no argument with the proof - just with people subsequently claiming
that it proved that use of CTR mode (as propsed by Wagner et al as an AES
standard chaining mode) is as secure as the block cypher involved.
In listing CTR mode advantages they say things like:
``Messages of arbitrary bitlength. Unlike other common modes of
operation, handling messages of arbitrary bitlength is made trivial. No
bits are wasted in doing this---the ciphertext C is of the same length
as the plaintext M. [...]''
...and...
``security of CTRmode encryption. See [2], which shows that the concrete
security bounds one gets for CTRmode encryption, using a block cipher,
are no worse than what one gets for CBC encryption. (Indeed there are
approaches to get better security bounds with CTRmode encryption than
with CBC mode, though these do not directly use the block cipher E).''
This is twaddle - you can't have it both ways.
CTR mode security sucks in the example of (say) 8 bit cyphertexts.
The message space is reduced town to one of 256 possible plaintexts.
This is *hugely* worse than the block cypher in CBC mode with some
padding scheme or another.
To claim that CTR mode securtity is proven no worse than CBC mode
on the basis of the fact that the CTR-mode stream is proven hard
to distinguish from a random one (assuming there's no break in the
underlying block cypher) is utter nonsense.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: Volker Hetzer <[EMAIL PROTECTED]>
Subject: Re: IV
Date: Wed, 13 Jun 2001 16:30:59 +0200
Tim Tyler wrote:
> CTR mode security sucks in the example of (say) 8 bit cyphertexts.
> The message space is reduced town to one of 256 possible plaintexts.
> This is *hugely* worse than the block cypher in CBC mode with some
> padding scheme or another.
>
> To claim that CTR mode securtity is proven no worse than CBC mode
> on the basis of the fact that the CTR-mode stream is proven hard
> to distinguish from a random one (assuming there's no break in the
> underlying block cypher) is utter nonsense.
If you compare short messages you should either do what other modes do, namely
padding to a comparable plaintext size (i.e. one block of the underlying block
cipher) or use an 8 bit block cipher for cbc.
Greetings!
Volker
--
They laughed at Galileo. They laughed at Copernicus. They laughed at
Columbus. But remember, they also laughed at Bozo the Clown.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Yarrow PRNG
Date: 13 Jun 2001 14:41:56 GMT
Eric Lee Green <[EMAIL PROTECTED]> wrote:
> 1. Can this lead to a possible attack? E.g., if someone knows that a
> ciphersystem is obtaining key data and challenges via Yarrow, does this
> in any way compromise the security of the ciphersystem?
In theory, yes, it weakens systems a little. In practice, the
difference is negligible. For example, suppose that you're trying to
guess a 128-bit key for some `perfect' cipher, but you know that the key
was generated using Yarrow-160. You `only' need to search 2^{128} -
2^{64} keys -- that's a whole 2^{64} fewer than if you didn't know
Yarrow had been used. (2^{64} is a tiddly tiny number compared to
2^{128}.)
> 2. Could this have been fixed by the simple step of adding yet another
> SHA-1 to the algorithm, at the output, to further "stir" the values
> being given to the user?
Possibly. This isn't really the `right fix', though. It adds a load of
complexity and makes it slower and harder to analyse.
-- [mdw]
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: IV
Reply-To: [EMAIL PROTECTED]
Date: Wed, 13 Jun 2001 14:43:39 GMT
Volker Hetzer <[EMAIL PROTECTED]> wrote:
: If you compare short messages you should either do what other modes do,
: namely padding to a comparable plaintext size (i.e. one block of the
: underlying block cipher) or use an 8 bit block cipher for cbc.
That's *not* what they proposed in their CTR mode proposal to AES:
``Messages of arbitrary bit-length. Unlike other common modes of
operation, handling messages of arbitrary bit-length is made trivial.
No bits are wasted in doing this---the ciphertext C is of the same
length as the plaintext M. [...]''
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: Phil Carmody <[EMAIL PROTECTED]>
Subject: Re: The 94 cycle cipher
Date: Wed, 13 Jun 2001 14:52:07 GMT
Tom St Denis wrote:
>
> If anyone is interested you can get a copy of the 94 cycle cipher (94 cycles
> on an Athlon). at
>
> http://tomstdenis.home.dhs.org/tc16.zip
>
> It uses the quadratic and rotation as the Feistel round function.
It's certainly short.
Any reason why you do
xor edi, eax
mov eax, edi
rather than
xor eax, edi
mov edi, eax
at the conjunction of two rounds? It's a simply replacing one of the 2
read-after-writes with a write-after-read.
You're computation bound so that the above probably has little or no
real effect on an out-of-order processor. However I'm sure that you
could trivially do two blocks in almost the same time as you do 1!
Remember that there are 32x32->32 multiply instructions in the >386 with
any register as the destination.
Phil
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Yarrow PRNG
Reply-To: [EMAIL PROTECTED]
Date: Wed, 13 Jun 2001 14:51:09 GMT
Eric Lee Green <[EMAIL PROTECTED]> wrote:
: 2. Could this have been fixed by the simple step of adding yet another
: SHA-1 to the algorithm, at the output, to further "stir" the values
: being given to the user?
If the SHA-1 accepted 64-bit blocks of the same size that Yarrow uses
internally, and output blocks of the same size then there would be
the same problem.
If they were "out of step" with one another, things may indeed be
much improved.
[Incidentally, chaining can't be used without sacrificing the
"parallelism" aspect of Yarrow.]
However, hash functions are not known for their speed. If you find
the need to slap a hash function over the outputs the question
arises as to why you didn't put it at the heart of the algorithm
in the first place.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: Volker Hetzer <[EMAIL PROTECTED]>
Subject: Re: IV
Date: Wed, 13 Jun 2001 17:04:36 +0200
Tim Tyler wrote:
>
> Volker Hetzer <[EMAIL PROTECTED]> wrote:
>
> : If you compare short messages you should either do what other modes do,
> : namely padding to a comparable plaintext size (i.e. one block of the
> : underlying block cipher) or use an 8 bit block cipher for cbc.
>
> That's *not* what they proposed in their CTR mode proposal to AES:
>
> ``Messages of arbitrary bit-length. Unlike other common modes of
> operation, handling messages of arbitrary bit-length is made trivial.
> No bits are wasted in doing this---the ciphertext C is of the same
> length as the plaintext M. [...]''
So you propose to ad a minimum length requirement to the CTR in the
AES proposal?
However, I still fail to see the problem (my fault likely enough):
Given a CTR encrypted message of one bit, i.e. a 0 or a 1, how
would you go about decrypting it?
Greetings!
Volker
--
They laughed at Galileo. They laughed at Copernicus. They laughed at
Columbus. But remember, they also laughed at Bozo the Clown.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic) - VERY
Date: Wed, 13 Jun 2001 17:21:18 +0200
Mark Wooding wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> > But measures should have adquate (intuitionally reasonable)
> > interpretations, I suppose. If a security measure
> > says 0 security, then one would 'very naturally' think
> > that that means no protection at all, isn't it?
>
> This is why we have different notions of security. There is a
> difference between the information-theoretic security provided by the
> one-time pad (and perfect secret-sharing systems) and the computational
> security provided (by assumption) by most commonly-used symmetric and
> asymmetric ciphers.
The problem is whether one has a 'common' measure of
security that could be applied to all sorts of encryptions.
>
> > I don't think that something that is at the disposal of the opponent
> > but requires a time of eternity to exploit isn't equivalent to 'no
> > information' to the opponent, on the other hand.
>
> The information is there; the ability to extract it is not.
There we agree fully.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic) - VERY
Date: Wed, 13 Jun 2001 17:21:06 +0200
[EMAIL PROTECTED] wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> writes:
> > [EMAIL PROTECTED] wrote:
> >>
> >> (2) In the case of PK systems, I generally *can* be 100% positive I have
> >> now got the private key in my hands.
> >
> > That's the axiom of existence of opponents of unbounded resources. If
> > one is any realistic, one wouldn't adopt that axiom.
>
> No it isn't, Mok. There are many many ways I can get a key in my hands,
> which I think might be yours. Once I have a candidate in my hand, I can
> verify with 100% certainty whether it *is* or *is not* your key.
>
> In the case of a OTP, YOU YOURSELF can walk right up to me and GIVE me
> your key, along with a box of chocolates. That does me no good: I have
> no way of knowing that it's your *real* OTP; it might be a clever fake
> you created to fool me. Even if your wife mails me the OTP, together with
> a note that says ``let's get together'', I can't be sure it's your key:
> you might have planted a key to fool your wife.
>
> That's what ``zero information-theoretic security'' means: by publishing
> your public key, you have furnished a foolproof means of telling the real
> private key from all other candidate keys. Which is the answer to your
> original question.
There are all sorts of assumptions that one could make.
For instance, it could be that one day I am completely
drunken and hand over my plaintext kindly to the opponent
in person. In using PK, one accepts that one has a means
to safely guard one's private key. The problems with OTP
are also well known. (In fact, moreover, ideal OTP doesn't
exist.) I suppose that it could be claimed that ANY cipher
that could be really implemented could have potential
problems. There are in life always situations where some
premises do not apply. One behaves correspondingly,
employing other solutions, whereupon some new problems
have to be dealt with. With that in mind, I think it
becomes understandable that a 'universal' and practically
sensible measure of security could not exist. (BTW, not
even the metric system is accepted throughout the world.)
M. K. Shen
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: IV
Reply-To: [EMAIL PROTECTED]
Date: Wed, 13 Jun 2001 15:23:27 GMT
Volker Hetzer <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> Volker Hetzer <[EMAIL PROTECTED]> wrote:
:> : If you compare short messages you should either do what other modes do,
:> : namely padding to a comparable plaintext size (i.e. one block of the
:> : underlying block cipher) or use an 8 bit block cipher for cbc.
:>
:> That's *not* what they proposed in their CTR mode proposal to AES:
:>
:> ``Messages of arbitrary bit-length. Unlike other common modes of
:> operation, handling messages of arbitrary bit-length is made trivial.
:> No bits are wasted in doing this---the ciphertext C is of the same
:> length as the plaintext M. [...]''
: So you propose to ad a minimum length requirement to the CTR in the
: AES proposal?
I propose they don't make claims that boil down to having their cake and
eating it.
*Either* claim simplicity (ease of encyphering messages of any length),
*or* claim security of equal to the block cypher - but *don't* claim both
- since the claims are not logically compatible with one another.
: However, I still fail to see the problem (my fault likely enough):
: Given a CTR encrypted message of one bit, i.e. a 0 or a 1, how
: would you go about decrypting it?
You immedialey know it is not one of the (possibly zillions)
of possible messages larger than 1 bit - and can narrow the
possibilities down to one of two plaintexts. This is not what
encryption ought to be about IMO.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: One last bijection question
Date: Wed, 13 Jun 2001 17:35:19 +0200
Mark Wooding wrote:
>
> The suggestion was to use the term `image' to sidestep this issue of
> ambiguity of `range' which has distracted the current conversation. I
> don't intend to overturn the way mathematics is done elsewhere, just dig
> the current thread out of a hole.
> The problem isn't that some people aren't familiar with the term
> `range'. The problem is that *everyone* seems familiar with it, but
> we disagree about its meaning. It's best to avoid ambiguous terms, so
> I've suggested what I'm sure is a less common alternative. Since this
> is a suggestion applicable only to the current discussion, I didn't
> think it was terribly controversial.
Ambiguity is maybe for persons who are accustomed to
certain literatures. Perhaps I haven't followed this
thread carefully and I beg your pardon. Could you please
demonstrate with existing literatures the said ambiguity,
i.e. in one literature the term 'range' is used in one
sense, while in another it is used in a different sense?
For me, with my books, the concept of range is unique
till this moment, for I don't have anything I know
where the term is used in any way different from that
defined in my books. (That's why in another post I
asked you to find a book where the 'ambiguity' could
be shown.) On the other hand, if someone uses 'image',
I would have to think a little bit about its meaning.
M. K. Shen
------------------------------
From: Phil Carmody <[EMAIL PROTECTED]>
Subject: Re: When the signer is trusted do birthdays matter?
Date: Wed, 13 Jun 2001 16:09:27 GMT
Neil Couture wrote:
> the birthday problems is related to the problems of determining a necessary
> security
> condition for hash functions that depends only on the size of the message
> Digest.
[SNIP - derivation of the O(sqrt(n)) Birthday attack on MD size n]
> So returning to you post, The security of a hashfunction has nothing to do
> with
> the number of message that somebody hash and sign but more to the fact of
> how easily it is to find a collision. It is certainly the case anyway that
> the fact of
> signing your hash gives you a lot of room if your hash function is not one
> which has low probability of collision.
Yes but I thought that the collision was merely within the whole set of
M = { malicious documents } which has work factor |M| to compute. With
the hand-wavy heuristic that there are |M|*|M|/2 = O(|M|^2) possible
pairs that could clash.
However, in my scenario, wouldn't Malory be looking for a member of M
which hashes to the same value as a member from T = { Trent's documents
}. The hand-wavy heuristic says that there are only |M|*|T|/ 2 = O(|M|)
pairs that could clash.
e.g. If Trent were to sign 2^128 documents, then if he had used a 128
bit key it would be _trivial_ to spoof a document, as almost every hash
value has already been signed. And so I'd say in this case the spoofing
work factor is O(1).
Hand waving seems to point to
Required Hash Len = Required brute-force workload equivalent length +
lg(|T|)
If RSA were to invent a 'perfect' 128-bit hash, and were to challenge
people to create a document which hashed to a particular 128-bit value,
what would the workload be?
I claim that's the situation before Trent has signed anything. The first
person to crack their challenge is the first Malory to spoof a document
that it appears Trent has signed.
If the workload in this challenge situation is 2^128, then that's in
agreement with what I feel to be the case, if it's 2^64 then I really am
lost.
I know this "puting a constraint on |T|" is an unusual one, but I
believe it's one worth discussing, as there is a real world analogue.
(I'm thinking of companies signing software service patches, once a
month, say.)
Phil
------------------------------
From: Volker Hetzer <[EMAIL PROTECTED]>
Subject: Re: IV
Date: Wed, 13 Jun 2001 18:27:08 +0200
Tim Tyler wrote:
>
> *Either* claim simplicity (ease of encyphering messages of any length),
> *or* claim security of equal to the block cypher - but *don't* claim both
> - since the claims are not logically compatible with one another.
But, even for block ciphers, if you *want* to transmit arbitrarily
long messages you have to transmit the length or some end sequence, thereby
adding redundancy in a way that an attacker can use to distinguish possible
from impossible plaintexts. (Remember, security rests in the key. Everything
else, like the padding strategy is known.)
OTOH, with the counter mode you don't have a full block, making analysis
harder.
How do they balance with a real world block cipher?
> : However, I still fail to see the problem (my fault likely enough):
> : Given a CTR encrypted message of one bit, i.e. a 0 or a 1, how
> : would you go about decrypting it?
>
> You immedialey know it is not one of the (possibly zillions)
> of possible messages larger than 1 bit - and can narrow the
> possibilities down to one of two plaintexts. This is not what
> encryption ought to be about IMO.
Well, do you think of the otp as an example of what encryption is
not about too? After all it has the same flaw CTR has.
Greetings!
Volker
--
They laughed at Galileo. They laughed at Copernicus. They laughed at
Columbus. But remember, they also laughed at Bozo the Clown.
------------------------------
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic) - VERY
From: [EMAIL PROTECTED]
Date: 13 Jun 2001 12:48:19 -0400
Mok-Kong Shen <[EMAIL PROTECTED]> writes:
> [EMAIL PROTECTED] wrote:
>>
>> That's what ``zero information-theoretic security'' means: by
>> publishing your public key, you have furnished a foolproof means of
>> telling the real private key from all other candidate keys. Which is
>> the answer to your original question.
>
> There are all sorts of assumptions that one could make.
> For instance, it could be that one day I am completely
> drunken and hand over my plaintext kindly to the opponent
> in person.
No. In an information-theoretic sense, the plaintext you hand me is
useless. I am forced to consider the possibility that you are lying,
and there is NO PROOF that you are NOT lying. If the cipher was a OTP,
you can give me the plaintext AND the key, and I STILL can't be sure
you aren't lying to me--even if you swear on your grandmother's grave.
> In using PK, one accepts that one has a means to safely guard one's
> private key.
Yes, but now you're talking about ``security'' in a generic sense, which
includes cryptographic notions, as well as physical security, as well as
personnell security, and a lot of other things. The one thing PK doesn't
give you is information-theoretic security: once your secret is out, I
*know* you aren't lying or fooling me, because I *know* that I now have
the private key corresponding to the public key.
Nobody is saying that PK systems aren't ``secure'', for reasonable def's
of ``secure''. Only that they are *not* secure in the sense of Shannon's
paper--not even a tiny, little bitty bit. Not at all. Do you understand
the issue now?
Len.
--
In the long run, managements stressing accounting appearance over economic
substance usually achieve little of either.
-- Warren Buffett, 1981
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Notion of perfect secrecy
Date: 13 Jun 2001 17:02:50 GMT
Tim Tyler <[EMAIL PROTECTED]> wrote:
> Talk to Shannon not me. He defined perfect secrecy so that it was a
> characteristic of a cyphermachine. The cyphermachine can control the
> length of the message - but it has no say in when the message
> actually gets sent.
Indeed. As I understand it, we have three random variables, K, P and C
related by C = E_K(P). Perfect secrecy occurs when, for any possible
plaintext p and ciphertext c,
Pr(P = p) = Pr(P = p | C = c)
That is, the probability of some given message being the correct
plaintext corresponding to a ciphertext doesn't change when you learn
what the ciphertext actually is.
Tim is therefore completely correct in saying that, if the plaintext is
some arbitrary string, the one-time pad does /not/ provide perfect
secrecy. In particular, the set of strings (over some countable set) is
(countably) infinite, whereas the set of strings of some given length
(or less -- allowing padding) is finite.
-- [mdw]
------------------------------
** 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
******************************
