Cryptography-Digest Digest #980, Volume #11 Thu, 8 Jun 00 21:13:01 EDT
Contents:
Re: Random IV Generation (Eric Lee Green)
Re: Observer 4/6/2000: "Your privacy ends here" (Dave Howe)
Re: DES question (Frank Gifford)
Re: Extending the size of polyalphabetic substitution tables
([EMAIL PROTECTED])
Re: Random IV Generation ([EMAIL PROTECTED])
Re: Some dumb questions (Mok-Kong Shen)
Re: Some dumb questions (Mok-Kong Shen)
Re: Brute forcing for Counterpane's Password Safe (Johnny Bravo)
Re: Random IV Generation (tomstd)
Re: Extending the size of polyalphabetic substitution tables (Mok-Kong Shen)
Re: Multiple encryptions (S. T. L.)
Re: PGP Self-Decrypt (S. T. L.)
My lastest paper on Block Ciphers (tomstd)
Re: Some dumb questions (William Rowden)
----------------------------------------------------------------------------
From: Eric Lee Green <[EMAIL PROTECTED]>
Subject: Re: Random IV Generation
Date: Thu, 08 Jun 2000 23:16:00 GMT
> o Use a PRNG to generate 8 random byte values (0-255)
Just use the random values themselves. You don't need to hash them. Random is
random.
Use a cryptographic-strength PRNG, *NOT* the 'rand()' function in your
computer's libc library. Bruce Schneir has a good one for Windows (Yarrow, see
http://www.counterpane.com ), and there exists a number of good ones for Unix
(and even not-so-good ones like my Ocotillo PRNG at
http://twofish-py.sourceforge.net :-). If you are using Linux or FreeBSD, the
situation is even simpler: simply request 8 bytes from the file "/dev/random".
Voila!
> should i just truncate the output to 64 bits, and if i do this will
> the output still be random?
In cryptography, you should more properly call these numbers "unpredictable"
rather than "random". "random", properly, refers to a statistical distribution
of a set of ordered pairs, and not all random distributions are unpredictable.
For example, rand() in your "C" library probably produces a statistically
verifiable random distribution -- yet is quite predictable (if you know a
small subset of values, you can predict the next set of values with 100%
accuracy).
But yes, if the set of values is unpredictable, then a subset of those values
will also be unpredictable. So you can safely truncate a 128-bit random value
to 64 bits and while you've chopped your entropy (you have half the bits to
play with!), you haven't chopped any more entropy than any other method would
chop.
--
Eric Lee Green [EMAIL PROTECTED]
Software Engineer Visit our Web page:
Enhanced Software Technologies, Inc. http://www.estinc.com/
(602) 470-1115 voice (602) 470-1116 fax
------------------------------
From: Dave Howe <DHowe@hawkswing>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,alt.politics.uk,alt.security.scramdisk,uk.telecom
Subject: Re: Observer 4/6/2000: "Your privacy ends here"
Date: Fri, 09 Jun 2000 00:29:28 +0100
Reply-To: DHowe@get_email_from_sig
In our last episode (<alt.security.pgp>[Tue, 6 Jun 2000 13:56:42
+0100]), "Morgan Holt" <[EMAIL PROTECTED]> said :
>Charles Bryant <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
>> In article <511.393a83f0.6d2e@scgf>, Phillip Deackes <[EMAIL PROTECTED]> wrote:
>> >The answer is simple. A massive campaign to get all email users to
>> >include certain words in every email they send.... they *cannot* deal
>> >with mass civil disobedience.
>>
>> They can't? So why haven't speed limits been abolished? About 70% of
>> people break the speed limit at some time or another.
>
>And 70% of stats are made up on the spot. The reason that a national speed
>limit exists in this country is because people generally believe it to be
>the safest option.
>
>HMG has a big PR job on its hands to convince everybody that they can have
>their letters opened by authorities.
Hmm. should be fun
Q: Why should you be allowed to open any email you like?
A: Because we have always opened any Post Mail we wanted, and want to
keep that power
Q: You do? why do you have permission for that? where is the law that
gives you the right to do so?
A: There isn't a law to stop us!
<stunned silence>
Q: Ok, so moving on; you don't have any safeguards in this RIP bill at
all, do you?
A: No, but that's ok, you don't have to have things written in the law
to prevent us, we won't do anything unreasonable
<second stunned silence as this answer is compared to the previous
one>
Q: And you expect us to believe this?
A: No, but it doesn't matter, since we cleared the House of Lords of
most of those who would object due to some moral imperative, and
replaced them with good loyal Party Members. muhahahaha!
------------------------------
From: [EMAIL PROTECTED] (Frank Gifford)
Subject: Re: DES question
Date: 8 Jun 2000 19:36:52 -0400
In article <[EMAIL PROTECTED]>,
tomstd <[EMAIL PROTECTED]> wrote:
>This is a bunch of BS and you should know better.
>
>For starters linear cryptanalysis can break DES faster then
>differential cryptanalysis, so even if your line of thinking
>*were* right (which it isn't) you are still wrong.
>
>The problem with saying 'DES can only provide O(2^56)
>resistance' is that you are assuming that differential
>cryptanalysis can always be performed, when in reality it
>normally can't. Which means the attack won't work.
>
>So in reality if you choose independant round keys, you can have
>upto 768-bit single-DES keys.
>
>If you wan't to argue this point (which I suggest you don't) why
>don't you consider the brute force search of the RC5 challenge
>which has a 64 bit key. RC5 with 12 rounds can be broken with O
>(2^53) effort yet *brute force* is what is being used. This is
>because only a handfull of ciphertexts are available.
>
>So your point is not valid, and please don't spread such lies.
Here's the quote from "Differntial Cryptanalysis of the Data Encryption
Standard", pg. 8:
"The full DES with independent subkeys (i.e., with 16*48=768 independent
key bits) is breakable by either a chosen plaintext attack or a known
plaintext attack with up to 2^61 steps." [I used the '^' instead of the
superscript notation in the book, BTW].
So although the work to break your DES-768 variant is a little more than
2^56, it's not a whole bunch more work. Certainly it is nowhere near
the 2^768 work that one would hope.
Besides, here is a theoretical paper and pencil attack against that variant
which DES is immune to. Encrypt a few (about 16) plaintexts with your secret
key K. Now give me those same plaintexts encrypted with the key (Key XOR 1).
Then encrypt the original plaintexts with (Key XOR 2). And so on for
the 768 bits of the key. Since the last round's key bits are not used
elsewhere in the algorithm, it's easy to see that the inputs to that round
will be the same. Simple differential analysis of one round and the sixteen
plaintexts will uniquely determine the key bits, one by one. In fact, this
can be done with paper and pencil - no computer necessary. A good evening's
work, no doubt.
Granted, this is a theoretical attack in that no opponent would provide
such data to you. But DES as it stands is immune to this theoretical
attack, while the variant is not.
The particular RC5 challenge is only a small number of blocks anyway, and
that is a much different thing than proving that a cipher is secure even
under theoretical conditions. Linear cryptanalysis of DES takes on the
order of 2^42 plaintexts, which is a huge number and not even something
which would appear in the real world. But it gives the people who use
the cipher a better feel about the strength.
In short, for all the trouble with DES, it does seem to be secure for its
56 key bit space. Not that it's worth much in this day and age, however. :)
As for your tone of voice in the post, I'll let your words speak for you.
-Giff
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Extending the size of polyalphabetic substitution tables
Date: Thu, 08 Jun 2000 23:35:10 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> 1. In modern block ciphers, the so-called S-boxes are columns of
> substitution tables. I was addressing the case of using more
> columns, keeping the classical context so that it is easier
> for me to explain. The basic ideas could be transfered to the
> modern designs.
Aha. The importance of using standard terminology is made obvious once
again. :)
This changes the question entirely. One I don't know how to answer, but
yes, larger S-boxes in general lead to better security, although
well-tuned smaller S-boxes might be better at defeating linear and
differential analysis. But a 256x256 S-box, even generated randomly, is
likely to do your job well when combined with other practices. (Ask Tom
-- S-Boxes alone do not make a good cipher. :)
> 2. As you pointed out, I didn't specify what PRNG to use. In the
> context of my post, it is also not necessary and in my opinion
> not appropriate to specify that. Why do you specifically call
> attention here of a special PRNG? Are you doing marketing for
> it, perhaps?
Again, wanting to use the tables as S-boxes changes the question
significantly. However, in the terms of the original post where tables
were being used as polyalphabetic ciphers it was functioning as a OTP --
and a OTP with a predictable pad is going to make for a lousy cipher. I
just wanted you to be aware of the consequences of using a poor
generator since the consequences are catastrophic.
As for marketing the BlumBlumShub generator, I haven't met any of the
three, nor any one who has met them. I don't *think* there are patents
or licenses on the thing (though you should check before integrating it
into a device or software). I suggest it because of the following quotes
from Schneier: "The simplest and most efficient complexity-theoretic
generators is called the Blum, Blum, and Shub generator...", "The
security of this scheme rests on the difficulty of factoring n.", "More
strongly the BBS generator is unpredictable to the left and
unpredictable to the right.", and finally, "However, for high-security
applications, such as key generation, this generator is the best of the
lot."
Since I thought you were going to use a PRNG for generating the
one-time-pad, BBS seemed like an obvious choice. :)
HTH :)
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Random IV Generation
Date: Thu, 08 Jun 2000 23:42:07 GMT
In article <[EMAIL PROTECTED]>,
tomstd <[EMAIL PROTECTED]> wrote:
> Please define the "Strength" of a IV.
A strong IV will help prevent dictionary attacks. A weak one (such as
the pathological case of "none") provides no help against dictionary
attacks.
Thus, it seems to me, one that is difficult to predict will make
dictionary attacks more difficult to mount. It is fufilling the same
role as password salt -- four salt bits increases the difficulty of a
dictionary attack 16 times. Ten salt bits increases the difficulty of a
dictionary attack 1024 times. By these feelings, the more 'difficult to
guess' bits in the IV, the more difficult a dictionary attack will be.
Thus an IV could be judged Strong or Weak based on how many bits of
entropy went into its generation.
(Never mind that they are practically infeasiable as it is with
reasonable ciphers, every layer helps. ;)
I hope this definition is good enough for conversational use. In a
mathematical paper I might wish a better one. :)
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Some dumb questions
Date: Fri, 09 Jun 2000 02:17:14 +0200
Bryan Olson wrote:
> I agree with Jim Gillogly's comments, and I think there's a
> danger that people will take the wrong lesson from some
> practical results. One might think that a lesson from
> Venoma is that the steps added to the OTP should have been
> made stronger. My opinion is the opposite - whatever effort
> was devoted to these additional measures should instead have
> been directed to using the pad properly.
Certainly you are right is stating that ensuring proper use of OTP
is what one should with all efforts do. I was trying to indicate
that there can be other matters that are also partly responsible
for failure, if OTP is misused. Thus in my opinion, while part of
the lesson of Venona is that OTP should never be reused, part of
the lesson is that we should also tighten complementary measures,
e.g. flattening frequency distributions. Anyway, in my humble
(and trivial) view one can never be careful enough in encryption
business and should at no time feel entirely safe and thus neglect
employing the best available techniques or excercising stringent
controls in any even tinyest corner of one's system.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Some dumb questions
Date: Fri, 09 Jun 2000 02:17:07 +0200
Jim Gillogly wrote:
> It seems to me that you're not clear on how one determines that two
> messages have been encrypted with overlapping pads, and how to determine
> the amount of overlap. To do this, use a kappa test: slide the two
> ciphertexts against each other and count the number of coincidences
> at each offset -- i.e. the number of times characters match in the
> two strings. It's very fast and effective, and uses only single
> characters at each point. With a respectable-sized overlap of the
> random keypad, you get a strong peak in the counts.
>
> I suggest you try a few actual experiments with random numbers
> and English text to see how easy and effective it is.
I guess that flattening the frequency distribution with some appropriate
techniques would provide sufficient immunity to such techniques.
Further, if OTP is employed two times, it's likely, in my view, that the
use of two same or overlapping segments are done at widely separate
timepoints and therefore the pool of messages containing these is quite
large and hence the chance of hitting such favourable pairs is
correspondingly low, I suppose.
M. K. Shen
------------------------------
From: Johnny Bravo <[EMAIL PROTECTED]>
Subject: Re: Brute forcing for Counterpane's Password Safe
Date: Thu, 08 Jun 2000 20:28:50 -0400
On Tue, 06 Jun 2000 21:09:14 GMT, Rex Stewart <[EMAIL PROTECTED]>
wrote:
>My experiance with even "techo savvy" people is they
>cannot formulate _and_ remember passwords with that
>much "entropy" (please excuse if this is not the word
>you would use here).
Diceware rocks in this regard, if I die my scramdisk partition is
going with me. 103.39 bits of password. Going to be a cold day in
hell before it gets brute forced. :)
It is easy to make up mnemonic sentences to help you remember an 8+
word passphrase since you are using actual english words.
--
Best Wishes,
Johnny Bravo
"The most merciful thing in the world, I think, is the inability
of the human mind to correlate all it's contents." - HPL
------------------------------
Subject: Re: Random IV Generation
From: tomstd <[EMAIL PROTECTED]>
Date: Thu, 08 Jun 2000 17:31:07 -0700
In article <8hpb0c$q1i$[EMAIL PROTECTED]>, sarnold_intertrust@my-
deja.com wrote:
>In article <[EMAIL PROTECTED]>,
> tomstd <[EMAIL PROTECTED]> wrote:
>
>> Please define the "Strength" of a IV.
>
>A strong IV will help prevent dictionary attacks. A weak one
(such as
>the pathological case of "none") provides no help against
dictionary
>attacks.
>
>Thus, it seems to me, one that is difficult to predict will make
>dictionary attacks more difficult to mount. It is fufilling the
same
>role as password salt -- four salt bits increases the
difficulty of a
>dictionary attack 16 times. Ten salt bits increases the
difficulty of a
>dictionary attack 1024 times. By these feelings, the
more 'difficult to
>guess' bits in the IV, the more difficult a dictionary attack
will be.
>Thus an IV could be judged Strong or Weak based on how many
bits of
>entropy went into its generation.
>
>(Never mind that they are practically infeasiable as it is with
>reasonable ciphers, every layer helps. ;)
>
>I hope this definition is good enough for conversational use.
In a
>mathematical paper I might wish a better one. :)
>
The thing is that your IV don't need to be random at all... so
how does 'randomness' or strength come into this at all?
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Extending the size of polyalphabetic substitution tables
Date: Fri, 09 Jun 2000 03:05:14 +0200
[EMAIL PROTECTED] wrote:
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > 1. In modern block ciphers, the so-called S-boxes are columns of
> > substitution tables. I was addressing the case of using more
> > columns, keeping the classical context so that it is easier
> > for me to explain. The basic ideas could be transfered to the
> > modern designs.
>
> Aha. The importance of using standard terminology is made obvious once
> again. :)
>
> This changes the question entirely. One I don't know how to answer, but
> yes, larger S-boxes in general lead to better security, although
> well-tuned smaller S-boxes might be better at defeating linear and
> differential analysis. But a 256x256 S-box, even generated randomly, is
> likely to do your job well when combined with other practices. (Ask Tom
> -- S-Boxes alone do not make a good cipher. :)
But if you have the same high quality S-boxes, wouldn't it be better
if you could use more of them?? (In the original context I was discussing
using a larger substitution tabl, nothing more. There was no implication
that enlarging the table is necessarily coupled with a degradation of the
quality of the individual column of the table. There is in fact no such
coupling.)
> > 2. As you pointed out, I didn't specify what PRNG to use. In the
> > context of my post, it is also not necessary and in my opinion
> > not appropriate to specify that. Why do you specifically call
> > attention here of a special PRNG? Are you doing marketing for
> > it, perhaps?
>
> Again, wanting to use the tables as S-boxes changes the question
> significantly. However, in the terms of the original post where tables
> were being used as polyalphabetic ciphers it was functioning as a OTP --
> and a OTP with a predictable pad is going to make for a lousy cipher. I
> just wanted you to be aware of the consequences of using a poor
> generator since the consequences are catastrophic.
I wonder how you got the association with OTP at all in this thread. A
classical polyalalphabetical substitution has by itself nothing to do with
OTP. In fact OTP was invented much much later than that. There is of
course on the other hand no exclusion in usage of the two, i.e. you can
use both in combination. But that is not relevant here, isn't it?
> As for marketing the BlumBlumShub generator, I haven't met any of the
> three, nor any one who has met them. I don't *think* there are patents
> or licenses on the thing (though you should check before integrating it
> into a device or software). I suggest it because of the following quotes
> from Schneier: "The simplest and most efficient complexity-theoretic
> generators is called the Blum, Blum, and Shub generator...", "The
> security of this scheme rests on the difficulty of factoring n.", "More
> strongly the BBS generator is unpredictable to the left and
> unpredictable to the right.", and finally, "However, for high-security
> applications, such as key generation, this generator is the best of the
> lot."
>
> Since I thought you were going to use a PRNG for generating the
> one-time-pad, BBS seemed like an obvious choice. :)
But in my original post the only thing I wrote relating to PRNG was
use of pseudo-random numbers. (Note that not even the term
PRNG occured there.) It is understood that these numbers must
come from some PRNG and that those who actually do what I said
there will naturally take care to choose one appropriately. Please tell
me why I should have recommended any specific PRNG there, even
if BBS or another one were my most favourite PRNG. If you are
convinced of the superiority of BBS, I don't have any objection. But
to bring out the issue that BBS is good is not relevant for the present
thread in my humble view. You could warn that, if one uses pseudo-
random numbers (the 3rd alternative in my original post) then one
should take care to use a crypto strong one. That would be o.k.
(Suppose the topic were about getting stuffs print out from computer.
I would suggest using a laser printer. The analogy of your BBS above
would be your saying using a HP Laser Jet. Do you see my point?)
Concerning your last sentence, let me once again remark that this
thread does not deal with one-time-pad at all.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (S. T. L.)
Subject: Re: Multiple encryptions
Date: 09 Jun 2000 00:58:02 GMT
<<Secretly, we also have another encryption program D. It
isn't public knowledge, but what we really do is take our
data files and encrypt them with D. Then we take the D
output and feed that into E. Programs D and E know
nothing of each other; each is meant to be used as a
stand-alone encryption engine. D also appends some
cleartext at the beginning of it's output, but of course
E encrypts that so our use of D is *mostly* a secret.>>
Your use of D is a complete secret unless E is broken.
<<I've heard that this hypothetical case is a bad idea, and
not just because of any false sense of security. Someone I
respect tells me that the result is actually LESS secure
than using either D or E alone.>>
It's actually not, and this method increases security. Both D and E have to be
broken for the message to be revealed. Only if E somehow undoes D's encryption
will it be weaker, but if the ciphers are unrelated, the chance of this
happening is basically too low to be considered. For example, 3DES, CAST, and
IDEA aren't related in any way, so you could use all three of them in sequence
for really good security (all 3 would have to be broken or brute-forced).
<<Let's say that word leaks out that we're using D before we
use E. Someone uses this knowledge to come up with
frequency distribution or some other pattern for D's
output. Perhaps it gives them a minor leg up on what output
to expect from E.>>
But plaintext fed into E has even more patterns. Just like compressing before
encrypting, it can only be a good thing unless your cipher sucks.
-*---*-------
S.T.L. My Quotations Page at *** http://quote.cjb.net *** is being
REORGANIZED. Comments are welcome. *392* quotations and growing!
Now playing: Half-Life Now learning: C programming (Hello, World!)
------------------------------
From: [EMAIL PROTECTED] (S. T. L.)
Subject: Re: PGP Self-Decrypt
Date: 09 Jun 2000 01:00:23 GMT
<<I've heard that new versions of PGP have a "self-decrypt" mode
that lets you send encrypted data to someone without PGP. But
how does this work?>>
Obviously it works by attaching a little program at the top of the data, much
like self-extracting files work.
<<If the recipient doesn't need PGP, then this can't support
public-key encryption, right? Does it ask for a password?>>
No, it will have to be symmetric (conventional) encryption. But of course it
will ask for a password, just like a password-protected self-extracting PKZIP
file. (And PGP's strength will be about a kazillion times more than PKZIP's.)
<<If it uses a password to decrypt, isn't it vulnerable to
brute-force attacks?>>
Of course, like every other cipher in existence excluding OTP.
<<If it doesn't even need a password, doesn't that mean
that it can be "decrypted" by anybody that receives it?>>
This question is meaningless.
-*---*-------
S.T.L. My Quotations Page at *** http://quote.cjb.net *** is being
REORGANIZED. Comments are welcome. *392* quotations and growing!
Now playing: Half-Life Now learning: C programming (Hello, World!)
------------------------------
Subject: My lastest paper on Block Ciphers
From: tomstd <[EMAIL PROTECTED]>
Date: Thu, 08 Jun 2000 18:01:35 -0700
I have just finished the Draft of my latest paper. It's called
"On Cryptographically Strong F Functions"
And is available (sorry) only in Word97 format at
http://tomstdenis.com/ffunctions.zip
There are probably tons of little mistakes, I have yet to have
anyone proofread it...
I am open to critiques :)
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: [EMAIL PROTECTED] (William Rowden)
Subject: Re: Some dumb questions
Date: 9 Jun 2000 01:08:18 GMT
In article <[EMAIL PROTECTED]>, Jim Gillogly <[EMAIL PROTECTED]> wrote:
> No, it was 8 bits long, representing a single character of 10
> messages encrypted with an overlap discovered in a 10-time-pad.
I'm sorry. In a different part of the thread the discussion was about
a pad used exactly twice. I assumed 10 characters at depth of 2,
while your example was 1 character at a depth of 10. Your post makes
much more sense to me now. It demonstrates the ease of determining
the plaintext at the point of pad reuse with as few as 10 messages.
> > It seems to me that the XOR of two ciphertexts encrypted with the same
> > random key is equivalent to transposed plaintext encrypted with a
> > cryptographically weak pseudorandom number generator.
>
> I don't see why it seems like that to you. I think we are looking
> at different problems.
Yes. I was trying to characterize the problem of deciphering the
result of XORing exactly two ciphertexts, without dragging probable
n-grams across it. The XOR of the ciphertexts is equivalent to the
XOR of the plaintexts in this context. I was imagining one of the
plaintexts arbitrarily as the message, and the other as a
(pseudorandom) key. This relates to question number 1 at the
beginning of the thread (the OTP reuse being question 2). How does
one decipher plaintext enciphered with a generator that is biased?
I'd explain more fully what I mean, but Real Life is calling at the
moment.
--
-William
PGP key: http://www.eskimo.com/~rowdenw/pgp/rowdenw.asc until 2000-08-01
Fingerprint: FB4B E2CD 25AF 95E5 ADBB DA28 379D 47DB 599E 0B1A
------------------------------
** 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
******************************
