Cryptography-Digest Digest #871, Volume #8 Sat, 9 Jan 99 13:13:04 EST
Contents:
Re: Secure Method Intact ([EMAIL PROTECTED])
Re: Well-written books on mathematics ? ([EMAIL PROTECTED])
Re: On the Generation of Pseudo-OTP (R. Knauer)
Re: On the Generation of Pseudo-OTP ("Trevor Jackson,III")
Re: On the Generation of Pseudo-OTP (R. Knauer)
Re: On the Generation of Pseudo-OTP (R. Knauer)
Cubes Inside Squares
Re: AES and diffusion with 128-bit block length ([EMAIL PROTECTED])
Re: AES and diffusion with 128-bit block length (David Crick)
Practical True Random Number Generator (Anthony Stephen Szopa)
Re: On the Generation of Pseudo-OTP (Paul L. Allen)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Secure Method Intact
Date: Sat, 09 Jan 1999 13:47:34 GMT
In article <#prraq5O#GA.222@upnetnews05>,
"hapticz" <[EMAIL PROTECTED]> wrote:
> after fiddling with des, blowfish, rsa and others, i have discovered a
> truely secure process.
>
> it is within my wifes head, it is completely secure and public. only she and
> her women friends understand how it works and are able to utilize it with no
> hindrance to/from any known government. it allows them to communicate
> across vast reaches of topics and cultures yet requires no visible
> parapernalia other than the air between their mouth and ears.
>
> i have no clue as to how they are able to totally obfuscate the most mundane
> of ideas topics and concepts into a stream of completely random utterings
> and vocalizations.
>
> maybe some day they will reveal this marvelous system to me, but for now,
> oh welll......
>
> has anyone else noticed this??
>
> --
> best regards
> [EMAIL PROTECTED]
>
>
If you really want to solve this problem take the Clinton approach
and sleep with a few of them. Maybe one of them will leak out the
secret code that they use. Of course what the hell does "sleep with"
mean even Clinton has no IDEA.
oh welll......
second good regards
David Scott
http://cryptography.org/cgi-bin/crypto.cgi/Misc/scott19u.zip
http://members.xoom.com/ecil/index.htm
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Well-written books on mathematics ?
Date: Sat, 09 Jan 1999 15:28:30 GMT
A few to look at:
Beginner:
"Algebra", Artin, Prentice Hall
"Elementary Number Theory", Burton, WCB Publishers
A little deeper:
"Algebra: An Approach Via Module Theory", Adkins & Wientraub, Springer
"A Course in Number Theory and Cryptography", Koblitz, Springer
"Prime Numbers and Computer Methods of Factorization", Riesel,
Birkhauser
Intermediate:
"A Course in Computational Algebraic Number Theory", Cohen, Springer
"Intro. to Elliptic Curves and Modular Forms", Koblitz, Springer
On Fri, 08 Jan 1999 12:54:57 -0500, Rx Video <[EMAIL PROTECTED]> wrote:
>Hello,
>
>I've had linear algebra some time ago, with all its vectors, rings,
>fields and matrices, but I didn't manage to quite understand it.
>Appears, that it is rather heavily used in the field of data encryption,
>so I would like to know, if there are some good books (well-explained,
>with examples and so on) which might be helpful with understanding at
>least the basics of encryption algorithms (why are they designed the way
>they are, and what makes them safe).
>Sincerely yours,
>
>Martin
Decrypt [EMAIL PROTECTED] with ROT13 for email address.
NOTICE TO BULK EMAILERS: Pursuant to US Code,
Title 47, Chapter 5, Subchapter II, 227, any
and all nonsolicited commercial E-mail sent to
this address is subject to a download and archival
fee in the amount of $500 US. E-mailing denotes
acceptance of these terms.
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Sat, 09 Jan 1999 15:42:16 GMT
Reply-To: [EMAIL PROTECTED]
On Fri, 8 Jan 1999 22:51:22 +0000, [EMAIL PROTECTED] (Paul L.
Allen) wrote:
>> That, however, is not verifiable - not even "statistically". The best
>> you can do is test a TRNG to see if it does something which violates
>> its prime directive, like output all 0s in worst case.
>Whoops! You can only check a finite length of output sequence. And it
>is perfectly possible for a working TRNG to generate a series of zeroes
>for whatever length of finite output sequence you care to postulate.
We discussed this exact thing at length a year ago and concluded that
what you say is theoretically correct, namely that 000...0 is a valid
output, but it is so unlikely for any practical length sequence that
it must be taken as a sign of malfunction.
Since then I reread one of Greg Chaitin's papers on randomness and
this time I paid attention to a small section where he calculates the
probability for such things to happen in terms of his algorithmic
complexity theory. For example he found that the probability for a
sequence pf length N to be less complex by 10 (that is, the sequence
can be compressed 10 additional bits) is 0.001. For sufficiently large
N that is inconsequential for purposes of security of the OTP system
as long such sequences are not a always occuring.
Therefore if a TRNG starts outputting unlikely sequences like 000...0
or 111...1, for any decent length N, that means it is broken, even
though such sequences are theoretically possible. But when we
discussed the prospect of testing for other "non-random" sequences,
for example ones with abnormal bias, posters here said that it is not
correct to filter such sequences or you will begin to leak
information.
>Yes, if I see the output is a million zeroes I will suspect that the
>generator is broken. But it *could* really be random output and the
>very next term in the sequence is non-zero. You have no way of knowing
>for sure - that sequence of a million zeroes is no less likely than
>any other sequence of a million digits.
You should ask how much information is leaked by interpreting that a
sequence of all 0s or all 1's means a broken TRNG. I believe the
answer is that no information is leaked - that is, by stopping the
TRNG and perhaps fixing it, you do not compromise the total
unbreakability of your OTP system. IOW, being safe doesn't cost you
anything in terms of security.
Bob Knauer
"We hold that each man is the best judge of his own interest."
--John Adams
------------------------------
Date: Sat, 09 Jan 1999 10:51:14 -0500
From: "Trevor Jackson,III" <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
R. Knauer wrote:
> I disagree. A TRNG can be made to crypto-grade specifications in that
> it would take more energy than exists in the Universe to break the
> OTP.
I disagree. The reason OTPs are valuable is that one cannot "break" them
when used properly. The reason an OTP cannot be broken is not that an
exhaustive search is infeasible, but that it is impossible. Given an
arbitrarily fast testing device applied to a message you could find all of
the possible decryptions that produce sensible messages. This set of
messages is identical to the set of all messages of the same length that
can be written.
A more concrete example is bed on two messages, available to the analyst
in both plan and ciphertext forms. There is no method the analyst can use
to associate each ciphertext with its associated plaintext. Given the
appropriate key values either plaintext could produce eaither ciphertext.
Thus one cannot speak of "breaking" an OTP that is used properly. Now if
ou have a copy of the pad... (but that's not part of crypto)
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Sat, 09 Jan 1999 16:07:33 GMT
Reply-To: [EMAIL PROTECTED]
On Sat, 09 Jan 1999 14:20:59 +0100, [EMAIL PROTECTED] wrote:
>> You don't believe in Hidden Variable theories, eh.
>No :-)
But how can you be sure, if they are hidden? :-)
>If there is a noise generator that produces some megabytes output with
>good statistical properties (same probability for all bitsequences that
>are short enough to be tested with the teststream) I'd use it.
Such a device is a TRNG if the noise you refer to is produced by a
physical process that is random, namely that all possible outputs of a
given finite length are equiprobable.
>I don't have any problem with this: If radioactive decay or transistor
>noise is deterministic and there is no way for the attacker to get
>enough parameters to calculate the resulting bitstream, so what?
That is the criterion for what Chaitin uses for his definition of
randomness in his algorithmic complexity theory, namely that one
cannot find a way to "reduce" the complexity by coming up with an
algorithm which is smaller than the length of the random number. In
your statement you would subsititue "parameters to calculate the
resulting bitstream" for "algorithmic reduction" in Chaitin's
statement.
But Chaitin goes on to show that it is impossible to decide by formal
means that there is no such algorithmic reduction possible. Therefore
unless you are willing to gamble that no one will ever find such
"parameters to calculate the resulting bitstream", algorithmic random
number generators must be ruled out for the OTP cryptosystem - since
it is not *proveably* secure.
The variation on this that I am interested in is the so-called "digit
expansion generator", like the BBP digit expansion generator for Pi
and other transcendental constants. If the inherent correlation in the
bitstream (because bits are calculated one after the other) does not
leak information then it might be suitable for a stream cipher. But
thus far no one here has critiqued that method in cryptanalytic terms.
One critique is to ignore the fact that the BBP calculation method is
for digit expansion and treat it as another PRNG. But it presumably
does not have one characteristic of a PRNG, namely it is not periodic
(because the underlying transcendental constant is not periodic).
>Maybe my suggestion is not the best, but what I expect when using
>quantum mechanic sources of noise is not a long-term periodicity but a
>bipass that causes my generator to produce more 0es that 1es or some
>short bitsequences more frequently than others. In this case it may be a
>good idear to hash the output of the RNG.
I still have a problem with a hash since it is algorthmic and can
introduce "non-randomness" into the sequence.
The method of mixing several bitstreams from different sources is
described by Schneier in his main book as a method of getting rid of
bias and more importantly correlation, but some people criticized even
that method - and nobody criticized their critique.
The upshot of all this was that if your stream generator requires that
you use a hash to "fix" it, then it is not a TRNG and cannot be used
for the OTP system.
>Of course hashing is reproducable, but it concentrates entropy.
The same could be said for text compression - but that does not
enhance security very much against sophisticated cryptanalytic
attacks.
Bob Knauer
"We hold that each man is the best judge of his own interest."
--John Adams
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Sat, 09 Jan 1999 16:18:59 GMT
Reply-To: [EMAIL PROTECTED]
On Sat, 09 Jan 1999 09:44:07 -0500, "Trevor Jackson,III"
<[EMAIL PROTECTED]> wrote:
>If the first 50 bits from the device are all ones do we have a biased
>device or an N-sigma event? I believe this question to be undecidable
>without further samples from the device.
But it does you no harm to treat such an occurance as prima facie
evicence that your TRNG is malfunctioning, since the likelihood of
such an occurance is extremely small.
IOW, by treating such a sequence as a warning that your TRNG *might*
be broken, you leak no information in your OTP ciphers. Just stop the
TRNG, inspect it for damage, fix it if necessary and begin again.
A perfect example would be unplugging the lava lamp on the SGI
Lavarand TRNG. (http://lavarand.sgi.com/)
Bob Knauer
"We hold that each man is the best judge of his own interest."
--John Adams
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Cubes Inside Squares
Date: 9 Jan 99 17:31:57 GMT
I was looking through some of my books about mathematics this morning.
One book had pictures of dissections of squares and rectangles into
distinct squares of smaller size. Previously, I had noted things like 32 =
27 + 5 and 128 = 125 + 3, for taking something in binary code into both
base-5 and base-3 at the same time.
Then it occured to me that I didn't have to code a message into base 503.
Because in a book I had looked at earlier, there were diagrams proving
that (1+2+3+4+...)^2 = 1^3 + 2^3 + 3^3 + 4^3 + ...
So instead of putting squares inside some very special squares, I could
put cubes of different size inside a wide selection of squares - any
square whose side was a triangular number.
As 10 is a triangular number, and a message can easily be encoded as
decimal digits using a straddling checkerboard, such as
0 1 2 3 4 5 6 7 8 9
A T O N E S I R
2 B C D F G H J K L M
6 P Q U V W X Y Z . /
one can then, after other steps, encode pairs of digits into groups of
three symbols, say from the alphabets +-, ABC, and abcd, with a table
like this:
0 1 2 3 4 5 6 7 8 9
0 * --- --+ AAA AAB AAC aaa aab aac aad
1 -+- -++ ABA ABB ABC aba abb abc abd
2 ACA ACB ACC aca acb acc acd
3 ada adb adc add
...
the arrangement can't be too regular, because of overlaps between the
squares if this pattern continues...
except for one odd symbol, marked by *, the three streams of enciphered
symbols can be fractionated independently.
Quite irregular in pattern...
John Savard
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: AES and diffusion with 128-bit block length
Date: Sat, 09 Jan 1999 16:40:27 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> In AC2 (section 15.3, p363 in my copy), BS writes:
>
> "There is some argument in the academic community whether a 64-bit
> block is long enough. On the one hand, a 64-bit block length only
> diffuses plaintext over 8 bytes of ciphertext. On the other hand,
> a longer block length makes it harder to hide patterms securely;
> there is more room to make mistakes."
>
> How do the various AES submissions perform and compare with their
> larger block sizes?
>
> David.
>
> --
After each algorithm has finished all rounds, all of them show the same
statistical distribution of bit changes. If 1 bit of plaintext us changed, on
the average 64 bits of ciphertext are changed. There is a deviation from 64
of similar amounts for all candidates. What I will report soon in my paper
that is being submitted, is how many rounds each algorithm takes to get
substantial avalanche and diffusion. For example Frog takes 32 rounds and HPC
takes 1 round to get avalanche that is near its final distribution. But then,
those 2 algorithms have very different numbers of rounds to complete their
algorithms. You will need to wait for the whole report, but for now you
should know that there is a noticeable difference between the algorithms for
how much excess avalanche is produced beyond the point at which a near-ideal
result is acheived.
> +---------------------------------------------------------------------+
> | David Crick [EMAIL PROTECTED] http://members.tripod.com/~vidcad/ |
> | Damon Hill WC '96 Tribute: http://www.geocities.com/MotorCity/4236/ |
> | Brundle Quotes Page: http://members.tripod.com/~vidcad/martin_b.htm |
> | PGP Public Key: (RSA) 0x22D5C7A9 00252D3E4FDECAB3 F9842264F64303EC |
> +---------------------------------------------------------------------+
>
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
Date: Sat, 09 Jan 1999 17:47:02 +0000
From: David Crick <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: AES and diffusion with 128-bit block length
[EMAIL PROTECTED] wrote:
> You will need to wait for the whole report, but for now you
> should know that there is a noticeable difference between the
> algorithms for how much excess avalanche is produced beyond
> the point at which a near-ideal result is acheived.
Cheers, I look forward to the report.
David.
--
+---------------------------------------------------------------------+
| David Crick [EMAIL PROTECTED] http://members.tripod.com/~vidcad/ |
| Damon Hill WC '96 Tribute: http://www.geocities.com/MotorCity/4236/ |
| Brundle Quotes Page: http://members.tripod.com/~vidcad/martin_b.htm |
| PGP Public Key: (RSA) 0x22D5C7A9 00252D3E4FDECAB3 F9842264F64303EC |
+---------------------------------------------------------------------+
------------------------------
From: Anthony Stephen Szopa <[EMAIL PROTECTED]>
Subject: Practical True Random Number Generator
Date: Sat, 09 Jan 1999 09:03:44 -0800
Reply-To: [EMAIL PROTECTED]
Practical True Random Number Generator
I think I have just come up with a practical device to generate true
random numbers.
Electronically attach a small closed container, such as a hollow sphere
or cube, to a computer. The inner surface of the container should be
covered with sensitive high density micro sensors. A suitable gas
should fill the hollow container. This gas of suitable density should
be heated to a suitable temperature under a suitable pressure. The
molecules colliding off the inner walls should be registered by the
micro sensors lining the inner surface of the container.
It is these registered random collisions over time that should generate
your random bits.
I'm sure someone with basic skills could have a very good working model
in a few weeks if not sooner.
Please give me one of your first production models or at least your
detailed plans so I can make one myself.
Thanks.
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (Paul L. Allen)
Subject: Re: On the Generation of Pseudo-OTP
Date: Sat, 9 Jan 1999 17:51:36 +0000
Reply-To: [EMAIL PROTECTED]
In article <[EMAIL PROTECTED]>
[EMAIL PROTECTED] (R. Knauer) writes:
> On Fri, 8 Jan 1999 22:51:22 +0000, [EMAIL PROTECTED] (Paul L.
> Allen) wrote:
>
> >> That, however, is not verifiable - not even "statistically". The best
> >> you can do is test a TRNG to see if it does something which violates
> >> its prime directive, like output all 0s in worst case.
>
> >Whoops! You can only check a finite length of output sequence. And it
> >is perfectly possible for a working TRNG to generate a series of zeroes
> >for whatever length of finite output sequence you care to postulate.
>
> We discussed this exact thing at length a year ago and concluded that
> what you say is theoretically correct, namely that 000...0 is a valid
> output, but it is so unlikely for any practical length sequence that
> it must be taken as a sign of malfunction.
*Any* pattern of output you specify is equally unlikely. All zeroes
is as likely, or unlikely as all ones, 123451234512345, 314159265359,
2718281828,... Well, they're all equally likely a priori. A posteriori
is another matter - whatever turned up, turned up.
> Since then I reread one of Greg Chaitin's papers on randomness and
> this time I paid attention to a small section where he calculates the
> probability for such things to happen in terms of his algorithmic
> complexity theory. For example he found that the probability for a
> sequence pf length N to be less complex by 10 (that is, the sequence
> can be compressed 10 additional bits) is 0.001. For sufficiently large
> N that is inconsequential for purposes of security of the OTP system
> as long such sequences are not a always occuring.
Even ignoring the strange English, I don't know what you're getting at.
There is nothing I know of in probability theory that says you cannot
toss an unbiased coin 100 times in a row and get 100 heads. Not only that,
getting 100 heads is neither more nor less likely than any other sequence
of heads and tails you care to name.
> Therefore if a TRNG starts outputting unlikely sequences like 000...0
> or 111...1, for any decent length N, that means it is broken, even
> though such sequences are theoretically possible.
I'd *suspect* it was broken. I'd check the circuitry. I'd see what
another model produced. But, unlike you, I would not conclude that
a TRNG outputting all zeroes *must* be broken. When you say "unlikely
sequences like 000...0" you are making a fundamental error. That sequence
is no more or less likely than any other sequence you could name of the
same length.
> But when we discussed the prospect of testing for other "non-random"
> sequences, for example ones with abnormal bias, posters here said that
> it is not correct to filter such sequences or you will begin to leak
> information.
That's the point. Every so often, a TRNG will produce the run "0", less
often it will produce the run "00", less often than that, it will produce
the run "000", etc. If you eliminated runs of n zeroes (for whatever value
of n you think indicates brokenness) you would be biassing the output of
the TRNG.
> >Yes, if I see the output is a million zeroes I will suspect that the
> >generator is broken. But it *could* really be random output and the
> >very next term in the sequence is non-zero. You have no way of knowing
> >for sure - that sequence of a million zeroes is no less likely than
> >any other sequence of a million digits.
>
> You should ask how much information is leaked by interpreting that a
> sequence of all 0s or all 1's means a broken TRNG. I believe the
> answer is that no information is leaked - that is, by stopping the
> TRNG and perhaps fixing it, you do not compromise the total
> unbreakability of your OTP system. IOW, being safe doesn't cost you
> anything in terms of security.
See above. You're decreasing the randomness from 1 bit of randomness
per bit of data to something less. How much less depends on how many
zeroes you have to see in succession before you filter them out, and what
other sequences you filter out for similar reasons.
--Paul
------------------------------
** 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
******************************
