Cryptography-Digest Digest #52, Volume #13 Mon, 30 Oct 00 21:13:01 EST
Contents:
Re: [PGP] Twofish, 256bit, and Usenet Posting (SCOTT19U.ZIP_GUY)
Re: Calculating the redudancy of english? (John Savard)
Re: Collision domain in crypt()? (David Wagner)
Re: SSL or public key infrastructure (xmedar)
Re: DATA PADDING FOR ENCRYPTION (Tim Tyler)
Re: Searching for a good PRNG (Tim Tyler)
Re: Calculating the redudancy of english? (Tim Tyler)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Crossposted-To: alt.security.pgp
Subject: Re: [PGP] Twofish, 256bit, and Usenet Posting
Date: 31 Oct 2000 00:58:30 GMT
[EMAIL PROTECTED] (Michael Young) wrote in
<8tl29d$rv0$[EMAIL PROTECTED]>:
>Thomas J. Boschloo wrote in message <[EMAIL PROTECTED]>...
>... some wrong speculations about how PGP generates session keys,
>and that it "doesn't sound safe".
>
>OK, here's how PGP generates a session key from a passphrase,
>when the hash function output is smaller than the required key:
>
You give a wonderful explantion of how the session key is encoded
could you also give us the current method of chaining the main ciphers
blocks, And does it still do a quick check to test if the key is correct
so that it doesn't have to decode the whole file before rejecting a
bad key.
I am specifically talking about the advertised higher security mode
where the public key encrytion is not used and one encrypt straight.
Thank You
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website **now all allowed**
http://members.xoom.com/ecil/index.htm
Scott LATEST UPDATED source for scott*u.zip
http://radiusnet.net/crypto/ then look for
sub directory scott after pressing CRYPTO
Scott famous Compression Page
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Calculating the redudancy of english?
Date: Tue, 31 Oct 2000 01:11:04 GMT
On Mon, 30 Oct 2000 22:42:08 GMT, Simon Johnson
<[EMAIL PROTECTED]> wrote, in part:
>In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (JPeschel) wrote:
>> Simon Johnson [EMAIL PROTECTED] writes:
>> >How does one calculate the redudancy of english?
>> Use the index of coincidence.
>What is the index of coincidence, Applied crypto doesn't seem to give
>enough info for me to estimate the redudanct of english.
No; Applied Cryptography doesn't discuss things like letter frequency
because it is mostly used in attacking pencil and paper ciphers, which
are the sort of things your "kid sister" might solve as puzzles - and
which are explicitly excluded from coverage in the book.
The index of coincidence, however, will only tell you how redundant
English text, encrypted by a secure method of letter transposition,
is. The actual redundancy of English text cannot be measured, only
lower bounds can be set for it: its single-letter frequencies indicate
it must have this much redundancy, its digraph frequencies indicate it
must also have this much more, its word frequencies indicate it must
have this much more yet.
Thus, getting the "real" redundancy of the English language requires
you construct a mathematical model that only generates sensible
English text, but isn't limited to only a fraction of the possible
English texts.
Still, a formula _is_ required to calculate each one of those lower
bounds. And it's something even my web page does not describe. (If you
were a mathematician, though, my page on optimized Morse armor would
give you enough clues to reinvent it.) "Cryptography: A Primer", by
Alan Konheim, does describe it, and so does "Elementary
Cryptanalysis", by Abraham Sinkov, and so does "The Codebreakers", by
David Kahn.
The index of coincidence itself is the probability that two letters,
from a source stream, will be the same letter. This increases as
redundancy increases, but it is not itself the redundancy.
Its formula is:
( the sum, over all possible letters i, of n(i) times (n(i) - 1) )
divided by ( N times ( N-1 ) )
where N is the number of letters in a message, and n(i) is the number
of times the letter whose index is i occurs in the message.
Given a probability distribution, rather than a specific text, one
would use the formula
the sum, over all possible letters i, of ( p(i) squared )
where p(i) is the probability of the letter whose index is i.
But for the redundancy, what you want is the entropy of the source
stream.
Each letter of an English text consumes log[base 2](26) bits, or
log[base 10](26) digits, of bandwidth.
The amount of bandwidth English text deserves, based only on letter
frequencies, would be:
the sum, over all possible letters i, of ( p(i) * log( 1/p(i) ) )
where p(i) is the probability of the letter whose index is i.
And the redundancy of English text is given by
1 - ( deserved bandwith / consumed bandwidth ).
So this is how to calculate redundancy from frequency tables.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Collision domain in crypt()?
Date: 31 Oct 2000 01:37:57 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Tim Tyler wrote:
>In fact - with an appropriate numbering scheme - you could uniquely
>represent all 4 million records with only 22 bits, with a zero chance
>of collision.
If you know the records before you have to choose the hash function,
yes, you can make do with 22 + epsilon bits of output.
If you must choose the hash function in advance, you need 44 bits.
When people ask for collision-less hash functions, the latter scenario
is much more commonly what is desired. But perhaps we should ask the
original poster what exactly is desired?
------------------------------
From: xmedar <[EMAIL PROTECTED]>
Subject: Re: SSL or public key infrastructure
Date: Tue, 31 Oct 2000 01:41:55 +0000
[EMAIL PROTECTED] wrote:
> What I would recommend is using whatever method you desire of
> distributing the root server key and the keys for individuals (X.509
> certificates will work nicely).
<snip>
Thanks I think the group situation is closest to what I require, the
messages
have to be routed through the server as it acts as an annonymiser. XM
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: DATA PADDING FOR ENCRYPTION
Reply-To: [EMAIL PROTECTED]
Date: Tue, 31 Oct 2000 00:51:13 GMT
Bryan Olson <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> Bryan Olson wrote:
:> : Tim Tyler wrote:
:> :> Bryan Olson <[EMAIL PROTECTED]> wrote:
:> :> : Tim Tyler wrote:
:> :> The problems of padding scheme of appending a 1 and padding
:> :> with 0s to the end of the block is the topic under discussion
:> :> I believe.
:>
:> : Specifically, you suggested that known plaintext it adds,
:> : and thus the ability to reject most individual keys (out of
:> : 2^128 of them) was some kind of security problem [...]
:>
:> That's a fair assessment.
: [...]
:> : One who cannot trust computational security might reasonably
:> : use the OTP.
:>
:> If they can handle the large keys involved.
:>
:> : But presenting this as a justification for bijective padding is
:> : nonsense.
:>
:> It's not nonsense. Failing to add known plaintext might help when the
:> attacker would not otherwise have a unique halting criterion.
:>
:> All he has to do is to guess keys ar random to stand an increased
:> chance of success with his improved halting criterion.
:>
:> This isn't difficult to understand. What is your problem with it?
: We already beat it. Exhaustive search is trivial to defeat.
Guessing keys is going to work some of the time, nevertheless.
If you are arguing that the advantage offered by an improved halting
criterion is relatively small in the face of to difficulties imposed
by a 128 bit key space, then you would be right - *IF* there are no
attacks on the algorithm in question, and there are no other ways to
get hold of key material besides cryptanalyic attack. Since neither
of these can be known to be true there are other attacks besides
brute force or guessing whith which the ability to reject keys helps.
: If you think it's still to dangerous with 128 bit keys, or
: that the attacker might know some, but not all, of the bits -
: then use a 256-bit key.
Bumping up the size of the key to provide security usually really helps.
Of course it introduces OTP-like key distribution problems, an problems
with the performance of any PK component of the algorithm - it's not a
magic bullet.
:> : The same 128-bit key is not going to provide ideal secrecy for
:> : realistic message spaces.
:>
:> There you go with your "message spaces" again.
: Yes. If you're seeking ideal secrecy without the OTP, then it
: turns out to be pretty important.
Of course - but in the context of this discussion, individual messages
are what can be short - not whole spaces of messages. A single short
message in a message space of millions of lengthy messages is
liable to lack a concrete halting criterion - in the absence of padding
slip-ups.
:> If each messag has its own key, message spaces are of little
:> relevance.
: That's one of my points. Use techniques that work for all
: message spaces.
Somehow you manage to completely ignore the point I'm raising and
go off in a new direction.
To repeat it again - a short message can be within the unicity
distance by itself - if it comes with its own key. Message
spaces matter not in the slightest to this issue. All that is
relevant is the transmission of the individual message in question.
:> You wrote:
:>
:> ``can you imagine someone so clueless as to expect his message
:> space won't have enough redundancy to cover a couple hundred (or
:> several thousand) bits of key equivocation?''
:>
:> "Multiple small messages" were not mentioned, AFAICS.
: Perhaps this was just a mis-communication. When I distinguished
: "message" from "messages", I was pointing out just that. What
: you quote above was from before the small-message case.
The section I quoted was fairly clearly "the redundancy in question".
However I'm quite content to put this section down to mis-communication.
:> Regardless of what you thought you were talking about, my
:> point still stands - short messages may not contain enough
:> entropy to allow a unique halting criterion. If you pad them
:> out with lots of zero bits, that may make the difference
:> between having a single unique possible message, and
:> having many such possible messages.
: And your point is still nonsense. Halting criteria is no
: problem. Use a large enough key.
Your objection appears to be nonsensical and contradictory! ;-)
Using a large enough key *makes* halting criteria a problem.
Your whole argument to date has been that the attacker can always get hold
of a halting criterion, even without padding. If you now say "use a large
enough key" to ensure no halting criterion exists, you seem to be
sabotaging your own argument.
Perhaps you are arguing that the key should be 128 bits bigger than normal
to make up for the plaintext in the padding ;-)
: Note that the one-bit followed by enough zeros to fill the
: block differs trivially from a bijection.
There's a categorial difference - one is a padding scheme - and the other
is a mapping between two sets ;-)
: Any message that does not end with an all-zero block is the padded
: image of some bit-string.
Sounds a bit wasteful. Why not do what you suggested and use "a one-bit
followed by enough zeros to fill the block."
Better still, why not use a bijective mapping between the set of 8-bits
files, and files with the desired block size.
:> : Very short messages happens frequently; for example an
:> : encrypted telnet session often sends individual key-strokes.
:>
:> : Do you know someone sending very-small messages with a new
:> : small key every time?
:>
:> I believe you can send messages of any size with PGP.
: Yes, I noted public key systems in the previous post, and that
: they have a unicity distance of zero, so no message is short
: enough.
You mentioned symmetric key distribution using PK systems.
Once a symmetric key has been distributed, what then?
Is that symmetric key used with a symmetric cypher??
Is that cypher applied to a message in plain text???
Will that message not have some redundancy in it????
Will that not result in a finite unicity distance (for that section
of the process)?????
It matters not if the PK algorithm only permits one possible message.
The PK algorithm need not be cracked to read the message. The message
can be read by obtaining the key to the symmetric algorithm. Someone
who can read the message might have no knowledge of the private key that
generated it.
: And do you actually know anyone sending only one message with
: each PGP key?
With each PGP *session* key? Yes.
AFAIK, everyone who uses PGP does this.
:> :> :> :> What about the man who forwards an encrypted message he has
:> :> :> :> intercepted back to his HQ for decipherment?
:> :>
:> :> :> The attacker that intercepts his message may be unable to
:> :> :> distinguish a correct decrypt from a random stream (without
:> :> :> lots of work).
:> :>
:> :> : Huh? If he's forwarding intercepted messages, then there's
:> :> : a small pool of possible plaintexts.
:> :>
:> :> Which may not be known to the attacker. He may not even
:> :> know the cipher it is encrypted under. His task might be to
:> :> strip off the outer layer of encryption and then pass the
:> :> message to his supervisor to deal with the (classified)
:> :> inner algorithm.
:>
:> : "Intercepted" means it came from an adversary. We're not
:> : talking about how the user might get lucky and not be
:> : attacked by that adversary. [...]
:>
:> I was not talking about that either. I was saying that some attackers
:> might not have the information necessary to mount the attack you
:> suggested. Consequently, defending against their (weaker) attacks
:> may still be worthwhile.
: As I wrote in the snipped part, one has to defend against
: chosen-plaintext in this case, where bijective padding is
: useless at best. Expecting that the message space won't have
: enough redundancy is clearly wrong if _any_ adversary knows
: the plaintext.
Obviously. Equally obviously, the contingent "if" need not be true.
: This example fails big.
No - you've still just failed to grasp it.
: [...]
:> : How about I give you message encrypted with a 128-bit key,
:> : but with over 128 zero bits at the end of the plaintext. It
:> : will have, as you defined the term, an "effective key space"
:> : of just one key. The termination criteria will be trivial.
:> : Want to try to recover the message?
:>
:> I'm no great cryptanalyst - that would probably be a waste
:> of my time.
:>
:> That such problems can be hard does not mean that adding known
:> plaintext to a message has no security implicactions, though.
:>
:> Even I would stand a better chance of identifiying the message
:> with the known plaintext added (even if I just guessed keys at
:> random) - since without that known plaintext, my chance of getting
:> the correct message (and knowing that I have it) is zero.
: Not true. To have a non-zero chance the attacker only needs
: recognizable plaintext, not known plaintext.
You didn't tell me anything else about the message in question,
and I made no assumption about its contents.
: Real-world traffic is recognizable.
Perhaps it was a session key. You didn't specify what it was.
: [...]
:> Nope. People can and do send short messages, and change key
:> before they exceed the unicity distance. Deal with it.
: Yet the only one you named, when specifically asked if you
: could, was PGP.
Yes.
: It's public key - unicity distance zero.
"Unicity distance of zero" only applies to the distributed session
key.
When considering the symmetric algorithm, it is quite proper to talk about
unicity distance - even if the PK algorithm section has only one possible
solution. If there's a break in the symmetric algorithm, that's where the
attack will come - not in the PK section. When attacking the symmetric
algorithm, unicity distance is a well defined notion, independent of the
PK section.
PGP is a suitable example of short messages being sent under a single
session key, where a better halting criterion could help an attacker.
: In addition, I know a lot of people who use PGP. I've set it
: up and provided support for a few. Never once have I heard of
: one who used one key per message (except maybe by accident).
: Have you?
One *session* key, yes.
:> *Even* in cases where the unicity distance is massively exceeded,
:> adding specific known plaintext is something to avoid - since it may be
:> able to provide a halting criterion that is either more concrete, or
:> faster to evaluate than other types of statistic about the plaintext.
: That's nuisance value. Don't bother.
Not good advice, IMO.
:> Alternatively, the halting criterion may be simpler, allowing a
:> brute-force parallel machine to be built using a smaller area of
:> silicon.
: No problem. If the chance of finding a key is too great, or
: the work factor too small, use a bigger key.
Bigger keys solve all problems eventually. If only they were free.
:> : I think we should design for the dangerous
:> : cases, not the ones where we get lucky.
:>
:> So (in this case) because some attacker might have complete known
:> plaintexts, don't bother trying to reduce known plaintext??
:>
:> Please. With known plaintext attakers can guess message keys,
:> confirm correct keys, etc. Without any known plaintext, they
:> can be stumped.
: Again, no problem. Use a big enough key.
Add 128 bits to the key to compensate for the known plaintext added
during the padding? Why not - since larger keys are free?
:> : Resist adaptive-chosen-plaintext; don't bother adding nuisance value
:> : against ciphertext-only. [...]
:>
:> Despite the fact that adaptive chosen plaintext attacks are relatively
:> rare in practice?
: Absolutely. Beating adaptive chosen plaintext implies beating
: off-line chosen plaintext, which implies beating known
: plaintext which implies beating ciphertext only.
That's true. It may not be pragmatic, though. Adaptive chosen plaintext
attacks are irrelevant in some applications.
: And adaptive chosen plaintext is not as rare as keys that go
: out of use before encrypting enough text to cover the unicity
: distance.
An unlikley statistic - any OTP key goes out of use before encrypting
enough text to cover the unicity distance.
:> I think one should defend against known-plaintext as well as is
:> conveniently possible.
: Then by all means use randomized one-to-many encryption and really
: beat it.
I believe I approve of this - though I'm not sure the defense is anywhere
near perfect. There's a downside in terms of cyphertext bulk, though.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Searching for a good PRNG
Reply-To: [EMAIL PROTECTED]
Date: Tue, 31 Oct 2000 00:56:14 GMT
David Schwartz <[EMAIL PROTECTED]> wrote:
: I like this quote too:
: "In practice, to avoid any residual bias resulting from non-random
: systematic errors in the apparatus or measuring process
: consistently favouring one state, the sense of the comparison between T1
: and T2 is reversed for consecutive bits."
: How can XORing a bit stream with a known sequence of bits make it any
: more or less random?
It wasn't claimed to make it less random - the technique was claimed to
"reduce bias".
With the normal technical meaning of the term "bias" (applied on the
level of bits), it looks like the scheme will work.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Calculating the redudancy of english?
Reply-To: [EMAIL PROTECTED]
Date: Tue, 31 Oct 2000 01:02:57 GMT
Simon Johnson <[EMAIL PROTECTED]> wrote:
: [EMAIL PROTECTED] (JPeschel) wrote:
:> Simon Johnson [EMAIL PROTECTED] writes:
:> >How does one calculate the redudancy of english?
:>
:> Use the index of coincidence.
: What is the index of coincidence, Applied crypto doesn't seem to give
: enough info for me to estimate the redudanct of english.
It does it for you, though. See p. 234, 2nd ed.
--
__________ 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
******************************
