Cryptography-Digest Digest #76, Volume #9 Sat, 13 Feb 99 00:13:03 EST
Contents:
Re: New high-security 56-bit DES: Less-DES ([EMAIL PROTECTED])
Re: RNG Product Feature Poll (R. Knauer)
Re: Transforming RC4 into a one-way hash function (Bauerda)
WW-2 German Enigma Machine For Sale (webb)
Re: New high-security 56-bit DES: Less-DES ("lyal collins")
Re: Transforming RC4 into a one-way hash function ("Peter K. Boucher")
Re: Program Idea (Casey Sybrandy)
Re: SCOTT COMPRESSION ("Eric W Braeden")
Re: RNG Product Feature Poll (Patrick Juola)
Re: hardRandNumbGen (Patrick Juola)
Re: Metaphysics Of Randomness (Patrick Juola)
Re: RNG Product Feature Poll (Patrick Juola)
Re: *** Where Does The Randomness Come From ?!? *** (Patrick Juola)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: New high-security 56-bit DES: Less-DES
Date: Fri, 12 Feb 1999 23:29:29 GMT
[EMAIL PROTECTED] wrote:
> 2. To send a message to Alice, Bob forms the first part of his
> desired message as a plaintext block of 64 bits:
>
> M1 = 0123...63
I'd suggest the first block should carry 64-M bits of plaintext
(like the others) and M bits of random padding, in order to
resist known plaintext attack. If we can't add random bits, for
fear they will be deemed "key", we could defend against partially
known plaintext by taking the M-bit pad from a hash of the entire
message.
> The Less-DES protocol may answer concerns regarding possibly
> diverging interpretations of export-free or WA terms -- since there
> is no additional key in Less-DES, of any kind, not even ignored, when
> security is enhanced from the 56-bit level.
Alas, the way the regulations are implemented in the US, it's the
government's interpretation that carries the day. The rules do not
say that 56-bit or even 40-bit encryption systems are freely
exportable, and neither does the latest statment of intentions to
"relax" export restrictions.
Instead, there's a "one-time review". The various agencies are under
no obligation to permit export based on adhearence to the letter of
the WA or even the agencies' own guidlines. If one wants to argue
that a system falls within legal limits, he'll be making that argument
to government cryptographers.
In 1995, Kent Briggs sought to export of a system using 40-bit
Blowfish. He was told he'd have to cut it to 32 bits. Given the
relative key agility of Blowfish versus ciphers that did receive
fast-track export approval, we can conclude that the reviewers
looked at how long the system would actually take to break, and
not merely at technical conformity to key length limits.
Since that time, export authority for civilian encryption
software has ostensibly moved to the Department of Commerce. In
practice this means that people who know nothing about crypto have
a chance to deny (but not approve) export before the request even
crosses the desk of anyone who knows what he'd doing.
--Bryan
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: RNG Product Feature Poll
Date: Sat, 13 Feb 1999 00:33:38 GMT
Reply-To: [EMAIL PROTECTED]
On Fri, 12 Feb 1999 15:02:45 -0700, "Tony T. Warnock"
<[EMAIL PROTECTED]> wrote:
>The probability of a 1-bit is 1/2. The probability of a 0-bit is 1/2. These are
>taken over the entire sequence. The excess of 1-bits over 0-bits in the first N
>bits is approximately N/log(N). This means that the frequency is 1/2 + 1/Log(N)
>for 1-bits.
I thought the Champernowne number was only defined for an infinite
number of bits.
>The absolute excess grows but the relative excess (which is the
>probability in the limit) goes to zero.
1) What is meant by "absolute excess"?
2) What is meant by "relative excess"?
3) What does any of this have to do with the infinite Champernowne
number?
Bob Knauer
"The one thing every man fears is the unknown. When presented with this
scenario, individual rights will be willingly relinquished for the guarantee
of their well being granted to them by their world government."
--Henry Kissinger
------------------------------
From: [EMAIL PROTECTED] (Bauerda)
Subject: Re: Transforming RC4 into a one-way hash function
Date: 13 Feb 1999 00:35:51 GMT
>You want to overcome RC4's weakness that the last few bytes of a long
>key have less effect than the first few bytes, right? What do you think
>of the following?
>
>1) At the time your hashing software is being developed, generate 1013
>"random" bytes, R, and hard-code them into your software.
Why bother with that many? I would say that only 8 to 256 bytes would be more
resonable.
>
>2) At run-time,
> a) take the message, M, and make a copy in the reverse-order, call it
>rM
> b) XOR M and rM together, making xM.
I don't like this. M is not used any where else, so if it has any symetric
patterns they might be killed. A palidrome passphrase will be completely
killed.
> c) XOR each byte in xM with a byte from R, resulting in K.
>
>Another way of stating this is:
> K[i] =3D M[i] XOR M[msg_length - i] XOR R[i modulo 1013]
>
>Use K as the key to RC4, and use RC4's output as the hash.
>
In my RC4 hash program, I just save the last 256 bytes from the input in a
circular buffer (repeating to fill the buffer if the input is less than 256
bytes) and add that on to the end of the input which is entered as the key ( no
matter how long it is). I then discard an additional 256 bytes (or 16 million
bytes if I want to slow down searches) before takening 16 or 20 bytes for the
hash.
David Bauer
------------------------------
From: electrovalue*nospam*@att.net (webb)
Subject: WW-2 German Enigma Machine For Sale
Date: 13 Feb 1999 00:38:48 GMT
Reply-To: electrovalue*nospam*@att.net
There is a WW-2 German Enigma Machine For Sale on the eBay
auction site. Also a post-WW-2 Swiss enigma linked to from the
following:
http://cgi.ebay.com/aw-cgi/eBayISAPI.dll?ViewItem&item=64840419
The auction ends Sunday night 2/14/99.
Webb WA2MOT
------------------------------
From: "lyal collins" <[EMAIL PROTECTED]>
Subject: Re: New high-security 56-bit DES: Less-DES
Date: Sat, 13 Feb 1999 11:39:05 +1100
>For M=14, Alice should take approximately one minute to solve the
>14-bit problem, while EFF's DES Cracker (a powerful DES cracker in
>hardware) would take approximately 75 years to solve the 70-bit
>problem. To compare, the EFF DES Cracker would take approximately 40
>hours for the usual 56-bit DES key.
These would seem to impose an upper limit of around 60 decrypted received
messages per hour - provided that machine isn't used for anything else.
Lyal
>Cheers,
>
>Ed Gerck
>
>=======================
>REFERENCES:
>
>[Ger99] Gerck, E., "Unicity, DES Unicity, Open-Keys; Unknown-Keys",
> in http://www.mcg.org.br/unicity.htm
>
>______________________________________________________________________
>Dr.rer.nat. E. Gerck [EMAIL PROTECTED]
>http://novaware.com.br
> --- Meta-Certificate Group member -- http://www.mcg.org.br ---
>
>
>-----------== Posted via Deja News, The Discussion Network ==----------
>http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: "Peter K. Boucher" <[EMAIL PROTECTED]>
Subject: Re: Transforming RC4 into a one-way hash function
Date: Fri, 12 Feb 1999 17:52:39 -0700
Bauerda wrote:
>
> >You want to overcome RC4's weakness that the last few bytes of a long
> >key have less effect than the first few bytes, right? What do you think
> >of the following?
> >
> >1) At the time your hashing software is being developed, generate 1013
> >"random" bytes, R, and hard-code them into your software.
> Why bother with that many? I would say that only 8 to 256 bytes would be more
> resonable.
> >
> >2) At run-time,
> > a) take the message, M, and make a copy in the reverse-order, call it
> >rM
> > b) XOR M and rM together, making xM.
> I don't like this. M is not used any where else, so if it has any symetric
> patterns they might be killed. A palidrome passphrase will be completely
> killed.
You're right. How about appending rM to M and _making_ it a palindrome?
--
Peter
------------------------------
From: Casey Sybrandy <[EMAIL PROTECTED]>
Subject: Re: Program Idea
Date: Fri, 12 Feb 1999 09:53:56 -0500
Get Norton Utilities. The new version can be set to wipe after your drive is
defragged.
John Doe wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> I am not aware of any program that functions in the manner that I am
> thinking of.. So here is my idea:
>
> While watching a defragmentation program run, I realised that my files were
> being scattered all over the place. Files that I would later wipe would
> still leave traces on other parts of the disk. Would it be possible to write
> a defragmentaion program that wipes as it defrags?
>
> Thank you for your time
>
> //||\\Jacob.Dav(no spam)@Usa.net//||\\
>
> -----BEGIN PGP SIGNATURE-----
> Version: PGP 6.0.2
>
> iQA/AwUBNsOx5dep1OgOEI6NEQKwpgCdFXSV83oYp5M1IeBkxwTt9MTQJzwAoNnd
> rmUVCpU/qvMWIkKf8M3f/nBO
> =9i4U
> -----END PGP SIGNATURE-----
------------------------------
From: "Eric W Braeden" <[EMAIL PROTECTED]>
Subject: Re: SCOTT COMPRESSION
Date: Mon, 8 Feb 1999 18:36:45 -0500
Horst Ossifrage wrote in message <[EMAIL PROTECTED]>...
>
>Compression of plaintext is a good idea before encryption. I commend you
>for proposing to write a compression program as a front end. It would be
>valuable since it would not have a HEADER BLOCK like pkzip. Without a
>header text it is harder to identify a correct cryptanalysis.
>
I agree that compression of plaintext before encryption is good.
I disagree that you should make compression a builtin frontend to your
encryption code. This will gain you little. Most will use their favorite
compression utility before encryption anyway. The fact that there
are standard headers in standard files, compressed or otherwise,
is an overstated danger. Don't worry about it especially if you are
using CBC.
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: RNG Product Feature Poll
Date: 11 Feb 1999 10:47:09 -0500
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>On 10 Feb 1999 08:52:54 -0500, [EMAIL PROTECTED] (Herman Rubin)
>wrote:
>
>>If by TRNG, you mean one in which all sequences have the same
>>probability, you will not get it. What you will have to settle
>>for is one which is "probably" "close" to that.
>
>That is something that can determine experimentally by doing a
>complete audit on each subsystem of the TRNG, including subsystem
>diagnostic tests. I believe the term in Kolmogorov Complexity Theory
>is pac (probably approximately correct). If you can prove
>experimentally that a TRNG is pac-secure to an acceptable level, then
>it is "proveably secure" to that level.
Excuse me -- if you prove that something is "probably approximately
secure," than that counts as provable?
Um.... This is exactly what you've been complaining about w.r.t.
statistical testing; all you can achieve is a statment that something
is "probably" secure or "probably" unbiased to within a particular
approximation.
-kitten
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: hardRandNumbGen
Date: 11 Feb 1999 15:42:48 -0500
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>On 10 Feb 1999 08:53:19 -0500, [EMAIL PROTECTED] (Patrick Juola)
>wrote:
>
>>Depends. If it's a really good generator with a known bias, there
>>are mathematical techniques that will allow me to strip out the bias
>>and produced an unbiased stream.
>
>This brings up the question of whether anti-skewing changes the
>equiprobability of the generator. I suspect it does for the following
>reason.
>
>A TRNG must be capable of generating all possible finite sequences
>equiprobably. If it is biased, then is it not doing that. Anti-skewing
>procedures do not generate those sequences that under-representted
>because of the bias.
Um... This is simply incorrect. That's *exactly* what anti-skewing
procedures do.
Think of it this way. Assume you have a biased, but independent, bit
source that generates 1s with probability p > 0.5. Consider two
successive bits, x, y.
The probability of getting the sequence 1, 0 is p * (1-p).
The probability of getting the sequence 0, 1 is (1-p) * p, which is
identical to the above.
So if you output a 1 bit when you see the pair 1,0 and a zero bit
when you see the pair 0,1 (and nothing otherwise), then you've
got a provably unbiased output stream -- the bias has been scrubbed
from the input -- by the technique of throwing away everyting that
*isn't* unbiased, broadly speaking.
-kitten
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Metaphysics Of Randomness
Date: 11 Feb 1999 15:38:23 -0500
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>On 10 Feb 1999 08:39:42 -0500, [EMAIL PROTECTED] (Patrick Juola)
>wrote:
>
>>>>Opinions, from experts, cost money. Truthful opinions tend to
>>>>cost even more.
>
>>>Hmm... that must mean that the book I am now reading by Li and Vitanyi
>>>is just a bunch of falsehoods - because it costs me nothing to read it
>>>(I got it from the library).
>
>>Or that you're a tax-dodging scoundrel. I'll leave you to guess
>>which.
>
>How can someone who uses the very library they help pay for with their
>tax dollars be a "tax-dodging scoundrel"? Your comment does not
>compute.
Oh, you mean that you paid money for the availability of the library?
I guess it wasn't free, then. 8-)
>
>>Well, the key thing about the PRNG is that it's *PROVABLY* biased
>>for lengthy strings; this is why the key-enumeration or brute force
>>attacks work.
>>So if you are serious enough in your testing, you'll catch this
>>bias.
>>Or, you could simply analyze the design and catch the PRNG, which I
>>recommend instead.
>
>Bias is not the only consideration for crytpo-grade security. There is
>correlation too. A counter shows little bias but it is about as
>correlated as one could expect.
But this just means that it's biased for longer ranges.
Suppose that we had a bad generator that repeated itself every
ten thousand bits. This means that not all strings of length
10,001 are equiprobable, hence sequence bias.
Correlation is just another kind of sequence bias.
-kitten
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: RNG Product Feature Poll
Date: 11 Feb 1999 10:52:59 -0500
In article <79t1in$[EMAIL PROTECTED]>,
Herman Rubin <[EMAIL PROTECTED]> wrote:
>In article <[EMAIL PROTECTED]>,
>R. Knauer <[EMAIL PROTECTED]> wrote:
>>On 10 Feb 1999 09:03:45 -0500, [EMAIL PROTECTED] (Herman Rubin)
>>wrote:
>
>>>That many people use "random" in the sense of "equally likely"
>>>does not mean that the two should be confused. I suggest that we
>>>keep things clear by using "equidistributed" instead. Random
>>>sequences are unpredictable, but not necessarily equidistributed.
>
>>A random number generator for use with the OTP cryptosystem must be
>>capable of generating all possible finite sequences equiprobably or
>>else the ciphers will leak information in a significant manner, making
>>them unsecure.
>
>Will the amount of information leaked be significant? The amount of
>information in the exact number of 1's in a sequence of 10^6 bits is
>less than 12, so how useful would the information be? And what would
>the amount of leakage if only sequences which had this property were
>used?
>
>If there was still independence, but the bit probabilities were .51
>instead of .50, this would give a channel capacity of .0003/bit.
>If we can reasonably assume that the probability that a bit is 0
>given all preceding bits is between .49 and .51, this will be an
>upper bound, and not a good one.
>
>These bounds assume that the interceptor can actually use them.
>Let me ask the cryptographic experts here; how large a message would
>one need to have a reasonable chance at cracking it if the OTP used
>had bits with a known probability of .51, or even .6, of being 0?
Depends on what else you know about the message. In the extreme
case, where you know that the message must be one of a few strings,
you can read the probabilities straight off the binomial theorem
and you probably don't need more than a few words. As the message
space increases, you need more and more information. In practical
terms, if the probability is 0.6 but you don't know anything at all
about the message, then what you've essentially done is OTP-encrypted
the biased key with an unknown message.
As a practical rule of thumb, every eight bits of English text contains
about 1 1/2 bits of uncertainty. If you have more uncertainty than that
in your pad, reconstruction is likely to be very difficult.
-kitten
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Crossposted-To: sci.skeptic,sci.philosophy.meta
Subject: Re: *** Where Does The Randomness Come From ?!? ***
Date: 11 Feb 1999 15:35:29 -0500
In article <79v5lp$7fm$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
>In article <79s36i$9ds$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (Patrick Juola) wrote:
>> In article <79q88q$tho$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
>> >In article <[EMAIL PROTECTED]>,
>> > [EMAIL PROTECTED] wrote:
>> >> [EMAIL PROTECTED] wrote:
>> >>
>> >> > If you are handed a message without having *any* idea of the underlying
>> >> > language or cryptograhic system, the number of possible kinds of hidden
>> >order
>> >> > are as near to infinite as makes no odds.
>> >>
>> >> They're not near infinite, they're infinite, even if you put limits on the
>> >variety
>> >> and number of symbols, since the message could be a code for absolutely
>> >anything.
>> >
>> >Even if it's of a finite length ?
>> >
>> >> Simple proof: say the code represents an integer.
>> >
>> >> There's no integer it
>> >couldn't
>> >> be a code for, and there are countably infinitely many integers, so there
>are
>> >at
>> >> least countably infinitely many possible meanings for the code.
>> >
>> >Surely a 10-character code could ony represent a finite range of integers ?
>>
>> No. It can only represent 2^80 integers at the same time -- but there's
>> nothing to prevent any individual integer from being part of that set.
>>
>
>I know. I said a finite RANGE of integers, not a range of FINITE integers.
>Finite range = your 2^80 possible messages.
Yes. But the finite range is selected from an infinite range of
*potential* integers/messages. If you know absolutely NOTHING about
what message I might want to send, you don't know what my range of
potential messages is.
With a given finite-key cryptosystem, I can send any of a finite set
S of messages. Each message s in S is presumably a code for
a much larger set M of potential messages.
There is no reason to assume that M is finite.
>Aarons's assertion:
>"There's no integer itcouldn't be a code for, and there are countably
>infinitely many integers, so there are at least countably infinitely many
>possible meanings for the code."
>
>...is a non-secuitur IMO. Once a mapping has been agreed
>between what has been sent and the meaning, the number of
>meanings is limited by the messgae length.
No. The number of distinct meanings that can be sent with that system
is finite. The number of *potential meanings* that could be
encoded into that system is infinite.
And the "hidden order" under discussion is a property of the messages'
potential meanings, not necessarily that of the cryptosystems.
-kitten
------------------------------
** 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
******************************
