Cryptography-Digest Digest #999, Volume #11 Sat, 10 Jun 00 21:13:01 EDT
Contents:
ATTN: Severe Bug In Cryptobag (tomstd)
Re: Cryptographic voting (David A Molnar)
Re: My lastest paper on Block Ciphers (David A Molnar)
Re: Large S-Boxes (Terry Ritter)
Re: Large S-Boxes (tomstd)
Re: Observer 4/6/2000: "Your privacy ends here" (David Hopwood)
Re: Statistics of occurences of prime number sequences in PRBG output ("John A.
Malley")
CAST sboxes --- scarry (tomstd)
question of generating random challenges in Java ("Jean-Luc")
Re: Miller-Rabin Probabilistic Prime Number Test in Scheme (James Pate Williams, Jr.)
Re: Large S-Boxes (zapzing)
----------------------------------------------------------------------------
Subject: ATTN: Severe Bug In Cryptobag
From: tomstd <[EMAIL PROTECTED]>
Date: Sat, 10 Jun 2000 14:41:00 -0700
I found a very severe bug in Cryptobag today. The keys in
serpent are not being used properly. In the routine which I
hastily copied it expects the keylen in bits not bytes. As a
result all keys are being truncated.
I have fixed the bug, and as a precaution I will test all other
ciphers against known test vectors.
I am also making the ciphers directly accessible to the
programmers by using a common "key" type, so the helper routines
will work regardless of the cipher you pick.
Sorry about the mess, lesson learnt "Peer review is good!".
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: David A Molnar <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Cryptographic voting
Date: 10 Jun 2000 21:54:11 GMT
In sci.crypt zapzing <[EMAIL PROTECTED]> wrote:
> For goodness sakes, people could use laundry
> tickets for money if they wanted to. Actually
> that gives me an interesting idea about
> cryptographic money .... I'll have to work on
> it after I get the *cryptographic* *voting*
> thing figured out (hint).
Please be aware that there is a truly massive amount of prior work done on
cryptographic money and digital cash. Your idea may be new, but you should
take a look at previous schemes and their attacks to make sure that it
satisfies at least some of the requirements which have been advanced
now and then.
_Applied Cryptography_ is probably a good place to start and has good
references up through 1994. After that I'm not sure what kind of overview
exists. Maybe the thesis of Stefan Brands, which is due from MIT Press in
July or so...
-dmolnar
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: My lastest paper on Block Ciphers
Date: 10 Jun 2000 21:58:10 GMT
Trevor L. Jackson, III <[EMAIL PROTECTED]> wrote:
> products. Something you scribbled on a napkin while eating lunch should be
> presented on the original napkin, not on a bonded, watermarked paper. The rule
> is that fuzzy ideas should look fuzzy and carefully thought out ideas should
> look professional.
latex does not imply professional looking documents. especially if you're
just learning it. :-)
I would suggest learning latex mainly because it makes entering equations
much faster. Instead of trying to remember complicated key combinations,
define a few macros and then you can write almost as you would speak.
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Large S-Boxes
Date: Sat, 10 Jun 2000 22:14:34 GMT
On Sat, 10 Jun 2000 18:43:20 GMT, in <8hu285$53i$[EMAIL PROTECTED]>, in
sci.crypt zapzing <[EMAIL PROTECTED]> wrote:
>In article <[EMAIL PROTECTED]>,
> tomstd <[EMAIL PROTECTED]> wrote:
>> In article <8hs2m0$rgs$[EMAIL PROTECTED]>, zapzing <zapzing@my-
>> deja.com> wrote:
>> >In article <8hrtja$nte$[EMAIL PROTECTED]>,
>> > Simon Johnson <[EMAIL PROTECTED]> wrote:
>> >>
>> >>
>> >> I think i'm flogging a dead-horse here, but i'm after
>> evidence in 'a
>> >> dummies guide to' style to the pro's and con's of randomly
>> generated
>> >S-
>> >> boxes.
>> >>
>> >> I'm thinking 16x16 for a block-cipher i'm devolping (don't
>> hold u're
>> >> breath, i don't have 1/2 a clue what i'm doing :), i just
>> having fun.)
>> >>
>> >
>> >Well the DES s-boxes are quite small. They are
>> >designed to be optimal against differential
>> >cryptograpohy, but they are in the lowest
>> >9-16% of the similar sized sboxes in terms
>> >of resitance to linear cryptography. So much,
>> >I say,for trying to design them optimally.
>> >
>> >Big random sboxes are resistant to both
>> >differential and linear crypto :)
>> >And it's easy for mere mortals to "design" them.
>>
>> While they are easy to design, they are hardly secure. Just
>> wait till I publish my test results on 8x8 sboxes (which will
>> also be in my paper as well).
>
>I agree that 8X8 sboxes ared too small to design
>randomly. One should never use any sboxes smaller
>than 16X16 if they are designed randomly. I await
>your tests with 16X16 random sboxes.
I disagree: I think the statistics on random 8x8 boxes are quite
good. By that I do not mean that there is no possibility of weakness;
I mean that weakness is very unlikely. On the other hand, the
statistics on random 4x4 boxes are very worrisome indeed.
Different types of cipher constructions have different requirements in
S-box statistics, but we generally do not use a single box on its own
in any case. Then lightning must strike multiple times to expose
weakness, and that sort of strength distribution is not an attack
approach.
An 8x8 box takes 256 Bytes. A 16x16 takes 128k Bytes. We can have
512 different 8x8 boxes in that same space.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
Subject: Re: Large S-Boxes
From: tomstd <[EMAIL PROTECTED]>
Date: Sat, 10 Jun 2000 15:19:07 -0700
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Terry
Ritter) wrote:
>
>On Sat, 10 Jun 2000 18:43:20 GMT, in <8hu285
$53i$[EMAIL PROTECTED]>, in
>sci.crypt zapzing <[EMAIL PROTECTED]> wrote:
>
>>In article <[EMAIL PROTECTED]>,
>> tomstd <[EMAIL PROTECTED]> wrote:
>>> In article <8hs2m0$rgs$[EMAIL PROTECTED]>, zapzing
<zapzing@my-
>>> deja.com> wrote:
>>> >In article <8hrtja$nte$[EMAIL PROTECTED]>,
>>> > Simon Johnson <[EMAIL PROTECTED]> wrote:
>>> >>
>>> >>
>>> >> I think i'm flogging a dead-horse here, but i'm after
>>> evidence in 'a
>>> >> dummies guide to' style to the pro's and con's of randomly
>>> generated
>>> >S-
>>> >> boxes.
>>> >>
>>> >> I'm thinking 16x16 for a block-cipher i'm devolping (don't
>>> hold u're
>>> >> breath, i don't have 1/2 a clue what i'm doing :), i just
>>> having fun.)
>>> >>
>>> >
>>> >Well the DES s-boxes are quite small. They are
>>> >designed to be optimal against differential
>>> >cryptograpohy, but they are in the lowest
>>> >9-16% of the similar sized sboxes in terms
>>> >of resitance to linear cryptography. So much,
>>> >I say,for trying to design them optimally.
>>> >
>>> >Big random sboxes are resistant to both
>>> >differential and linear crypto :)
>>> >And it's easy for mere mortals to "design" them.
>>>
>>> While they are easy to design, they are hardly secure. Just
>>> wait till I publish my test results on 8x8 sboxes (which will
>>> also be in my paper as well).
>>
>>I agree that 8X8 sboxes ared too small to design
>>randomly. One should never use any sboxes smaller
>>than 16X16 if they are designed randomly. I await
>>your tests with 16X16 random sboxes.
>
>I disagree: I think the statistics on random 8x8 boxes are
quite
>good. By that I do not mean that there is no possibility of
weakness;
>I mean that weakness is very unlikely. On the other hand, the
>statistics on random 4x4 boxes are very worrisome indeed.
>
>Different types of cipher constructions have different
requirements in
>S-box statistics, but we generally do not use a single box on
its own
>in any case. Then lightning must strike multiple times to
expose
>weakness, and that sort of strength distribution is not an
attack
>approach.
>
>An 8x8 box takes 256 Bytes. A 16x16 takes 128k Bytes. We can
have
>512 different 8x8 boxes in that same space.
I disagree: and I have proof. Check out
http://tomstdenis.com/sbox8.txt
Which has a distribution of DP and LP maxes for about 50,000 8x8
sboxes... I can send the program I used if you like too...
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!
------------------------------
Date: Sat, 10 Jun 2000 18:25:01 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Observer 4/6/2000: "Your privacy ends here"
=====BEGIN PGP SIGNED MESSAGE=====
Cinder wrote [re deniable encryption]:
> What about a program which encrypts 2 files at once using different keys?
> If only one file is specified, it encrypts a random string with a random
> key instead. Presumably you could then say that you only had one file
> encrypted, so you don't know the second key.
This is a well-known technique, but note that the order of the ciphertexts
must be randomised (otherwise giving the key to the second ciphertext will
be suspicious).
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOUJ5sTkCAxeYt5gVAQErogf+IGYJdNesddaxmw3xtOcUJuHBBs6x23Ut
GVFw5U3VNqc4EPFS9cf8/ncmXFgdtP0hXSBR/e2s7PaLuhsuFU7B4tYOZPDb/9Ku
spFzVFF0vnIQZumrCLwUSypqz8V6PF9K0Jr6NK/MsmD2bx8n7Cphhf1rkQO9jAGT
AdHAyhcKF5y2J8BvaW5WzT75GTCFFqg5uLQkiFMebX9OW1c73qZI1NNzsEbNzAKt
9gb0H+VCbiyecat1W7xeC2BviPOsAIbyQNmNeaIB5gTu8+kqpGCiX1/8E/XTEHPR
SI7n4wWdL6VL2kEPQA9LbXR/AynZIU3aaWKfoCNfzcShw+8HXVjd5g==
=9DjH
=====END PGP SIGNATURE=====
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: Statistics of occurences of prime number sequences in PRBG output
Date: Sat, 10 Jun 2000 16:08:28 -0700
John wrote:
>
> Odd. You would not be able to encrypt much data with just prime
> #s, as there aren't that many between 0 and 255. If you go
> higher, you even get less primes.
>
True, but that's drifting from the original question.
Take the keystream output of an asynchronous stream cipher that's L bits
in length, where L is the maximum length of a non-repeating keystream.
Partition the L bits into m bit blocks. Choose m such that each value
of an m-bit number occurs once in the keystream. Take L bits from a true
random bit source and partition it into m bit blocks the same way.
Now we have two sequences of m-bit numbers with values from 1 to M,
where M <= 2^m - 1, each value occurs once. The keystream is a
permutation of the sequence of integers from 1 to M. The random bit
stream is also a permutation of the sequence of integers from 1 to M.
And we assume the keystream passes statistical tests for "randomness" -
like the poker test, band and gap frequencies tests, etc.
There are M! permutations of the numbers between 1 and M, where M <=2^m
-1. Every one of the M! permutations is equally likely from a true
random bit source spitting out L bit long sequences, BUT, only a
fraction of the M! permutations are produced from the pseudorandom bit
generator spitting out L bit long sequences.
There are pi(M) prime numbers less than M, where pi(*) is the prime
counting function. Each one of these pi(M) primes occurs once in the
keystream and in the random bit stream. Sometimes 2, 3, 4, 5, 6 or more
primes, all less than M, occur in a row in the keystream sequence and in
the random bit sequence. Call these "substrings of primes, all less than
M."
I conjectured that the statistics for occurrences of substrings of
primes, all less than M, in keystreams of bitlength L from pseudorandom
bit generators are (drastically?) different from the statistics of
occurrences of substrings of primes, all less than M, in bitstreams of
length L from a true random bit source. And if true, then finding
substrings of primes, all less than M, in the ciphertext stream output
of a stream cipher would tell a cryptanalyst information about the
plaintext.
Does anyone know of any research in this area? Or am I on a wild goose
chase? (honk honk)
John A. Malley
[EMAIL PROTECTED]
------------------------------
Subject: CAST sboxes --- scarry
From: tomstd <[EMAIL PROTECTED]>
Date: Sat, 10 Jun 2000 17:01:17 -0700
This is bothering me that nobody knows how to make cast style
sboxes. The CAST designers don't even have websites, and
ENTRUST is fairly useless for technical information.
<rant>Couldn't it be possible they 'lied' about their
construction and nobody ever bothered to check?</rant> i don't
want to spread rumors or belittle them, but I find it very
disconcerning that I can't find a single document saying how
they made those sboxes. In the early 80's they talked about
making single nxn sboxes but never sboxes that way.
<rant ver2.0>Ever notice in CAST-128 they mix the output of the
boxes using various dyadic operators but in CAST-64 (the
original) they only use xor? Which operator makes
them "ideal"</rant ver2.0>
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: "Jean-Luc" <[EMAIL PROTECTED]>
Subject: question of generating random challenges in Java
Date: Sun, 11 Jun 2000 00:41:34 GMT
Hello all,
For a challenge-response authentication scheme, I need a 16-byte random
challenge. Below are the details , my question to the group is about the
scheme's security weaknesses.
The challenge will be generated in a Java component so the first options in
mind were the Random and SecureRandom classes. However, the SecureRandom
appears to be too slow and some threading problems in the Microsoft JVM do
not recommend it for a multiuser scenario. By the way, the users will be
distributed on a large geographic scale (the application is a web site). The
communication with the web server is done over SSL so sniffing is not an
issue.
According to the JDK documentation, "the Random class uses a 48-bit seed,
which is modified using a linear congruential formula. (See Donald Knuth,
<i>The Art of Computer Programming, Volume 2</i>, Section 3.2.1.)". The seed
would be the current time of the day. I don't have the book so don't know
how good the randomness is and what's the sequence's length.
My question is whether the strength would be improved or not by generating
the challenge as an MD5 hash of the Random() number appended to a timestamp.
Your feedback is highly appreciated.
Thanks,
J-L.
------------------------------
From: [EMAIL PROTECTED] (James Pate Williams, Jr.)
Subject: Re: Miller-Rabin Probabilistic Prime Number Test in Scheme
Date: Sun, 11 Jun 2000 00:55:57 GMT
; Miller-Rabin probablistic prime number test
; See _Handbook of Applied Cryptography_ by
; Alfred J. Menezes et al. page 139
(define sqrmod
(lambda (x m)
(remainder (* x x) m)))
; expmod modified from _Structure and Interpretation of
; Computer Programs_ by Harold Abelson et al. page 45
(define expmod
(lambda (a n m)
(cond ((= n 0) 1)
((even? n) (sqrmod (expmod a (/ n 2) m) m))
(else (remainder (* a (expmod a (- n 1) m)) m)))))
(define miller-rabin-iter
(lambda (j n s y)
(cond ((and (<= j (- s 1)) (not (= y (- n 1))))
(let ((z (sqrmod y n)))
(if (= z 1)
#f)
(miller-rabin-iter (+ j 1) n s z)))
(else (if (not (= y (- n 1)))
#f
#t)))))
(define miller-rabin-helper
(lambda (n r s)
(let ((a (+ 2 (random (- n 3)))))
(let ((y (expmod a r n)))
(if (and (not (= y 1)) (not (= y (- n 1))))
(miller-rabin-iter 1 n s y)
#t)))))
(define miller-rabin-calculate-r-s
(lambda (n s)
(let ((p (/ n 2)))
(if (odd? n)
(list n s)
(miller-rabin-calculate-r-s p (+ s 1))))))
(define miller-rabin-loop
(lambda (i n r s t)
(cond ((= i t)
#t)
(else
(if (eq? (miller-rabin-helper n r s) #f)
#f
(miller-rabin-loop (+ i 1) n r s t))))))
(define miller-rabin
(lambda (n t)
(cond ((<= n 3)
#t)
(else
(let ((lst (miller-rabin-calculate-r-s (- n 1) 0)))
(let ((r (car lst))
(s (car (cdr lst))))
(miller-rabin-loop 1 n r s t)))))))
(define first-primes-iter
(lambda (x)
(if (eq? (miller-rabin x 8) #t)
x
(first-primes-iter (+ x 1)))))
(define first-primes
(lambda (n x)
(cond ((= n 0)
'())
(else
(let ((prime (first-primes-iter x)))
(cons prime (first-primes (- n 1) (+ prime 1))))))))
(first-primes 20 2)
Output of a run of the above from a favorite Scheme environment:
Welcome to DrScheme, version 101.
Language: Graphical Full Scheme (MrEd).
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71)
==Pate Williams==
[EMAIL PROTECTED]
http://www.mindspring.com/~pate
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: Large S-Boxes
Date: Sun, 11 Jun 2000 00:36:33 GMT
In article <8htu11$qkn$[EMAIL PROTECTED]>,
"Scott Fluhrer" <[EMAIL PROTECTED]> wrote:
>
> Simon Johnson <[EMAIL PROTECTED]> wrote in message
> news:8hstkt$dik$[EMAIL PROTECTED]...
> > In article <8hsknh$bov$[EMAIL PROTECTED]>,
> > "Scott Fluhrer" <[EMAIL PROTECTED]> wrote:
> > >
> > > Simon Johnson <[EMAIL PROTECTED]> wrote in message
> > > news:8hrtja$nte$[EMAIL PROTECTED]...
> > > >
> > > >
> > > > I think i'm flogging a dead-horse here, but i'm after evidence
in 'a
> > > > dummies guide to' style to the pro's and con's of randomly
> > generated S-
> > > > boxes.
> > > >
> > > > I'm thinking 16x16 for a block-cipher i'm devolping (don't hold
u're
> > > > breath, i don't have 1/2 a clue what i'm doing :), i just having
> > fun.)
> > >
> > > So, you're think about an sbox that will take 128k of memory?
Well,
> > that'll
> > > work in the sense that (with high probability) there won't be any
> > > troublesome characteristics, however, an sbox that big won't fit
in a
> > > conventional L1 cache. Assuming you're running it on any modern
CPU,
> > any
> > > sbox reference will take several cycles while the CPU waits for
the
> > memory
> > > (or more likely, the L2 cache) to retrieve it. Since this will
> > happen to
> > > almost every sbox reference, you're performance is likely to be
> > dreadful,
> > > and as has been pointed out, a secure block cipher is actually
pretty
> > easy
> > > to design if you are willing to settle for dreadful performance...
> >
> > I never even considered that. I suppose the real question is two
block
> > thru an 8x8 faster than one block thru a 16x16? Another important,
and
> > linked, question is how long does it take to retreive from the L1
cache?
> > Moreover, won't the operating system be using this cache?
> I think you don't quite understand what L1 cache is. In modern CPUs
(it was
> different in the past, and it may very well be different in the
future), you
> have CPUs that can do a single operation in 2-5 nsec, and you have
main
> memory (the memory that is cheap enough to have multiple megabytes
lying
> around) that might be able to do a single access in 50nsec. So that
the CPU
> isn't spending all its time waiting for the memory, CPU designers
insert a
> 'cache' between the two. This cache is designed so that the CPU can
access
> it in one 2-5nsec cycle (so the CPU doesn't slow down accessing it),
and
> usually the CPU can access multiple locations in the cache at once.
This
> cache is usually situated on the CPU chip, and is typically
4k-32kbytes
> large. This cache (actually, any cache, this is the definition of
"cache")
> works by storing the contents of recently accessed portions of the
main
> memory, in hopes that the program will access them again. So, if you
access
> a location once, the CPU stalls for the 50 nsec waiting for that
location
> again. But, if you access the location again, the CPU can read that
> location immediately. However, if the cache was full (every location
[1]
> was already holding a memory location), the L1 cache picks something
already
> in the cache and throws it out.
>
> And, because the L1 cache isn't big enough, computer designers insert
a
> second 'L2' cache between the L1 cache and the main memory. This
cache is
> larger (128k-1Megabyte), and slower (10-20nsec, IIRC).
>
> Now, suppose you have a 128k sbox, and a 32k L1 cache [2]. That means
that
> at most 1/4 of the sbox is currently in the L1 cache, even if your
> encryption routine makes no other data accesses, and has been running
long
> enough to read the sbox into the cache. Sbox accesses are essentially
> random, and so any sbox reference that your program makes has at least
a 3/4
> probability of missing the L1 cache, causing (at least) several cycles
of
> stall while the sbox contents are read from the L2 cache.
>
> And so, yes, 2 8x8 sbox accesses (two distinct 8x8 sboxes easily fits
in the
> L1 cache) are usually considerably faster than a single 16x16 sbox
access.
>
> And, as for whether the OS is using the cache -- I think you are
confusing
> that with 'disk cache', which is the same caching concept applied to
disk
> accesses. The L1 cache is a feature of the CPU, and every program
running
> on the computer, including the OS, does use it. Practically speaking,
only
> the program currently running on the CPU has its data in the cache.
>
> >
> > These points considered, it looks like the signs point to an
optimized
> > s-box. The problem with this approach is i don't even know where to
> > start.
> A better approach might be to do an initial design (using either
random
> sboxes, or no sboxes), and see if you can break it. If you can't,
simplify
> the design. Breaking ciphers teaches you much more than just
designing
> them.
>
> [1] Actually, L1 caches usually can't hold any memory location in any
cache
> element -- there are usually constraints. That can be ignored for
this
> overview
>
> [2] L1 caches are often split up between 'instruction' and 'data', so
a 32k
> L1 cache can usually hold only 16k worth of sbox data. I will ignore
this.
It would depend on your algorithm design, in conjunction
with your hardware, wouldn't it? I mean you caould have
an algorithm that sends out some data to be run through
an sbox, does some other neet stuff, then the data that
was sent out comes beck from the sbox device, all nice
and sboxed up, just in time to be processed further.
--
If you know about a retail source of
inexpensive DES chips, please let
me know, thanks.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
** 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
******************************
