Cryptography-Digest Digest #58, Volume #9 Tue, 9 Feb 99 08:13:03 EST
Contents:
Re: Intel's description of the Pentium III serial number
Re: Recluse Creates Encryption-Based Imagery (JTyburczy)
Re: Privacy, Traps and Frozen Hell (Terje Mathisen)
4096-bit block cipher ([EMAIL PROTECTED])
Re: IDEA Rounds (Colin Plumb)
Questions about pseudoprimes, testing primes (mathematical) ("Benjamin Johnston")
Re: *** Where Does The Randomness Come From ?!? *** (Patrick Juola)
Re: Metaphysics Of Randomness (Patrick Juola)
Re: Metaphysics Of Randomness (Patrick Juola)
Re: GPL'ed RNG (Patrick Juola)
Re: hardRandNumbGen (Patrick Juola)
Re: What is left to invent? (Paul Crowley)
Re: Metaphysics Of Randomness (R. Knauer)
Re: Metaphysics Of Randomness (R. Knauer)
Re: Encryption Algorithms ([EMAIL PROTECTED])
Re: Threat Models: When You Can't Use a One-Time Pad (R. Knauer)
Re: Threat Models: When You Can't Use a One-Time Pad (R. Knauer)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] ()
Crossposted-To: comp.sys.intel
Subject: Re: Intel's description of the Pentium III serial number
Date: 9 Feb 99 04:33:30 GMT
Roger Carbol ([EMAIL PROTECTED]) wrote:
: Anthony Naggs wrote:
: > The lower 64 bits
: > are different for each processor and have no independent meaning.
: So what's serial about it, then? The numbers must be part of some
: series if they are serial numbers.
Well, the series is indicated by those _other_ bits. The lower 64 bits
start with 1 (or 0), and are different for each processor. But they don't
mean anything else.
John Savard
------------------------------
From: [EMAIL PROTECTED] (JTyburczy)
Subject: Re: Recluse Creates Encryption-Based Imagery
Date: 9 Feb 1999 06:31:02 GMT
Here we go again.....
------------------------------
From: Terje Mathisen <[EMAIL PROTECTED]>
Subject: Re: Privacy, Traps and Frozen Hell
Date: Tue, 09 Feb 1999 09:10:54 +0100
[EMAIL PROTECTED] wrote:
[snipped message about extending a secret key with N unknown bits]
> equivalent -- say, the attacker is 15,000,000,000,000 times faster?
>
> Can we still favor that "one" in lieu of that very powerful attacker,
> which has even defined the very contrived privacy limits we have for
> maneuver? Can we escape the trap and outsmart the attacker? How long
> can we hold off the attacker from that secret? Can we hold off the
> attacker until Hell freezes over?
The simple answer to this problem seems to be that as long as the
attacker needs significantly more time to break the 56-bit key than the
recipient needs to decode the message (message block), then you can use
this to keep the message secret as long as you want.
If however the attacker can exhaustively search the 56-bit key space in
the same time as the recipient needs to decode using the the key, then
they would seem to be equal?
> Further, under the given M-DES protocol and in other modes of it, the
> effective bit-length faced by Carol can be much larger than 70-bits.
> It can even afford perfect secrecy -- one that cannot be broken even
> by an attacker with unlimited resources, so it is possible to prove
> that Carol could never break that mode. Not even if Carol owns the
> Universe and works until Hell freezes over...
>
> This will be discussed in next messages.
This is something I'd like to see!
Terje
--
- <[EMAIL PROTECTED]>
Using self-discipline, see http://www.eiffel.com/discipline
"almost all programming can be viewed as an exercise in caching"
------------------------------
From: [EMAIL PROTECTED]
Subject: 4096-bit block cipher
Date: Tue, 09 Feb 1999 10:43:10 GMT
4096-bit block cipher
The size of the block is 4096 bits or 512 bytes.
Inserted key is transformed to 256 bytes( effective keys)
using current encryption. There are three effective
keys: K1,K2,K3. If you use default key then K1=K2=k3=default.
K1 is interpreted as a sequence of automorphisms of a group
in 8-bit chained encryption.
K2 is interpreted as a sequence of automorphisms of a group
in 16-bit chained encryption.
K3 is interpreted as permutation of all double bytes in block.
Encryption follows in three steps:
1. A block is encrypted using 8-bit Alex chained algorithm
with the key K1.
2. A block is encrypted using 16-bit Alex chained algorithm
with the key K2.
First two steps give suitable dispersion of bytes in
the block.
3. Permutation of all 256 double bytes in block is made using
256 byte key K3.
This algorithm is implemented and has performance approximately 1Mb/sec.
The freeware executable, Delphi 4&Assembler source code and updated
algorithm description are available for download at
www.online.de/home/aernst
Please follow the link for 'Alex8x16x4096.zip' in download area.
Regards
Alex
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
Subject: Re: IDEA Rounds
From: [EMAIL PROTECTED] (Colin Plumb)
Date: Tue, 09 Feb 1999 10:00:51 GMT
In article <[EMAIL PROTECTED]>,
Dirk Mahoney <[EMAIL PROTECTED]> wrote:
> I know that the key schedule is constructed by a 25-bit left (?) shift,
> which doesn't seem that great (although I lack the knowledge to understand
> the importance of the sub-key generation bit).
The IDEA key schedule algorithm is very simplistic indeed. There is
a known weakness that all-zero subkey words are rather weak, and if the key
is mostly zero bits, you can get enough of those in a row to weaken
the whole cipher. There's a proposed improvement that XORs a constant 16-bit
word with each subkey word after scheduling. I'd suggest incorporating
that if you're going to be incompatible anyway. (I don't have the reference
handy to figure out what the constant is, but Applied Cryptography probably
has a reference.)
You could also go to a more sophisticated subkey generation algorithm.
For example, initialize a 129-bit LFSR (with dense coefficients) with
128 bits of user subkey and a 1 bit, and take output from that to
generate the round subkeys. It'll be nicely uniform.
> I understand that I need 6 * NUM_ROUNDS + 4 subkeys for the cipher, so is
> there any hassle (apart from any key management I'd have to do) with
> generating the subkeys directly? Sure (for standard 8 round IDEA) I'd need
> 832 bits, but that would surely put the cipher out of range of a brute force
> attack (I know at 128 it is anyway, but as I think I said earlier, I like a
> little paranoia).
Other than that, no problem. It'll work fine. Most ciphers are easily
extended to extra rounds.
--
-Colin
------------------------------
From: "Benjamin Johnston" <[EMAIL PROTECTED]>
Subject: Questions about pseudoprimes, testing primes (mathematical)
Date: Tue, 9 Feb 1999 21:36:30 +1100
Hi,
I'm a "newbie" to encryption, so excuse me if I'm asking a stupid question.
I'm trying to find primes to use for encryption (using methods that I can
sort of understand).
What I've found out so far...
All primes, p, should have the property that
m^(p-1) mod p = 1
for all 0<m<p, correct?
so if I have a number, n, which is not a prime (but I don't know that yet).
and on my first test I find that (using 2 for this example),
2^(n-1) mod n =1,
then n is said to be a pseudoprime (in this context), right?
What I would like to know is:
1. If know that n is a composite, and I find that 2^(n-1) mod n =1, does
this tell me anything about n (eg. info about it's factors)?
2. Given a composite number, n, can I determine all m where
m^(n-1) mod n = 1.
3. If I am using the above test, to find verify primes with very high
certainty, how many m should I try, and are there any rules for choosing an
m that is most effective at proving that a number is not prime.
(does anybody know where I can find out mora about the Euler Totient
Function (phi(n)), maybe even a proof that it works, or an explanation how
it manages to work).
Thanks
-Benjamin Johnston [EMAIL PROTECTED] (no spam please)
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: *** Where Does The Randomness Come From ?!? ***
Date: 8 Feb 1999 08:36:40 -0500
In article <[EMAIL PROTECTED]>, Calvin <[EMAIL PROTECTED]> wrote:
>Aaron boy babbled:
>> 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.
>> 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. Reals are a
>> trickier case, but it's possible that the same applies for them, in which case the
>> number of possible meanings is uncountably infinite.
>End Babbling
>When you say that a code (cipher?) represents an integer, do you mean in
>a (theoretical) practical system? Because in all applied systems, there
>is a block length.
Aaron is discussing codes here, and not cyphers -- and his reasoning
is quite correct. I could easily agree with a (secret) correspondent
that the message '0' means the entire text of Moby Dick, and the message
'1' means the entire text of the OED. More realistically, the famous
message "The Italian Navigator has reached the New World" was an
agreed-upon code to mean that Fermi had run his atomic reactor experiments
at the University of Chicago and that they had been successful. There's
no reason to assume that one is using a block-based cypher.
-kitten
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Metaphysics Of Randomness
Date: 8 Feb 1999 08:41:28 -0500
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>On 5 Feb 1999 09:11:19 -0500, [EMAIL PROTECTED] (Patrick Juola)
>wrote:
>
>>Well, a simple example, then. Perhaps oversimplified -- but what
>>do you expect for free in a seventy-line posting.
>
>The truth, perhaps? Or is that asking too much? What makes you think
>that the truth costs money to obtain?
Opinions, from experts, cost money. Truthful opinions tend to
cost even more.
>>Define a level of "unacceptable" bias
>
>What makes you think that tests for bias are conclusive? What if a
>PRNG passes such tests, and yet is not secure at all?
That's a separate question.
>>Implicit in this is are (mathematically) two probabilities, that
>>the statistician you hired can probabily give you the formulae
>>for.
>
>"Probably" give you the formulas? If he can't give the you the
>formulas, then he is a Snake Oil salesman - not a statitician.
Depends on how much you hired him for. You asked above why the
truth would cost money. You hire a cheap statistician, you may
not get the formula....
>>1 -- the probability that a good generator would fail this
>>2 -- the probability that a biased generator with bias right as
>> the threshhold would pass.
>
>You have reduced the whole question of using statistical tests down to
>testing for bias. I find that inadequate.
That's because all there *is* is bias. "Capable of generating all
finite-length strings equiprobably", remember? If there's some string
that is less (or equivalently, more) probable than the norm, then
that's a bias against (for) that string.
You may be thinking of bit-bias, which *is* too limiting a case. But
bias comes in a lot more flavors than that.
-kitten
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Metaphysics Of Randomness
Date: 8 Feb 1999 08:43:14 -0500
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>On 5 Feb 1999 09:11:19 -0500, [EMAIL PROTECTED] (Patrick Juola)
>wrote:
>
>>>Perfectly secure generators can produce numbers which do not pass bias
>>>tests,
>
>>But, in general, they don't -- this probability can be reduced
>>as far as you like.
>
>I maintain that statistical tests, including those for bias, are not
>suitable for determining crypto-grade randomness, even to a specified
>level of confidence.
>
>Consider the following proveably secure cipher. Let the OTP key be the
>same as the message. The resulting cipher is composed of all 0s, which
>is an extremely biased number. Yet that cipher is crypto-grade random
>because it is completely indeterminant - i.e., it leaks no
>information.
>
>If so, then I challenge you to decipher the following random number:
>
>000000000000000000000000000000000000000000000000000000
>
>[Don't try too hard. :-)]
>
>I realize that this is a stupid protocol, since you have to send your
>correspondent the key each time. Furthermore, since the key is
>identical to the message, why bother to send him the cipher (except to
>befuddle your attacker. :-) But that is not a valid criticism of my
>point above, since I do not have to justify the practical use of this
>cryptosystem.
>
>To make your point regarding the adequacy of ststistical tests, you
>have to show that bias in random numbers will result in some analytic
>weakness in the cipher. And if that is the case, then how do you
>rationalize the use of TRNG numbers for keys, since some of them are
>biased? Should you not filter those out so they won't weaken the OTP
>ciphers?
You're confusing bias in the *NUMBER* with bias in the GENERATOR.
-kitten
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: GPL'ed RNG
Date: 8 Feb 1999 08:51:58 -0500
In article <[EMAIL PROTECTED]>, Wm. Toldt <[EMAIL PROTECTED]> wrote:
>Paul Rubin wrote:
>>
>> In article <[EMAIL PROTECTED]>, Wm. Toldt <[EMAIL PROTECTED]> wrote:
>> >[EMAIL PROTECTED] wrote:
>> >>
>> >> Is there a GPL or LGPL random number generator that produces "good"
>> >> random numbers? rand() just isn't cutting it :P
>> >>
>> >> Joseph
>> >
>> >Do the letters GPL stand for some words in the English Language?
>>
>> General Public License; it refers to a particular software licensing
>> scheme ("copyleft") of the Free Software Foundation. It doesn't
>> specifically relate to cryptography. The GNU C compiler and most
>> other GNU programs, and the Linux kernel, are examples of GPL'd
>> software. See www.gnu.org for more info.
>
>I went to the GNU website looking for a definition of GNU, but could find
>none.
>
>Do the letters GNU stand for some words?
"GNU's Not Unix."
The MIT-ers are fond of "recursive acronyms."
-k.
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: hardRandNumbGen
Date: 8 Feb 1999 08:49:11 -0500
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>On 7 Feb 1999 09:35:58 -0500, [EMAIL PROTECTED] (Herman Rubin)
>wrote:
>
>>So a 10 megabyte file could be easily tested in such a way
>>that one could be fairly sure that the deviation from randomness
>>was at most 1%, and have good chance of acceptance if it was .1%.
>
>I am still having a problem relating this "deviation from randomness"
>you are testing for and the indeterminancy inherent in a TRNG. You are
>claiming that a property for infinite numbers applies to finite
>numbers, albeit with less than probability one.
>
>The thing that really bothers me is that "good chance" part in your
>statement above. If your tests are probabilistic with only a "good
>chance" of being correct, then how can they be relied on?
The "good chance" is quantifiable (as is the "fairly sure").
What is your acceptable degree of uncertainty? What is your
minimal "good chance."
Remember that, according to modern physics, it's only probabilistic
with a good chance that water will get hotter instead of colder
when placed over a lit gas burner.
-kitten
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: Re: What is left to invent?
Date: 9 Feb 1999 08:23:28 -0000
[EMAIL PROTECTED] (John Savard) writes:
> [EMAIL PROTECTED] (Terry Ritter) wrote, in part:
> >I would say that the only "provably secure" OTP is one for which we
> >have a provably random source.
> >But there *is* *no* PROVABLY random source.
> >So there *is* *no* PROVABLY secure OTP.
> [...] while your point is valid, I think it is a very minor one.
I don't know, it sounds like the sort of thing that might break the
hypnotic grip the "perfect" OTP has on the occasional people who visit
sci.crypt to argue against use of modern cryptography, or to tell us
about their "pseudo-OTP" schemes.
--
__
\/ o\ [EMAIL PROTECTED] http://www.hedonism.demon.co.uk/paul/ \ /
/\__/ Paul Crowley Upgrade your legacy NT machines to Linux /~\
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Metaphysics Of Randomness
Date: Tue, 09 Feb 1999 12:53:03 GMT
Reply-To: [EMAIL PROTECTED]
On 8 Feb 1999 08:41:28 -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).
Thanks for warning me.
>>What makes you think that tests for bias are conclusive? What if a
>>PRNG passes such tests, and yet is not secure at all?
>That's a separate question.
Yes, but it is a valid question - and a most important one at that. Do
you have an answer?
>Depends on how much you hired him for. You asked above why the
>truth would cost money. You hire a cheap statistician, you may
>not get the formula....
But then you could hire an expensive one and still not get the
formula.
What if your statistician were a Centurian?
>>You have reduced the whole question of using statistical tests down to
>>testing for bias. I find that inadequate.
>That's because all there *is* is bias. "Capable of generating all
>finite-length strings equiprobably", remember?
How could I forget.
>If there's some string
>that is less (or equivalently, more) probable than the norm,
>then that's a bias against (for) that string.
What is that norm? The probability of generating any string of length
N is 2^{-N} for each and every string. Is that what you are talking
about?
>You may be thinking of bit-bias, which *is* too limiting a case. But
>bias comes in a lot more flavors than that.
Actually I was thinking of k-bit group bias, with the "bit-bias" you
are talking about being the case k=1.
What other properties of numbers than k-bit group bias do you propose
to measure statisitcally to certify that a RNG is suitable for use
with the OTP cryptosystem in a secure manner?
Bob Knauer
"The world is filled with violence. Because criminals carry guns,
we decent law-abiding citizens should also have guns. Otherwise
they will win and the decent people will loose."
--James Earl Jones
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Metaphysics Of Randomness
Date: Tue, 09 Feb 1999 12:54:36 GMT
Reply-To: [EMAIL PROTECTED]
On 8 Feb 1999 08:43:14 -0500, [EMAIL PROTECTED] (Patrick Juola)
wrote:
>You're confusing bias in the *NUMBER* with bias in the GENERATOR.
Actually I am not - I am criticizing using bias in the NUMBER to
characterize bias in the GENERATOR.
How do you propose to measure bias in the generator in a practical
manner?
Bob Knauer
"The world is filled with violence. Because criminals carry guns,
we decent law-abiding citizens should also have guns. Otherwise
they will win and the decent people will loose."
--James Earl Jones
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Encryption Algorithms
Date: Tue, 09 Feb 1999 12:47:39 GMT
In article <[EMAIL PROTECTED]>,
Asher Pressman <[EMAIL PROTECTED]> wrote:
> Does anyone know of any good sites where i can find encryption
> algorithms? I've been looking for a while and i just can't find
> anything...
>
>
Please, take a look at
www.online.de/home/aernst
Regards
Alex
============= 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: Threat Models: When You Can't Use a One-Time Pad
Date: Tue, 09 Feb 1999 12:56:37 GMT
Reply-To: [EMAIL PROTECTED]
On Mon, 08 Feb 1999 23:03:25 GMT, Darren New <[EMAIL PROTECTED]>
wrote:
>> Truth is found in Reality. Falsity is a lack of Truth.
>Shame on you. Godel disproved this decades ago.
Godel disproved using formal systems to decide all truth and falsity.
My statement permits experimentation in the real world to decide truth
and falsity.
Bob Knauer
"The world is filled with violence. Because criminals carry guns,
we decent law-abiding citizens should also have guns. Otherwise
they will win and the decent people will loose."
--James Earl Jones
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Threat Models: When You Can't Use a One-Time Pad
Date: Tue, 09 Feb 1999 13:00:19 GMT
Reply-To: [EMAIL PROTECTED]
On Tue, 09 Feb 1999 02:24:26 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
wrote:
>Darren New wrote:
>> Shame on you. Godel disproved this decades ago.
>A liberal interpretation of G�del's results is that some true
>assertions cannot be proven without expanding the domain of
>discourse (which would create additional unprovable truths).
>So far as I can see this has no bearing on cryptology.
The original thread was the Metaphysics of Randomness, which is still
active. Mr. New is (was) a frequent contributor.
Since cryptology is about randomness and that is about computability,
Godel has a natural place in meta-mathematical discussions.
Bob Knauer
"The world is filled with violence. Because criminals carry guns,
we decent law-abiding citizens should also have guns. Otherwise
they will win and the decent people will loose."
--James Earl Jones
------------------------------
** 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
******************************
