Cryptography-Digest Digest #39, Volume #12 Thu, 15 Jun 00 20:13:01 EDT
Contents:
Re: Random sboxes... real info (David A. Wagner)
Re: Random sboxes... real info (Uri Blumenthal)
New cypher (=?ISO-8859-1?Q?Jacques_Th=E9riault?=)
Re: Random sboxes... real info (Rex Stewart)
Re: Observer 4/6/2000: "Your privacy ends here" (Paul Shirley)
Re: salt length? (Rex Stewart)
Re: MDS theory? ("Paulo S. L. M. Barreto")
Re: Comments/analysis requested: stream cipher derived from hash function (SHA-1)
(Tim Tyler)
Re: MDS theory? (tomstd)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Random sboxes... real info
Date: 15 Jun 2000 13:11:01 -0700
In article <I4a25.3249$[EMAIL PROTECTED]>,
Paul Pires <[EMAIL PROTECTED]> wrote:
> I heard (i.e didn't pay attention to the source, probably the Discovery
> Channel) that this was one of the failings of Enigma. The machine was
> designed so that the output character could never be the input character &
> therefore was flawed since potential settings could easily be excluded with
> a small crib. Is this the kind of thing you mean?
The Enigma failing was much more severe, but it's an analogous situation, yes.
------------------------------
From: Uri Blumenthal <[EMAIL PROTECTED]>
Subject: Re: Random sboxes... real info
Date: Thu, 15 Jun 2000 18:29:07 -0400
Reply-To: [EMAIL PROTECTED]
"David A. Wagner" wrote:
> Nope, I stand by my statement.
>
> You might want to think about this more carefully.
> Here's a useful thought experiment. Consider the following
> two universes:
> Universe A: We encrypt using a permutation chosen
> uniformly at random from the set of all
> permutations.
> Universe B: We encrypt using a permutation chosen
> uniformly at random from everything but
> the identity permutation.
> I claim that (A) is strictly stronger than (B).
I disagree.
> The way to think about this is to look for an attack that
> lets you read encrypted traffic. If you can find an attack
> which works strictly better against (A) then (B), you will
> have proven your point. I claim you can't. Have a try! :-)
The purpose of encrypting usually is to deny the adversary
the knowledge of the contents of the message you're sending.
So if I know your is likely to consist of one word "yes" or
"no" - and I intercept a message from you which says "FB",
I don't *care* whether I can prove which plaintext it is
[well, actually I don't care all THAT much :-].
What counts is that I have a reasonable conjecture and can
plan my actions accordingly.
Similarly with OTP. Mathematicaly speaking, there's no
difference between all-zeroes pad and a "decent" pad.
However upon seeing a message "encrypted" by identity
transform, even though I can't be *sure* what it's
contents really is, I'll have a pretty resonable
guess.
Think VENONA.
--
Regards,
Uri
-=-=-==-=-=-
<Disclaimer>
------------------------------
Subject: New cypher
From: [EMAIL PROTECTED] (=?ISO-8859-1?Q?Jacques_Th=E9riault?=)
Date: Thu, 15 Jun 2000 22:31:27 GMT
MCTER 2
========================================================================
==========
1111
IDX 5555555566666666667777777777888888888899999999990000
2345678901234567890123456789012345678901234567890123
----------------------------------------------------
IDX 111111111122222222223333333333444444444455
0123456789012345678901234567890123456789012345678901
ALFA ABCDEFGHIJKLMNOPQRSTUVWXYZ@!"#$%&'()*+,-./0123456789
Key1 FIRSTKEYFIRSTKEYFIRSTKEYFIRSTKEYFIRSTKEYFIRSTKEYFIRS
Key2 SECONDKEYSECONDKEYSECONDKEYSECONDKEYSECONDKEYSECONDK
Kmix X)C(O!/R4U/J0NUCL1@6R/G'6I7'EQ(T!3OE/DJ5NY9VM.6W/K$G
Mix0 -13H!I&XT*I21EVOG!YN.M2+@3D6X#1EA.J*IP9VZ9FRI'WONVM2
Mix1 N$L($77(5D8GXBN@XT34T08NQ7%2F(9#0PS@V5-#@SP(#20DE4R4
Mix2 54ASRLFX@2JO!V0V("UKU)AVD7@DO&@GV0K*TW9%FZ4E*UO&7L-B
PTXT PLAINTEXTONEPTEXTTWOPTEXTTHREEPTEXTFOURPTEXTFIVEPTEX
CTXT X)LII!G".JUYN/HSYO)SC2CF,NMMXS.CP"5PC+DX85&FSUZ-QYIS
========================================================================
==========
The message is encrypted by chunk of 52 characters. So the key can be
52 character
long. If it is shorter it is reused until all the 52 positions are
filled.
========================================================================
==========
All arrays are 52 elements of 1 character, array elements starts at 0
ALFA - is the array with the letters "A-Z" and "Space - 9" in
ascending ascii
characters.
IDX - is the index of each characters of ALFA
Set up array key1 with the first key, repeating the key if necessary
Set up array key2 with the second key, repeating the key if necessary
Ex: key1(0) = 5 5 is the index of 'F' of key1 in ALFA
Ex: key2(0) = 18 18 is the index of 'S' of key2 in ALFA
Once that is set up you add respective array elements of key1() and
key2() to
produce the array kmix(). All the additions are Modulo 52
Set tmp = 0
tmp = ( tmp + key1(0) + key2(0) ) MOD 52
kmix(0) = tmp
and you repeat that for the 52 elements of key1() and key2()
Repeat with chunk of 52 characters of plaintext, pad with blanks if
less than 52
Example of a typical round. There is three of them
FOR i = 0 to 51 ' mix all the 52 elements of the key
c1 = lookup index character kmix(i) in ALFA
c2 = lookup index character kmix(c1) in ALFA
iv = (iv + c2) MOD 52
mix0(i) = ALFA(iv)
NEXT i
UNTIL there is no more chunk of plaintext
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* * *
This is a system designed to be used manually. Using a computer or a
calculator
facilitate the coding enormously, but the fact remains that you can
operate
this with brain power only...Or maybe make a program on a HP41 or some
similar
calculators.
This is my second attempt to design a cypher algorithm with the
possibility to
use it manually. The first one Mcter was posted earlier this year on
this newsgroup.
The design was similar to this one, but more simple in design.
Mcter 2 uses 2 keys and 3 rounds for each chunk of 52 characters of
plaintext.
I've used 2 keys and try to mix them in a way that the keys are not
leaked or cannot
be easily guessed.
At 52 character there is a little bit more than 5.5 bits of entropy in
the key.
So the combined keys are 52 x 5.5, or 286 bits. or 2^286 or 1.24E+86.
The mixing of the keys and the 3 rounds uses a feedback mechanism where
the last
character calculated is re-used in the next calculation.
The first round is discarted to prevent anything before it leaking into
the cypher text
calculation.
In the cyphertext calculation, each character is calculated
individually, nothing is
carried to the preceding or following characters. The plaintext doesn't
leak anything
in the subsequent rounds. The cyphertext depends only on mix1 and mix2
I would like to get comments on this algorithm and how secure it is.
Recommendations are welcome to improve or change the algorithm as you
wish.
Jacques Th�riault
[EMAIL PROTECTED]
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* * *
Following is a Basic program to help you test if you want
DIM 1 look$(255)
DIM k1(255), k2(255), m0(255),m1(255),m2(255), pt1(255), PT2(255)
look$ = "ABCDEFGHIJKLMNOPQRSTUVWXYZ !"+CHR$(34) +
"#$%&'()*+,-./0123456789"
k1$ = "FIRSTKEY": k2$ = "SECONDKEY"
pt1$ = "PLAINTEXTONEPTEXTTWOPTEXTTHREEPTEXTFOURPTEXTFIVEPTEX"
JMX = LEN(look$)-1 ' num of elements - 1
WHILE LEN(k1$) < (jmx+1) ' fill key 1
k1$ = k1$ + k1$
WEND
k1$ = LEFT$(k1$,jmx+1) 'size it
WHILE LEN(k2$) < (jmx+1) 'fill key 2
k2$ = k2$ + k2$
WEND
k1$ = LEFT$(k1$,jmx+1) 'size it
WHILE LEN(pt1$) < (jmx+1)
pt1$ = pt1$ + pt1$
WEND
pt1$ = LEFT$(pt1$,jmx+1)
CLS
PRINT "ALFA ";
FOR j = 0 TO JMX
PRINT MID$(look$,j+1,1);
fp1 = INSTR(1,look$, MID$(k1$,j+1,1)) -1
fp2 = INSTR(1,look$, MID$(k2$,j+1,1)) -1
fp3 = INSTR(1,look$, MID$(pt1$,j+1,1)) -1
fp4 = INSTR(1,look$, MID$(pt2$,j+1,1)) -1
k1(j) = fp1 :k2(j) = fp2 :pt1(j) = fp3 :pt2(j) = fp4
look$(j) = MID$(look$,j+1,1)
NEXT j
PRINT :PRINT "Key1 ";
FOR j = 0 TO JMX
fpx = INSTR(1,look$, MID$(k1$,j+1,1)) -1: PRINT look$(fpx);
NEXT j
PRINT: PRINT "Key2 ";
FOR j = 0 TO JMX
fpx = INSTR(1,look$, MID$(k2$,j+1,1)) -1: PRINT look$(fpx);
NEXT j
PRINT: PRINT "Kmix ";
kmx% = 0
FOR j = 0 TO JMX
m0(j) =( k1(j) + k2(j) + kmx%) MOD (JMX+1): m2(j) = m0(j): kmx% =
m0(j): PRINT look$(m0(j));
NEXT j
iv = kmx% ' Initial value
IMPORTANT
rem CONTINUE here if you have more Plaintext to code
MORE:
PRINT: PRINT "Mix0 ";
FOR j = 0 TO JMX
c1 = m0( j): c2 = m0( c1 ): iv = (c2 + iv) MOD (JMX+1): m0(j) = iv:
PRINT look$(m0(j));
NEXT j
PRINT: PRINT "Mix1 ";
FOR j = 0 TO JMX
c1 = m0( j): c2 = m0( c1 ): iv = (c2 + iv) MOD (JMX+1): m1(j) = iv:
m0(j) = iv
PRINT look$(m1(j));
NEXT j
PRINT: PRINT "Mix2 ";
FOR j = 0 TO JMX
c1 = m0( j): c2 = m0( c1 ): iv = (c2 + iv) MOD (JMX+1): m0(j) = iv:
m2(j) = iv
PRINT look$(m2(j));
NEXT j
PRINT: PRINT "Ptex ";
FOR j = 0 TO JMX
PRINT look$(pt1(j));spx$;
NEXT j
PRINT: PRINT "Ctex ";
TEXT _monaco,9,0
FOR j = 0 TO JMX
c1 = m1(j): c2 = m2(j): c3 = pt1(j): ct = (c1 + c2 + c3 ) MOD
(JMX+1): PRINT look$(ct);
NEXT j
PRINT
rem NOTE: If there is more plaintext then goto the label 'MORE:' above
rem continue with the 'iv' value last calculated
============== END OF BASIC LISTING =============
------------------------------
From: Rex Stewart <[EMAIL PROTECTED]>
Subject: Re: Random sboxes... real info
Date: Thu, 15 Jun 2000 22:27:20 GMT
You are probably correct in that observation. That is not
the *direction* he is persuing. He seems intent (at this
time) to be persuing balanced and unbalanced Fistel constructs
which, due to the inherant delay in access of main memory
tend to be faster with smaller s-boxes. (And yes, this was
discussed in an earlier conversation.) With an addicted
curiosity like he seems to have, if large s-boxes are someday
found to have an interesting property, I am sure he will get
around to them also :-)
--
Rex Stewart
PGP Print 9526288F3D0C292D 783D3AB640C2416A
In article <8iba88$a86$[EMAIL PROTECTED]>,
zapzing <[EMAIL PROTECTED]> wrote:
>
> I must confess I didn't follow it all exactly,
> and I could be wrong, but I didn't see
> anywhere where he tried using large key
> dependent sboxes.
>
> --
> 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.
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Paul Shirley <[EMAIL PROTECTED]>
Reply-To: Paul Shirley <[EMAIL PROTECTED]>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,alt.politics.uk,alt.security.scramdisk,uk.telecom
Subject: Re: Observer 4/6/2000: "Your privacy ends here"
Date: Thu, 15 Jun 2000 23:47:38 +0100
In article <[EMAIL PROTECTED]>, Mok-Kong Shen <mok-
[EMAIL PROTECTED]> writes
>You didn't read a previous post of mine which had a bit detail saying
>that the key, a seed of a PRNG, is sent as a prefix to the ciphertext.
>So handing over the key is trivial and I remain outside of the prison :)
You still *don't understand*.
If there's a message you are subject to RIP. The key is irrelevant, as
long as you encrypted *anything* RIP applies. Sending the key with it
potentially stops them taking any action against you, but it also stops
them wasting time in decryption attempts or in courts. So what's the
point?
--
Paul Shirley: reply address may change at short notice.
cc'ed news posts *unwelcome*
------------------------------
From: Rex Stewart <[EMAIL PROTECTED]>
Subject: Re: salt length?
Date: Thu, 15 Jun 2000 22:47:34 GMT
Could you (or anyone) give me a referance to something on
the problems with the RC4's keyschedule problems?
I have searched through a lot of papers and I have seen
a lot of bits and pieces, but I would like to
get something more complete.
--
Rex Stewart
PGP Print 9526288F3D0C292D 783D3AB640C2416A
In article <8ib2vl$hbr$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (David A. Wagner) wrote:
> Actually, I, too, would recommend pre-hashing the password and salt
> and feeding only the result to RC4's key schedule.
>
> RC4's key schedule has some funny properties when fed with non-random
> keys, especially with multiple related keys, and I'm not sure how much
> to trust it for that use.
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Date: Thu, 15 Jun 2000 20:41:03 -0300
From: "Paulo S. L. M. Barreto" <[EMAIL PROTECTED]>
Subject: Re: MDS theory?
tomstd wrote:
>
> I decided to play around with the x^-1 mod p sboxes (the really
> spiffy ones that don't follow sac) with the affine transform
> Problem is, I don't know how MDS's work. I know what they are
> suppose todo, but not how.
>
> Any help?
Have a look at Vincent Rijmen's doctoral dissertation. It includes a
really nice introfuction to the topic and how MDS codes can be applied
to cipher design.
The basic idea is the following, in very simplified terms.
A (linear) code is a set of "words", i.e. fixed-length strings of
elements taken from a finite field; for instance, all Square ciphers and
Twofish use codes over GF(2^8). In an MDS code there's a lower bound for
the Hamming distance between any two code words (i.e. the number of
elements where the code words differ). The great trick is that, given
only part of a code word, the remaining can be calculated from that part
by means of matrix multiplication (this is to say that the code is a
linear subspace of the set of all words of same length over the same
field).
Now suppose you are given two partial code words that differ in only a
few elements (this circumstance models differential attacks if you take
the partial words as plaintext to be subjected to a cipher round). The
MDS property ensures there will be many differences among the remaining
elements of these words, i.e. the differences in the plaintext pair are
quickly spread over the ciphertext (resulting from a single round). The
overall effect is that the differential characteristics will have low
probability. That this is indeed so, and that similar results exist for
linear attacks is proved in Joan Daemen's and in Vincent Rijmen's
theses.
Let's see two concrete examples. Rijndael and Twofish use [8,4,5] codes
over GF(2^8); this means subspaces of dimension 4 of the set of all
8-byte words, where each word differs from any other word in at least 5
bytes. The first half of a code word models a 4-byte plaintext; the
second half models the corresponding ciphertext. Therefore, if two
plaintexts differ in a single byte, the ciphertexts after a single round
will differ in all four bytes (the total number of differing bytes
being thus 5).
So much for similarities between Rijndael and Twofish; from this point
on each cipher uses distinct means to diffuse the plaintext differences
over all 16 block bytes, but I think this is enough to have a taste of
MDS codes applied to block ciphers.
Cheers,
Paulo S. L. M. Barreto.
------------------------------
Crossposted-To: sci.crypt.random-numbers
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Comments/analysis requested: stream cipher derived from hash function
(SHA-1)
Reply-To: [EMAIL PROTECTED]
Date: Thu, 15 Jun 2000 22:58:11 GMT
In sci.crypt.random-numbers David Blackman <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> In sci.crypt.random-numbers tomstd <[EMAIL PROTECTED]> wrote:
:> : An even better idea is to maintain a counter.
:>
:> Counter-based schemes allow backtracking. Avoiding this seemed to be the
:> point of the design.
: How do you backtrack with Tom's method? It looked about as hard as
: breaking SHA-1 to me. (Provided the random seed is kept secret.)
By decreasing the counter.
The assumption is that the attacker has somehow learned of the state of
counter at some point - e.g. through theft. Preventing him from
using this to recover any earlier sections of transmission under the same
key is the idea behind the proposed system.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ UART what UEAT.
------------------------------
Subject: Re: MDS theory?
From: tomstd <[EMAIL PROTECTED]>
Date: Thu, 15 Jun 2000 17:02:33 -0700
In article <[EMAIL PROTECTED]>, "Paulo S. L. M.
Barreto" <[EMAIL PROTECTED]> wrote:
>tomstd wrote:
>>
>> I decided to play around with the x^-1 mod p sboxes (the
really
>> spiffy ones that don't follow sac) with the affine transform
>> Problem is, I don't know how MDS's work. I know what they are
>> suppose todo, but not how.
>>
>> Any help?
>
>Have a look at Vincent Rijmen's doctoral dissertation. It
includes a
>really nice introfuction to the topic and how MDS codes can be
applied
>to cipher design.
I can't get to his site because of his anti-ms ego trip. So if
anyone has direct links to his papers I would appreciate it.
>The basic idea is the following, in very simplified terms.
>
>A (linear) code is a set of "words", i.e. fixed-length strings
of
>elements taken from a finite field; for instance, all Square
ciphers and
>Twofish use codes over GF(2^8). In an MDS code there's a lower
bound for
>the Hamming distance between any two code words (i.e. the
number of
>elements where the code words differ). The great trick is
that, given
>only part of a code word, the remaining can be calculated from
that part
>by means of matrix multiplication (this is to say that the code
is a
>linear subspace of the set of all words of same length over the
same
>field).
>
>Now suppose you are given two partial code words that differ in
only a
>few elements (this circumstance models differential attacks if
you take
>the partial words as plaintext to be subjected to a cipher
round). The
>MDS property ensures there will be many differences among the
remaining
>elements of these words, i.e. the differences in the plaintext
pair are
>quickly spread over the ciphertext (resulting from a single
round). The
>overall effect is that the differential characteristics will
have low
>probability. That this is indeed so, and that similar results
exist for
>linear attacks is proved in Joan Daemen's and in Vincent
Rijmen's
>theses.
>
>Let's see two concrete examples. Rijndael and Twofish use
[8,4,5] codes
>over GF(2^8); this means subspaces of dimension 4 of the set of
all
>8-byte words, where each word differs from any other word in at
least 5
>bytes. The first half of a code word models a 4-byte
plaintext; the
>second half models the corresponding ciphertext. Therefore, if
two
>plaintexts differ in a single byte, the ciphertexts after a
single round
>will differ in all four bytes (the total number of differing
bytes
>being thus 5).
>
>So much for similarities between Rijndael and Twofish; from
this point
>on each cipher uses distinct means to diffuse the plaintext
differences
>over all 16 block bytes, but I think this is enough to have a
taste of
>MDS codes applied to block ciphers.
What I got from Vaudenays analysis of multipermutations is that
a (r + n)-multipermutation is a permutation from Zr to Zn (Z is
a alphabet) such that any two pairs in the form (x, f(x)) cannot
collide in r positions.
Where the pair (x, f(x)) is the input and output. So if you had
a 4x4 code each would be eight bytes. If you had a (4 + 4)-
Multipermutation (is that possible?) that means any two pairs
will not share (collide) in four bytes (in/output).
I am a bit shaky on this all. The MDS in Twofish would be a (4
+ 4) multipermutation since it must cause 5 byte changes...?
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!
------------------------------
** 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
******************************
