Cryptography-Digest Digest #797, Volume #11 Wed, 17 May 00 08:13:00 EDT
Contents:
Re: Encryption of graphics by transposition ([EMAIL PROTECTED])
Re: About Hardware RNG (Will Dickson)
Interesting differentials in BREAKME (Mark Wooding)
Re: About Hardware RNG (Will Dickson)
Re: AES Comment: the Hitachi patent (Mok-Kong Shen)
Re: About Hardware RNG (Tom St Denis)
Re: Interesting differentials in BREAKME (Tom St Denis)
Re: Creating a good key-shedule (Tom St Denis)
Re: Fixed the stream cipher "Slime"? (Tom St Denis)
Re: (May 16, 2000) Cipher Contest Update (Tom St Denis)
web hosting for sci.crypt (Tom St Denis)
Re: An attack on reduced Pikachu (Tom St Denis)
Re: AES final comment deadline is May 15 (Mok-Kong Shen)
Re: AES final comment deadline is May 15 (Mok-Kong Shen)
Re: Crypto & UNICODE??? (Mok-Kong Shen)
Re: Creating a good key-shedule (David Blackman)
Introduction to zero knowledge proofs? (Volker Hetzer)
Re: Interesting differentials in BREAKME (Mark Wooding)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Encryption of graphics by transposition
Date: Wed, 17 May 2000 09:31:02 GMT
On Sun, 14 May 2000 11:54:05 GMT, [EMAIL PROTECTED] (John Bailey)
wrote:
>Are the usual encryption techniques, eg pgp, feistel ciphers, DES, etc
>really suitable for encrypting graphics, eg gif files, pgp files, etc?
>A more straightforward approach than using these substitution based
>ciphers would be remapping the location of pixels within the image,
>using any of several techniques which guarantee one to one mapping
>consistency.
(snip)
>What do you think?
Wow!!! You allude to techniques for remapping pixels which guarantee
1:1 mapping consistency. That would be a unitary transformation. (A
very macro unitary transformation) Unitary transformations are
reversible. Furthermore, it would make remapping of the image a group.
An image consists of a lot of pixels. If R represents a remapping, R^n
represents a remapping. Remapping thus generates a group. Last but not
least, the Fermat-Euler theorem (Hardy & Wright theorem 72, aka Euler's
generalization of Fermat's little theorem, Schneier page 203) therefore
applies, namely a^phi(m) =(congruent) to 1 mod m where phi(m) is the
Euler totient function. This reapplies all the math of RSA and
Diffie-Hellman without all the tedious large numbers (just large
rastersand some large numbers, the exponents) So, the technique lends
itself to public key codes, signatures, and key exchange. What else
would you like?
You forgot to ask about patentability.
Am I missing something? Have you applied for a patent? Is this now
all in the public domain?
Web
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Will Dickson)
Subject: Re: About Hardware RNG
Date: Wed, 17 May 2000 10:00:03 GMT
[EMAIL PROTECTED] (Guy Macon) wrote:
>How does the circuit determine the threshhold to compare the noise to
>in order to decide whether to call the current bit a 1 or a 0? Is this
>a logic input, comparator, op-amp, Transistor (FET or bipolar?) or what?
My circuit (I presume you mean that one, rather than the one Tom
found) uses split supplies (+/- 15V) and uses a plain op-amp
comparator to compare the signal to 0V. The noise source is
capacitively coupled so the capacitor output oscillates about 0V.
Will.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Interesting differentials in BREAKME
Date: 17 May 2000 10:04:18 GMT
BREAKME is a 10-round Feistel network proposed by Adam Durana. The F
function is based on a single 8 x 4 S-box:
: S is a 8 by 4 s-box.
: X is the 32-bit input.
: A,B,C,D are X divided up into 8-bit chunks.
:
: A' = S(A) | S(B)
: B' = S(C) | S(D)
: C' = S(A') | S(B')
: D' = S(B') | S(C')
:
: X' = (A', B', C', D')
:
: X' is the output of the function (32-bits).
The S-box has poor differential properties. An input difference of 0x65
gives an output difference of zero with propability 1/8. This can be
used to construct a 10-round differential characteristic with
probability 2^-15.
Let X, Y be random 32-bit words such that X (+) Y = 0x65000000. We
break X into A, B, C, D and Y into E, F, G, H such that A (+) E = 0x65
and B = F, C = G, D = H. S(A) = S(E) with probability 1/8, which then
causes the outputs from the F function to be identical.
We then construct a 2-round iterative characteristic.
65000000 00000000
| |
(+)<---- F ------+
| |
65000000 00000000 probability 1
| |
|------ F ---->(+)
| |
65000000 00000000 probability 1/8
Since there are 10 rounds, this characteristic holds for the entire
cipher with probability 2^-15.
I conclude that BREAKME is broken. Increasing the number of rounds to
44 *and* moving the key mixing to before the F-function would fix this
problem. I'd suspect that there are other problems too.
Watch out particularly for zero-output differentials. Adam: where did
you get that S-box: it's awful.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Will Dickson)
Subject: Re: About Hardware RNG
Date: Wed, 17 May 2000 10:09:24 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
>Well I have to figure out a power supply for the device. I think I may
>have a power supply (i.e batteries) for the mcu, but steal power from
>the rs-232 port for the rng.
YMMV on this one. I tried to do the same thing for my device: set one
of the RS232 control lines high (+12V-ish), the other low (-12V-ish)
and hey presto, split supply. Unfortunately, my 3rd-party comm driver
(a Java one - my code has to be cross-platform) took over the control
lines and used them for their proper purpose, ignoring my attempts to
hijack them! In the end I had to build a mains-based supply for the
device. That said, given the extent to which the lines were sagging
even when driving the LED's in my serial tester, I'm not sure that
they would have made adequate supplies even if I had got them to work.
> Since my friend showed me how to tie +10/-
>10 to get a +20v power (which is simple thing for you guys, but all new
>for me).
It's news to me as well. How does that work?
Will.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: AES Comment: the Hitachi patent
Date: Wed, 17 May 2000 12:37:45 +0200
Sundial Services wrote:
> It's pretty darned obvious that the patent laws, as they stand right
> now, aren't cutting the mustard anymore ... but "what else is the poor
> patent-reviewer to do?" Lots of people are getting patents that will
> not stand the light of day ... someday the Congress will finally decide
> that they have no choice but to review the patent-laws and change them
> ... and meanwhile, lots of patent attorneys are getting lots of money.
The 'minimum' of necessary reform is to have public review of
applications, same as with all European patents. This is not a
cure-all, but it at least offers competitors that have sufficient
resources in patent expertise good opportunities to present
materials against the submitted patent applications. Otherwise,
there could be problems even with very excellent patent
reviewers. Bruce Schneier mentioned years ago in this group
that US patents are going to have public reviews. But I have
never heard anything anywhere about that topic since then.
M. K. Shen
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: About Hardware RNG
Date: Wed, 17 May 2000 10:44:00 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Will Dickson) wrote:
> Tom St Denis <[EMAIL PROTECTED]> wrote:
>
> >Well I have to figure out a power supply for the device. I think I
may
> >have a power supply (i.e batteries) for the mcu, but steal power from
> >the rs-232 port for the rng.
>
> YMMV on this one. I tried to do the same thing for my device: set one
> of the RS232 control lines high (+12V-ish), the other low (-12V-ish)
> and hey presto, split supply. Unfortunately, my 3rd-party comm driver
> (a Java one - my code has to be cross-platform) took over the control
> lines and used them for their proper purpose, ignoring my attempts to
> hijack them! In the end I had to build a mains-based supply for the
> device. That said, given the extent to which the lines were sagging
> even when driving the LED's in my serial tester, I'm not sure that
> they would have made adequate supplies even if I had got them to work.
>
> > Since my friend showed me how to tie +10/-
> >10 to get a +20v power (which is simple thing for you guys, but all
new
> >for me).
>
> It's news to me as well. How does that work?
I may have misundertood but it resembled...
+10v ------> device -------> -10v ----> gnd
I dunno, I am not an electronics person, so forgive the huge
ignorance...."Thats when it reallys sets in 'ouch', shoulda gone to
devry"? hehehehehe
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Interesting differentials in BREAKME
Date: Wed, 17 May 2000 10:37:14 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Mark Wooding) wrote:
> Watch out particularly for zero-output differentials. Adam: where did
> you get that S-box: it's awful.
He made it with sboxgen, but I doubt you can really make secure 8x4
sboxes anyways. I think he told me the max differential was 32/256
which is 1/8, which is what you found in the round function right?
Personally in my ciphers I use n by n sboxes and try toget as low as
possible (i.e 8/256 for example). However this cipher was designed to
be cryptanalyzed.
Tom
BTW Sboxgen: http://www.tomstdenis.com/sboxgen.c
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Creating a good key-shedule
Date: Wed, 17 May 2000 10:39:58 GMT
In article <[EMAIL PROTECTED]>,
David Blackman <[EMAIL PROTECTED]> wrote:
> Tom St Denis wrote:
> >
> > In article <8fsgvf$76l$[EMAIL PROTECTED]>,
> > Simon Johnson <[EMAIL PROTECTED]> wrote:
> > > Fair enough, 32-bit enough or would u use a large bits size?
> >
> > I would say at the very least 48 bits... but I would stick with 64
bits
> > as a min, since it's kinda standard.
> >
> > Tom
> >
> > Sent via Deja.com http://www.deja.com/
> > Before you buy.
>
> Today 64 bits is not enough for several practical purposes that you
can
> run into even if you're a serious home user, or a small business. It
is
> safe for small rarely sent messages, if the method is good and the
> keyspace is big enough, but that is not the only use for encryption.
>
> I suggest 96 bits as a safe minimum. There's really no reason not to
go
> 128 bits or even larger. A 128 bit block can probably be encrypted
> securely slightly faster than 2 64 bit blocks on current hardware, so
> you may even win on performance.
Well yea, I think 128-bits is a good starting point, but not alot of
amateurs want to start there... so start with 64 bits.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Fixed the stream cipher "Slime"?
Date: Wed, 17 May 2000 10:41:54 GMT
In article <8ftd96$ujk$[EMAIL PROTECTED]>,
"Scott Fluhrer" <[EMAIL PROTECTED]> wrote:
>
> Tom St Denis <[EMAIL PROTECTED]> wrote in message
> news:8fssfq$jkp$[EMAIL PROTECTED]...
> > In article <8fsra4$ibl$[EMAIL PROTECTED]>,
> > Tom St Denis <[EMAIL PROTECTED]> wrote:
> > > I found if I changed the constant '1' to something with 16
significant
> > > bytes (the simplest constant I could find see the paper) I get way
> > > better results.
> > >
> > > The revised paper is at
> > > http://www.tomstdenis.com/slime.txt
> > >
> > > Tom
> >
> > And of course my test vectors don't match for DJGPP and Turbo C...
sure
> > why not... it's all byte arithmetic... arrrrrggggg!!!!!!..
> >
> > Any help....?
>
> Well, one problem I spotted was in slime_expand. You had:
>
> for (y = x - 1; y >= 0; y++)
> t = sbox[t ^ key[y]];
>
> You meant:
>
> for (y = x - 1; y >= 0; y--)
> t = sbox[t ^ key[y]];
>
> I don't know if that's your problem. BTW: main returns int.
>
> Also, it is "rather quick"??? For a block cipher, it appears slow.
For a
> stream cipher, it's extremely slow. Eyeballing it, the current
> implementation appears to take a minimum 48 cycles per byte: each loop
> iteration does the two xors and the sbox lookup, with each calculation
> depending on the results of the previous one, so they cannot be
overlapped.
Nah, 'slime' sucks the big one.
It's a good idea (small, etc) but there is too much correlation behind
the key (i.e keys that differ in only one bit will not output a random
string when xor'd together).
IOW, it's sucks, it's broken, shame on me, sorry guys, it's done.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: (May 16, 2000) Cipher Contest Update
Date: Wed, 17 May 2000 10:47:19 GMT
In article <[EMAIL PROTECTED]>,
Raphael Phan Chung Wei <[EMAIL PROTECTED]> wrote:
> Adam,
>
> I have written a program to list out the linear distribution table of
your
> sbox... and have found that the max entry is 24
> and -24, with probability of 152/256.. roughly around 0.6 and the
corresponding
> input and output masks are 127 and 11,
> 127 and 12
>
> NS(127,11) = 152
> NS(127,12) = 104
>
> Raphael
He used sboxgen to make the sbox, so he should be able to find those
biases of +24/-24 himself. Part of my sboxgen [1] outputs the sbox
table, as well as the wt output (linearness) and differential xor-pairs
distribution table.
Tom
[1] sboxgen: http://www.tomstdenis.com/sboxgen.c
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: web hosting for sci.crypt
Date: Wed, 17 May 2000 10:54:49 GMT
Need a place to stash your stuff? Check out
http://www.tomstdenis.com/sci.crypt/
It's all free, and I don't mind doing it. There is already one package
there...
Tom
[EMAIL PROTECTED]
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: An attack on reduced Pikachu
Date: Wed, 17 May 2000 10:53:38 GMT
In article <8ft3p4$rvm$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Hello sci.crypt
>
> See the Pikachu cipher at Cipher Contest
>
> http://www.wizard.net/~echo/crypto-contest.html
>
> I have developed a truncated differential attack on nine or ten rounds
> of Pikachu. A truncated differential is one in which only part of the
> cipher text XOR is known in the intermediate rounds.
>
> The linear layer takes four bytes of input and produces
>
> a = 2a+b+c+d
> b = 2a+2b+2c+d
> c = a+b+2c+d
> d = 2a+b+2c+2d
>
> The transform has some interesting differentials. If we take two
texts
> (a,b,c,d),(a',b,c',d) and XOR them we sometimes get (k,0,k,0). The
> interesting part is that sometimes the output of the linear layer will
> be
> (x,0,x,0) when the input is (k,0,k,0). The rules appear to be that
>
> (a+c) == (a'+c') and
> ((2a+c)^(2a'+c')) == ((a+2c)^(a'+2c'))
>
> This happens in about 1 in 32 cases.
Gotcha so far.
> Now the non-linear layer pass the bytes through four sboxes. When the
> input is differentially (x,0,x,0) the output is sometimes (j,0,j,0).
> the chance of both linear and non-linear happening together is about 1
> in 256 or 2^-8.
Don't gotcha. Are we talking about real values for 'j' or is 'j' the
difference? Since if 'j' are a real value then sbox1[j] != sbox2[j]
for most of the time (I haven't really counted but I doubt it's all
that often)
> So here is an attack that can recover some of the key. This shows
> differential input. Two texts are used to create the input. The
right
> side will be equal the left has a certain XOR pattern.
>
> 1 (x,0,x,0) (0,0,0,0) probability 1 two texts (abcdefgh)^
(cbadefgh)
> 2 (0,0,0,0) (y,0,y,0) p = 2^-8
> 3 (y,0,y,0) (z,0,z,0) p = 2^-8
> 4 (z,0,z,0) (m,0,m,0) p = 2^-8
> 5 (m,0,m,0) (z,0,z,0) p = 2^-8
> 6 (z,0,z,0) (k,0,k,0) p = 2^-8
> 7 (k,0,k,0) (t,0,t,0) p = 2^-8
> 8 (t,0,t,0) (e,0,e,0) p = 2^-8
> 9 (e,0,e,0) (q,0,q,0) p = 1 the pattern will fail here
>
> (q,0,q,0) (a,b,c,d) cipher text
>
> The probability is about 2^-56. Several 'good pairs' can be gathered.
> Part of the key be deduced from the b and d in the last round. Since
> the XOR of the input is known to be (q,0,q,0) and by assumption the
> previous round had the form of (y,0,y,0), the key may be guessed to
> within a few values. Three good pair should do it. Some wrong pairs
> might creep in as well, they wil suggest the wrong value. The most
> suggested value is the correct one.
Semi gotcha here. How many rounds are you attacking 7 or 6? (7*-8 = -
56?)
> If the whitening key is guessed, then the last round key can be peeled
> off. The cipher is then one round shorter and the same attack can be
> used.
There is 64-bits of whitening per round though... or are you talking
about the final key xor?
> I ran the attack on six rounds with some success. The code is pretty
> sloppy but I will clean it up if there is interest.
Yeah I want to see this going... heheh down with Pikachu!!!
I can host it on my sci.crypt site (email to [EMAIL PROTECTED])
> The attack took more input than I expected so my 2^-8 probability may
> be
> off somewhat. Anymore than 12 or 13 rounds is certainly immune to this
> attack.
Wow that 12 rounds was a lucky guess, er... right decision. I kinda
had the feeling with only 8 or so rounds it would go down in flames...
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: AES final comment deadline is May 15
Date: Wed, 17 May 2000 13:20:31 +0200
Runu Knips wrote:
> Mok-Kong Shen wrote:
> > According to NIST's intention (as far as I understand) the
> > users of the AES winner shouldn't have to pay patent royalities.
> > What do you mean by worldwide pressure? Why do you think
> > that a patent holder should give up his legitimate rights? For
> > ethical or humanitary reasons perhaps??
>
> Nono, I wanted to say that I believe those patents are not
> really true inventions. Therefore if enough people have an
> interest then there will be enough money to pay the fight
> against them.
What you said is at least a partly different issue in my humble
view. Suppose you used AES shortly after it has become the
standard and two months thereafter you received a notice form
Hitachi asking you to pay license fees. What do you think
about that? Sure, you can fight and there might be a very good
chance that you win. But do you like the whole proceeding?
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: AES final comment deadline is May 15
Date: Wed, 17 May 2000 13:20:45 +0200
Bryan Olson wrote:
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> > Isn't it that both secret key and public key encryption are needed
> > in practice?
>
> Not to mention authentication, certification and revocation,
> e-cash and micro-payments, fair elections, group signatures,
> time stamping, time release and many others. Cryptography
> can provide capabilities far beyond the "secret writing"
> that gives it its name.
Very true. Our group should have more discussions on these
more modern and certainly fruitful topics too. The problem
seems to be lack of initiators of threads on these. Those who
are knowledgeable are seemingly too lazy to do that or are
perhaps outside of our group.Let's hope that the future will be
better, somehow. (The atmosphere of a group is determined
by the ensemble of participants. There is very little that an
individual alone can achieve in that, unfortunately.)
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Crypto & UNICODE???
Date: Wed, 17 May 2000 13:21:04 +0200
Kenneth Cascio wrote:
> If I have a plaintext Message "ABCDEFG" (Represented in memory by 7-Bytes
> (HEX): 41, 42, 43, 44, 45, 46, 47) that I want to keep a secret (i.e.
> encrypt) and my application is using standard ASCII character strings (1
> byte per character), than an eavesdropper, unless he has other methods, can
> not infer anything about my original message from the ciphertext.
>
> On the other hand, if my application is using UNICODE instead of ASCII, the
> same message "ABCDEFG", now occupies 14-Bytes of memory (UNICODE is a
> multi-byte character) and is represented in memory (on an Intel based
> machine) as: 41, 0, 42, 0, 43, 0, 44, 0, 45, 0, 46, 0, 47, 0. Any algorithm
> acting on this block of memory (now 14 bytes) will be encrypting the 0s
> which are now part of the message.
>
> The eavesdropper could now infer (if he knows anything about my system)
> parts of the original plaintext message. He/she could assume that the
> original message looked something like this: ?, 0, ?, 0, ?, 0, ?, 0, ?, 0,
> ?, 0. The "?" represents an unknown BYTE and the 0s are the known BYTES
> (zeros). Now, he/she knows half of my original message! With this
> information, I would think that a "Known Plaintext Attack" could be used in
> an attempt to decrypt the ciphertext.
Sorry for my ignorance. I don't yet understand your agruments. If, as
you said, the opponent knows of you system that every other byte is
a meaningless 0, then he reduces the information obtained to that of
the first case you described. How can he be in a better position to
crack than in the first case? Presumably I have missed quite a lot.
Could you please illustrate with a tiny concrete example of your
known plaintext attack? Thanks in advance.
M. K. Shen
------------------------------
From: David Blackman <[EMAIL PROTECTED]>
Subject: Re: Creating a good key-shedule
Date: Wed, 17 May 2000 21:22:24 +1000
Tom St Denis wrote:
>
> In article <[EMAIL PROTECTED]>,
> David Blackman <[EMAIL PROTECTED]> wrote:
> > There's really no reason not to go
> > 128 bits or even larger. A 128 bit block can probably be encrypted
> > securely slightly faster than 2 64 bit blocks on current hardware, so
> > you may even win on performance.
>
> Well yea, I think 128-bits is a good starting point, but not alot of
> amateurs want to start there... so start with 64 bits.
>
> Tom
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
Why don't people want to start at 128 bits? It doesn't look hard to do.
------------------------------
From: Volker Hetzer <[EMAIL PROTECTED]>
Subject: Introduction to zero knowledge proofs?
Date: Wed, 17 May 2000 11:33:17 +0000
Hi!
Is there any good introduction on zero knowledge
proofs out there?
What I read in applied cryptography basically is:
"It works but you're too stupid to understand the maths
behind it."
I'd like to decide that for myself.
Greetings!
Volker
--
"Isn't it just my luck. Some stranger says to me, "I LOVE YOU"
and next thing I know, I've got this virus..."
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Interesting differentials in BREAKME
Date: 17 May 2000 11:33:52 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] (Mark Wooding) wrote:
> > Watch out particularly for zero-output differentials. Adam: where did
> > you get that S-box: it's awful.
Mea typo. That should have been a `?' at the end. (I have an excuse:
this was a rapid retype after my news client lost the original.)
> I think he told me the max differential was 32/256 which is 1/8, which
> is what you found in the round function right?
Indeed. In fact there's only one input difference with a 1/8
zero-output probability.
The big problem was that it had an output of zero, giving me a free
second round each time. And I'd just been looking at Rijmen and
Knudsen's cryptanalysis of LOKI97, which uses a very similar idea (and
ends with the immortal words, `Conclusion: LOKI97 is broken.'
> However this cipher was designed to be cryptanalyzed.
Well designed, then ;-)
-- [mdw]
------------------------------
** 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
******************************
