Cryptography-Digest Digest #908, Volume #8 Fri, 15 Jan 99 00:13:03 EST
Contents:
Re: What is left to invent? (Jayant Shukla)
Re: Practical OTP for secure two-person emailing (Anthony Stephen Szopa)
Re: sci.crypt intelligence test. ("R H Braddam")
Re: On the Generation of Pseudo-OTP ("Tony T. Warnock")
Algorithms as Keys & Security Thru Obscurity (was: Metaphysics Of Randomness) (Nicol
So)
Re: Cayley-Purser algorithm? (Jim)
Re: Cayley-Purser algorithm? ([EMAIL PROTECTED])
Re: AES and diffusion with 128-bit block length ([EMAIL PROTECTED])
Re: CRAZY hack.. 3D card running RC5/DES cracking client? (Myself)
Re: sci.crypt intelligence test.
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Jayant Shukla)
Subject: Re: What is left to invent?
Date: 14 Jan 1999 21:42:55 GMT
Alan Braggins <[EMAIL PROTECTED]> writes:
>[EMAIL PROTECTED] (Jayant Shukla) writes:
>> >(For those out there unfamiliar with the term, a random oracle
>> >is a mythical device which when presented with a question it
>> >gives a truly random answer, with the proviso that if the question
>> >has been asked before it gives the same answer as last time.
>>
>> If I take a rendom data string "S" and XOR it with a data
>> string "D", I get a completely random answer and the answer will
>> always be the same for a given that data string provided you do not
>> change "S". So, is this a rendom Oracle?
>No. If you don't change S, then if you change one bit of "D", you
>can predict that the result will be the previous answer with one
>bit changed. That's not a completely random answer.
My question was, how is a random oracle different from a
pseudo-random number generator? It generates a random number for
a given number, but that is true for any cipher. I just gave a
simple example of XOR function, which can be broken using
differential cryptanalysis as you showed and we all know that.
Again the question is, how is a random oracle different for a
pseudo-random number generator or another cipher if you (or someone
else) claim that these are new things in cryptography.
I just got hold of the paper by Bellare on Random Oracles. Hopefully
it will clear things up.
regards,
Jayant
------------------------------
From: Anthony Stephen Szopa <[EMAIL PROTECTED]>
Subject: Re: Practical OTP for secure two-person emailing
Date: Thu, 14 Jan 1999 15:49:05 -0800
Reply-To: [EMAIL PROTECTED]
Anonymous wrote:
> (Forgive me if someone already posted an idea like this.)
>
> Following on the thread of the "Practical TRNG," if Alice filled a 660mb
> file with a stream of true random bits, burned one CD-ROM copy for herself
> and one copy for Bob, then met Bob to give him the CD-ROM OTP, it seems
> like they could exchange years worth of personal email (textual at least)
> before needing to generate a new OTP and meet again to swap it.
>
> Alice starts at offset zero, Bob starts at offset halfway through the CD,
> and if Alice hits Bob's offset or Bob hits the end of the CD (or say, they
> come within 10% of their ends), then they begin to make provisions to
> create and exchange a new OTP. Each message contains an offset number to
> avoid synchronization problems.
>
> Each party could send ~330mb of data before the pad would be used up.
> This is quite a decent amount of text, certainly more text than I write to
> any single person in my lifetime.
>
> This seems to make an OTP-based TSCS quite feasible in real life, as long
> as you make sure you never re-use any portion of the pad, and that the pad
> (and original file) are securely deleted after use. Obviously the
> strongest attack would be to recover either Alice or Bob's pad.
>
> Protocol concerns such as Bob being assured that Alice REALLY made good
> TRNs for the OTP could be addressed by each of them burning their own OTP
> CD-ROMs and trading them, then agreeing to use XOR-ed data combining one
> byte from each CD-ROM to create one key byte.
>
> Muse, muse, muse...
>
> K
Been done.
go to http://www.ciphile.com
New Windows GUI version about to become available very soon.
------------------------------
From: "R H Braddam" <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: sci.crypt intelligence test.
Date: Thu, 14 Jan 1999 19:11:32 -0600
>
>Here is the intelligence test part.
>
>True or false?
>
Yes.
--
Rick [EMAIL PROTECTED]
Murphy's Law is the only sure thing in the universe.
------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
Date: Tue, 12 Jan 1999 09:51:03 -0700
Reply-To: [EMAIL PROTECTED]
Patrick Juola wrote:
> In article <[EMAIL PROTECTED]>,
> R. Knauer <[EMAIL PROTECTED]> wrote:
> >On 11 Jan 1999 16:41:29 -0500, [EMAIL PROTECTED] (Patrick Juola)
> >wrote:
> >
> >>>How about specific constants like ln(c) or c^1/2, etc.? Can these be
> >>>show to be random like pi on a case by case basis?
> >
> >>Yes. But on a case-by-case basis. It's *NOT* the case that
> >>all transcendental numbers are "random" in a cryptographic
> >>sense.
> >
> >But how does one do the characterization? What are the criteria for
> >deciding that a given transcendental constant produces a crypto-grade
> >random sequence? For that matter, how do we know that pi is random?
>
> Arcane and heavy mathematics, which I won't bore you with -- especially
> as I don't know the details myself. I don't even own the necessary
> textbooks to cite from any more, it was sufficiently long ago.
>
> But, as my half-assed remembrance tells me, the proof is actually
> expressed in terms like "pi is 'normal' to every base", where
> 'normal' means that every (finite) digit stream appears *somewhere*
> in the decimal expansion of pi.
>
> This is necessary, but not sufficient, for producing a cryptologically
> random stream.... for example, the stream
>
> 0.123456789101112131415161718192021...
>
> is also 'normal' to base 10, but is pretty pathetic as an OTP.
You're on the right track here. Some clarifications:
"Normal to base b" means that every finite digit stream occurs with the
proper frequency, that is 001 occurs (base 2) 1/8 of the time, etc. Borel
(1909) showed that with probability 1, all real numbers are normal to every
base. I do not believe that there is a proof that Pi is normal to any base.
The only normal numbers that I am aware of are those constructed like your
example. Champernowne constructed that example in the '30s (1930' for
y2k'ers). Similar numbers may be constructed in base 2: 011011100 etc. Note
that asymtotically there is an excess of 1 bits, n/ln(n) approximately for n
total bits. This doesn't hurt the frequency but it is annoying. The "strong
law of large numbers" is rather weak cryptographically. Dropping the leading
1, required in each base 2 number evens things out a bit. Then the excesses
alternate between 1's and 0's at n/(4ln(n)). Other normal numbers may be
constructed by concatinating the values of polynomials at the integers: using
x^2 in base 2 gives: 0,1,100,1001,10000,etc. One can also use the primes,
non-primes, etc. There is lots of literature.
I have also used the following schemes:
Construct Champernowne's number in bases 2,3,5, etc.
In base 3, map digits 1,2 to 1, 0 to 0.
In base 5, map digits 3,4 to 1, 0,1,2 to 0.
Etc.
Xor the sequences digit by digit.
Base 2: 0,1,10,11,100,101,110,111,1000,1001,1010,1011,1100,1101,1110,1111,...
Base 3:
0,1,2,10,11,12,20,21,22,100,101,102,110,111,112,120,121,122,200,201,202,210,211,212,...
Base 5:
0,1,2,3,4,10,11,12,13,14,20,21,22,23,24,30,31,32,33,34,40,41,42,43,44,100,101,102,103,...
and now:
Base 2: 01101110010111011110001001101010111100110111101111100011
Base 3: 01110111110111110010110111011111111011111110010110111101
Base 5: 00111000000010100000001011010101111101010111100000000000
XOR: 00100001100010001100110101100000111010011000011001011110
I haven't proved that the result is normal.
Another method is to concatenate de Bruijn sequences of increasing length. (A
subset of these are the shift-register sequences.)
01,0011,0010111, etc.
None of these methods seems good cryptgraphically.
Tony
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Algorithms as Keys & Security Thru Obscurity (was: Metaphysics Of Randomness)
Date: Thu, 14 Jan 1999 21:30:26 -0500
(This is somewhat longish, but if the subject interests you, read on.)
>From a mathematical but non-computational viewpoint, an encryption
function can be modeled as an indexed family of bijective mappings.
There is no requirement, one way or the other, that the indexes (keys)
are procedural descriptions of the mappings. The same family of
mappings can be implemented in more than one way, using different sets
of indexes.
For discussion purposes, consider an encryption function E modeled as a
family of 2^n mappings. One can implement the same family of 2^n
mappings in more than one way, using different indexes (keys).
One may have an algorithm (or device) that computes nothing but the
mappings in E. In this case, it may suffice to index E using n-bit
strings, with each string corresponding to 1 mapping in E.
Alternatively, one may use a universal computer. In this case, E may be
indexed by a set of 2^n (textual descriptions of) algorithms.
In both cases, the same family of mappings are realizable (by
appropriate choices of the key). In both cases, security of the
encryption function comes from uncertainty about the choice of the
mapping (from among 2^n possibilities). But in the latter case, the
keys can also be considered as algorithm descriptions.
My point is: (with reasonable assumptions) mathematically it makes no
difference whether you use algorithms as keys or not, so long as the set
of mappings remains the same. However, there are several important
*practical* differences.
1. Using algorithms as keys makes keys longer (or much longer, depending
on the chosen algorithm notation and its expressive power). In most
notations, very few random strings are well-formed algorithm
descriptions. Among those that are, very few compute something a person
would find useful. And among those that do, very few compute bijective
mappings. And among those that do, very few preserve the length of the
plaintext. And so on. In short, good keys are very sparse among all
possible strings up to a certain size.
2. Often times, it is useful to be able to use random strings as keys
and be able to count on that almost all random keys are good. Using
algorithms (directly) as keys makes key generation highly non-trivial.
In order to have a reasonable probability of generating a good key, one
may use a key generation algorithm that takes random bit strings as
inputs and outputs only algorithms good for keys. This trades
expressiveness for abundance of good keys. The more you move in this
direction, the closer you are to the usual block ciphers that takes
random bit-strings (as opposed to algorithms) as keys.
3. If one's willing to restrict the choice of mappings to a very "small"
set of "good" bijections, one can have very optimized
(hardware/software) implementation of the encryption function. Hardware
implementations of DES (and pretty much all practical ciphers), fit this
description. If one uses algorithm descriptions as keys and a universal
computer as the processor, it would be hard to have an optimized
implementation that can handle, say, 100Mbps, *on a consistent basis*.
For such a scheme, the performance will vary dramatically depending on
the choice of the key.
What about security through obscurity? Is there a difference between
relying on the secrecy of keys and relying on the secrecy of the
design? Like in the above discussion, the answer is "no" in theory, but
"yes" in practice.
The problem with obscurity (of design) is not that it hurts security in
itself, but that often it cannot be relied on. If you have a piece of
software that is shared only among several most trusted friends, and all
copies are properly protected, obscurity is fine. However, if you have
a successful cipher that is widely deployed, it is just dangerous to
assume that nobody knows how it works. (It is not that someone will
always bother to reverse engineer it or they will always be successful,
but if you are in the security business, you want to be conservative).
Cryptographic keys can be considered as parts of a system, and as such,
part of an instance of a general design. However, the thing that makes
keys special is that keys are designed to be highly (and easily)
changeable. The same cannot be said of other parts of a system in
general. If you have a system whose security rests solely on the
security of its keys, and you are unluckily enough to lose (the secrecy
of) them, you can still keep all the hardware and software. All you
need is to generate new keys and distribute them securely. But if your
system doesn't have a small portion that is highly changeable (and
therefore works like a "key") and you have to rely on the secrecy of the
*entire* design, you will have to obsolete all copies of software and
hardware when secrecy is compromised. It is not easy to make arbitrary
changes to a system (and make it function the same way in most aspects)
if it doesn't have a portion that's been designed to allow arbitrary
changes.
Nicol
R. Knauer wrote:
>
> On Thu, 14 Jan 1999 19:26:07 GMT, [EMAIL PROTECTED]
> (John Savard) wrote:
>
> >One could say, if one wished, that *all* cryptography is security
> >through obscurity, since it depends on the opponent not knowing the
> >key.
>
> That was my original point, admittedly somewhat philosophical.
>
> > But that viewpoint is not useful.
>
> What if the "key" is some small text string and some other parameters
> like a name and some page parameters that point to "useful"
> information that can be made into a secure key? What makes that key
> any different from any other key in general, albeit not being in
> conventional use?
>
> ...
>
------------------------------
From: Jim <[EMAIL PROTECTED]>
Subject: Re: Cayley-Purser algorithm?
Date: Fri, 15 Jan 1999 08:58:31 -0500
==============95037706A884C765F34565F5
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Sarah won contest prizes with Intel and esat. See this link for her esat award
http://www.esat.ie/youngscientists/intel.html . I am assuming she's the
young girl on the right and not the middle aged one on the left :)
Here's her intel award:
ftp://download.intel.com/pressroom/images/community/iiseft23.tif
and ftp://download.intel.com/pressroom/images/community/iiseff19.tif
Now, I feel bad for her that Intel put such poor publicity shots of her
on the net. The british and irish sites were much kinder. Anyway, the Intel
contest site is Intel International Science and Engineering Fair .
If anyone has pull with Intel, you should be able to get her contest
entry from them.
Since I'm free to speculate until the truth comes out, might this be one
of those precalculation algorithms where for the cost of one long
precalculation, you can encrypt multiple messages with different
but somehow related keys? Just my $.02.
==============95037706A884C765F34565F5
Content-Type: text/html; charset=us-ascii
Content-Transfer-Encoding: 7bit
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML>
Sarah won contest prizes with Intel and esat. See this link
for her esat award
<BR> <A
HREF="http://www.esat.ie/youngscientists/intel.html">http://www.esat.ie/youngscientists/intel.html</A>
. I am assuming she's the
<BR>young girl on the right and not the middle aged one on the left :)
<BR>Here's her intel award: <A
HREF="ftp://download.intel.com/pressroom/images/community/iiseft23.tif">ftp://download.intel.com/pressroom/images/community/iiseft23.tif</A>
<BR>and <A
HREF="ftp://download.intel.com/pressroom/images/community/iiseff19.tif">ftp://download.intel.com/pressroom/images/community/iiseff19.tif</A>
<BR>Now, I feel bad for her that Intel put such poor publicity shots of
her
<BR>on the net. The british and irish sites were much kinder.
Anyway, the Intel
<BR>contest site is <A HREF="http://www.intel.com/education/isef/index.htm">Intel
International Science and Engineering Fair</A> .
<BR>If anyone has pull with Intel, you should be able to get her contest
<BR>entry from them.
<P>Since I'm free to speculate until the truth comes out, might this be
one
<BR>of those precalculation algorithms where for the cost of one long
<BR>precalculation, you can encrypt multiple messages with different
<BR>but somehow related keys? Just my $.02.</HTML>
==============95037706A884C765F34565F5==
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Cayley-Purser algorithm?
Date: Fri, 15 Jan 1999 03:22:28 GMT
> Still nothing specific about exactly what the algorithm is, so I doubt their
> claim that it's more secure can be legitimate. Who tested it?
>
The MSN news here said she tested it as a part of her submittal. It was only
a children's science fair, albeit she did win the 1000 pound prize. The news
also stated she intends to publish it fairly soon.
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: AES and diffusion with 128-bit block length
Date: Fri, 15 Jan 1999 02:40:53 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Bruce Schneier) wrote:
> >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.
I want to clarify that Frog has 128 identical rounds that are parameterized in
an inner loop of 16 passes and an outer loop of 8 passes. The author of Frog
says this algorithm has 8 rounds, so I should go with his terminology, which I
did not use in my original post. HPC has 8 rounds with "about" ten dissimilar
operations in each round.
>>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.
>
> Good. I had been hoping that someone was doing an analysis like this.
> If you wish, I would be interested in commenting on your methodology.
>
> Bruce
> **********************************************************************
> Bruce Schneier, President, Counterpane Systems Phone: 612-823-1098
> 101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
> Free crypto newsletter. See: http://www.counterpane.com
I must work independently. You can comment after Feb. 1, the deadline for
submitting my paper.
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (Myself)
Crossposted-To: comp.sys.ibm.pc.hardware.video,comp.sys.ibm.pc.hardware.misc
Subject: Re: CRAZY hack.. 3D card running RC5/DES cracking client?
Date: Fri, 15 Jan 1999 04:43:36 GMT
On Wed, 30 Dec 1998 23:09:00 GMT, [EMAIL PROTECTED] (Mike
Hennessy) wrote:
>On Tue, 29 Dec 1998 11:24:39 GMT, [EMAIL PROTECTED] (Mr. Boffo)
>wrote:
>>On a BBS we were discussing the various kinds of funky
>>distributed.net clients people have come up with. There are
My brother's working one for his TI-85 calculator..
>>distributed.net client to crack code on 3D hardware?
>Not with the kind of hardware used in todays accelerators.
I was considering purchasing this badass video card that boasted an
i960 on board. It was going for ~$70 I think.. These things might be
reasonably common. Also, how versatile are the DSPs on sound cards,
modems, etc?
>As I see it, the reason someone could write a postscript client is
>that the printer has a programmable CPU which can download and execute
Okay, I draw the line here. It was nifty when Commodore disk drives
played music by shaking the head motor, but it's just gotten out of
hand now. We definitely need better things to do with our time.
------------------------------
From: [EMAIL PROTECTED] ()
Crossposted-To: talk.politics.crypto
Subject: Re: sci.crypt intelligence test.
Date: 15 Jan 99 03:56:59 GMT
Anthony Stephen Szopa ([EMAIL PROTECTED]) wrote:
: Is there any law restricting the creation and use of any random number
: generator? These come in many different forms and are included in every
: computer operating system / compiler in the world.
As long as the random number generator is not of good enough quality to be
used as the basis for a stream cipher, but otherwise there may be a
problem.
And, of course, while performing the XOR of numbers is legal, XORing a
whole file can be considered to be encryption with a large key.
Yes, the export laws are silly ... and, unlike software programs,
exporting, say, some 20-sided dice and an adding machine would not even be
noticed. But I think they will still try and get you with the export laws.
John Savard
------------------------------
** 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
******************************
