Cryptography-Digest Digest #602, Volume #12 Sun, 3 Sep 00 11:13:01 EDT
Contents:
Feistel Cipher ("Martin 'SirDystic' Wolters")
Re: New cryption method... ("Stephan Leclercq")
Re: DES weak keys in 3DES (Mark Wooding)
Re: New cryption method... (Benjamin Goldberg)
Re: New cryption method... ("Stephan Leclercq")
Transposition Problem (Future Beacon)
Re: Transposition Problem (SCOTT19U.ZIP_GUY)
PKI & Crypto kits for palmtop computers required. (Ichinin)
Re: Feistel Cipher (Mark Wooding)
Re: New cryption method... (PROdotes)
----------------------------------------------------------------------------
From: "Martin 'SirDystic' Wolters" <[EMAIL PROTECTED]>
Subject: Feistel Cipher
Date: Sun, 3 Sep 2000 13:03:57 +0200
Hi,
I'd like to hear, what you think about this cipher, I hope it's
at least a little bit better than the ones I posted before.
Here's a description (Have a look at it, PROdotes this is a description)
1. The key schedule
1.1. Take a 128-Bit User key K.
1.2. Left-Rotake K by n bits (n=0).
1.3. Perform the following permutation on the result:
PC1:
9, 39,102, 50,107, 46, 98, 27,115, 35, 99, 10, 94, 51, 23, 83
57,118, 75, 15, 45, 2, 58, 87, 70, 19, 6, 65, 31, 73,106, 54
122, 66,111, 22, 86, 26, 34, 17, 74, 82,103, 42,123, 30,121, 13
85, 5, 78, 38, 91, 69, 97, 1, 59, 41, 37, 21, 71, 61, 81, 67
110, 55, 33, 49, 14,117, 53,109, 79, 11,119, 3, 29,113, 43, 95
90, 18,101, 63, 77, 25,125, 7,114, 62, 89,105,127, 93, 47,126
1.4. Again, left-rotate the result by n bits.
1.5. Perform the permuted choice 2 on the result:
PC2:
11,43,80,16,59,28,8,22
74,26,37,64,2,53,95,76
20,86,58,31,44,5,65,19
71,7,52,34,1,41,32,49
92,83,23,47,67,17,55,13
68,40,94,4,35,46,38,73
56,91,29,77,85,70,61,89
10,62,88,50,14,74,82,25
1.6. The Output of this permutation is the 64 bit Subkey n.
1.7. Increase n by 1 and repeat the steps 1.2. to 1.6 16 times, to get 16
subkeys.
2. The encryption
2.1. Take a 128 Bit block to be encrypted.
2.2. Perform the initial permutation IP on it:
IP:
128,121,118,115,112,105,102, 99,125,122,119,116,109,106,103,100
96, 89, 86, 83, 80, 73, 70, 67, 93, 90, 87, 84, 77, 74, 71, 68
35, 38, 41, 48, 51, 54, 57, 64, 36, 39, 42, 45, 52, 55, 58, 61
32, 25, 22, 19, 16, 9, 6, 3, 29, 26, 23, 20, 13, 10, 7, 4
127,124,117,114,111,108,101, 98,126,123,120,113,110,107,104, 97
95, 92, 85, 82, 79, 76, 69, 66, 94, 91, 88, 81, 78, 75, 72, 65
34, 37, 44, 47, 50, 53, 60, 63, 33, 40, 43, 46, 49, 56, 59, 62
31, 28, 21, 18, 15, 12, 5, 2, 30, 27, 24, 17, 14, 11, 8, 1
2.3. Split the result into 2 halves l(the left 64 bits) and r(the right 64
bits).
2.4. Permute r using this table:
BHP:
64, 8,11,14, 2, 5,12,15
17,24,27,30,18,21,28,31
33,40,43,46,34,37,44,47
49,56,59,62,50,53,60,63
4, 7,10,13, 3, 6, 9,16
20,23,26,29,19,22,25,32
36,39,42,45,35,38,41,48
52,55,58,61,51,54,57, 1
2.5. XOR the result with Subkey m.
2.6. Split the result into 16 4-Bit blocks. b[0] to b[15]
2.7. Substitute b[x] with the values in the following table, using x as the
row
and the value of b[x] as the column.
S:
D026FCAB851349E7
8D7C2B0E6FA41359
0AF8561CDE4937B2
14E0BD38AC927F65
C63E958FB7DA0124
7283D4F1905BECA6
2FD903547AECB618
EB1F42C7536D809A
43BAC09D167F258E
A15DE8460B3792CF
689B7ED5C201A4F3
39C16A704825FEDB
F507A9E321B6C84D
9764812A3DFE5B0C
BC453F62E980DA71
5EA217B9F4C86D30
2.8. Permute the concatenation of b[0] to b[15] using this permutation:
P:
27,58,38, 9,25,53,44, 3
30,52,42,15,18,59,36, 5
32,62,47, 7,22,50,41,10
17,64,35, 2,21,61,33,11
26,63,45,14,24,55,40, 1
31,51,39,16,19,54,46, 6
29,56,43, 4,28,57,48,13
20,60,34,12,23,49,37, 8
2.9. Xor the result with l and switch the two halves r and l.
2.10. Increase m by 1 and repeat the steps 2.4. to 2.9 16 times.
To decrypt use the 16 subkeys in reverse order.
I think it can be used as one way hash this way:
Use 0x0123456789ABCDEFFEDCBA9876543210 as the plaintext.
Pad the Message to be hashed with one byte '00000001'
and then append zero bytes until the length mod 128 = 0.
Encrypt the plaintext with the first 128 bits of the
message, and use the resulting ciphertext as the new plaintext.
Repeat this until the whole message was used.
------------------------------
From: "Stephan Leclercq" <[EMAIL PROTECTED]>
Subject: Re: New cryption method...
Date: Sun, 03 Sep 2000 11:29:15 GMT
OK, time to get a little bit constructive here,
PROdotes <[EMAIL PROTECTED]> a écrit dans le message :
[EMAIL PROTECTED]
> Hey... "if knowledge is power then to be unknown is to be unconquered"
He moves in mysterious ways :-)
> Want some more... got some remarks... want to piss me of... just say it.
"Yes", "Yes" and "Only depends on you : no if you want to learn, yes if you
try to convince professional cryptographers that you hold all the answers"
:-)
Let's see if I understand you well. I'm not a professionnal cryptographer,
just a guy with some mathematical and computer science background. So any
further information is welcome.
Step 1 - "Switching randomly"
I presume the algorithm is :
1) Get a PRNG and seed it with the key (where do you get the key ?).
2) Arrange the message as an array of bytes.
3) Generate 2 integers with the PRNG
4) Consider the two integers as the indexes to the bytes to swap, and swap
them
5) Repeat steps 3 and 4 a fairly big number of times.
Obviously, the receiver of the message will need to do the same, but using
the random numbers in the reverse order. Otherwise, unscrambling is
impossible :
Scramble
ABC -> (swap 1-2) -> BAC -> (swap 2-3) -> BCA
Unscramble
BCA -> (swap 1-2) -> CBA -> (swap 2-3) -> CAB
So if you scramble a meaningful number of times (at a very minimum, you
should make a number of swaps the same order of magnitude as the number of
bytes to swap), the receiver would have to pre-build the random numbers in
an array, or restart the PRNG at each number. The algorithm would take
either a big amount of memory (this step roughly requires 2 integers of
storage for each encrypted byte, that's 8 to 1) or be very slow.
Step 2 - "Convert to black and white"
???
Step 3 - "Randomly invert bytes"
What do you mean by "Invert" ?
Steps 4 and 5 - "Mix rows and columns"
I assume you use a technique similar to step 1, but using whole rows or
columns at a time. Why do this, as it is more complicated than swapping
bytes, and less secure (the longer the data structures you move around, the
more information an attacker has to break your cipher) ?
> file. so there are ((n*8)!)^2 * n^2 * 2 combinations for scrambling...
> where n is the fix(sqrt(number of bytes)) + 1.
Probably not. It depends also on the length of the key, the strength of the
PRNG, etc...
--
Stephan Leclercq - sauron <at> minasmorgul <dot> com
www <dot> minasmorgul <dot> com
S'il n'y a pas de solution, c'est qu'il n'y a pas de problème -- proverbe
Shadok
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: DES weak keys in 3DES
Date: 3 Sep 2000 11:19:55 GMT
Gisle Sælensminde <[EMAIL PROTECTED]> wrote:
> DES have a number of weak and semi-weak keys, but in 3DES
> (DES-EDE3) tree independent keys is used. How is the securiy if
> one (or two) of these keys are weak. Shoud the key be avoided if
> any of the DES-keys are weak, or must as least two of them be
> weak before it becomes a problem.
I believe that rejecting a single weak key is not beneficial. To notice
the weak key being used, you'd have to successfully guess the other two
keys, which is harder than attacking the full triple encryption (using,
e.g., meet-in-the-middle or Lucks' probabilistic attack).
I'd reject two weak keys out of three, though, if I were the sort of
person who rejects weak keys.
-- [mdw]
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: New cryption method...
Date: Sun, 03 Sep 2000 11:48:34 GMT
Stephan Leclercq wrote:
[snip]
> Step 1 - "Switching randomly"
>
> I presume the algorithm is :
>
> 1) Get a PRNG and seed it with the key (where do you get the key ?).
> 2) Arrange the message as an array of bytes.
> 3) Generate 2 integers with the PRNG
> 4) Consider the two integers as the indexes to the bytes to swap, and
> swap them
> 5) Repeat steps 3 and 4 a fairly big number of times.
>
> Obviously, the receiver of the message will need to do the same, but
> using the random numbers in the reverse order. Otherwise, unscrambling
> is impossible :
>
> Scramble
> ABC -> (swap 1-2) -> BAC -> (swap 2-3) -> BCA
> Unscramble
> BCA -> (swap 1-2) -> CBA -> (swap 2-3) -> CAB
>
> So if you scramble a meaningful number of times (at a very minimum,
> you should make a number of swaps the same order of magnitude as the
> number of bytes to swap), the receiver would have to pre-build the
> random numbers in an array, or restart the PRNG at each number. The
> algorithm would take either a big amount of memory (this step roughly
> requires 2 integers of storage for each encrypted byte, that's 8 to 1)
> or be very slow.
Actually, if he uses a PRNG that can run forwards and backwards, and
which can easily be started in a later state, then precomputing isn't
necessary. We could use a block cipher in counter mode, advance the
counter some amount, and then decrement it instead of incrementing it.
This will give the reverse order of blocks as running in normal mode.
Of course, I'm not implying that the cipher is secure, just not as
horribly slow as it would be if we needed precompute.
--
... perfection has been reached not when there is nothing left to
add, but when there is nothing left to take away. (from RFC 1925)
------------------------------
From: "Stephan Leclercq" <[EMAIL PROTECTED]>
Subject: Re: New cryption method...
Date: Sun, 03 Sep 2000 12:32:06 GMT
Benjamin Goldberg <[EMAIL PROTECTED]> a écrit dans le message :
[EMAIL PROTECTED]
> Actually, if he uses a PRNG that can run forwards and backwards, and
> which can easily be started in a later state, then precomputing isn't
> necessary. We could use a block cipher in counter mode, advance the
> counter some amount, and then decrement it instead of incrementing it.
> This will give the reverse order of blocks as running in normal mode.
I agree, I had in mind a simple LFSR. Anyway, if we already have a block
cipher, wouldn't it be easier to use it to encrypt the message directly
rather than using it to generate PRNs to encrypt the message in a novel way
? i.e. simply xoring with the output of the block cipher would be stronger
than any random bit or byte shuffling.
On the other hand, using a simple congruential X(n+1) = (X(n) * A + B) mod C
can also be run backwards if A and C are well chosen. An attacker would
certainly like such a PRNG.
--
Stephan Leclercq - sauron <at> minasmorgul <dot> com
www <dot> minasmorgul <dot> com
S'il n'y a pas de solution, c'est qu'il n'y a pas de problème -- proverbe
Shadok
------------------------------
From: Future Beacon <[EMAIL PROTECTED]>
Subject: Transposition Problem
Date: Sun, 3 Sep 2000 09:27:43 -0400
If one wishes to use a binary random number generator
to select a transposition of some number of blocks, the
following problem seems to arise:
The number of possible transpositions is N! where N is
the number of blocks to be transposed. The binary numbers
obtained from the RNG to select a transposition may produce
a bias. For instance, if the number of blocks is 3, the
number of possible transposition is 3! = 6.
If two bits are used to select a number between 1 and 4 and
then one bit is used to select 0 or 2 and these two numbers
are added, the selections will be between 1 and 6, but the
possible selections are not equally likely.
Table
+ | 1 2 3 4
=========
0 | 1 2 3 4
2 | 3 4 5 6
Using this table, transpositions 3 and 4 are twice as likely
as the others.
Also I am suspicious of a bias in the event that three bits
are used to select 1 of 8 and two outcomes are simply ignored.
Does anybody know of an unbiased selection method for
transposition?
Thank you for your help.
Jim Trek
Future Beacon Technology
http://eznet.net/~progress
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Transposition Problem
Date: 3 Sep 2000 13:54:53 GMT
[EMAIL PROTECTED] (Future Beacon) wrote in
<[EMAIL PROTECTED]>:
>
>
>If one wishes to use a binary random number generator
>to select a transposition of some number of blocks, the
>following problem seems to arise:
>
>The number of possible transpositions is N! where N is
>the number of blocks to be transposed. The binary numbers
>obtained from the RNG to select a transposition may produce
>a bias. For instance, if the number of blocks is 3, the
>number of possible transposition is 3! = 6.
>
>If two bits are used to select a number between 1 and 4 and
>then one bit is used to select 0 or 2 and these two numbers
>are added, the selections will be between 1 and 6, but the
>possible selections are not equally likely.
>
>Table
>
>+ | 1 2 3 4
>---------
>0 | 1 2 3 4
>2 | 3 4 5 6
>
>
>Using this table, transpositions 3 and 4 are twice as likely
>as the others.
>
>Also I am suspicious of a bias in the event that three bits
>are used to select 1 of 8 and two outcomes are simply ignored.
>
>Does anybody know of an unbiased selection method for
>transposition?
>
>Thank you for your help.
>
>
>Jim Trek
>Future Beacon Technology
>http://eznet.net/~progress
>[EMAIL PROTECTED]
>
>
>
This really is no problem at all "if you have a generator
of random binary bits"!
suppose you want to select states 1 to 6 equally. Then get
next 3 bits. If the binary vlaue is 1 to 6 use it. If the
value is 0 or 7 then get the net three bits and so on.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website **now all allowed**
http://members.xoom.com/ecil/index.htm
Scott rejected paper for the ACM
http://members.xoom.com/ecil/dspaper.htm
Scott famous Compression Page
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
"The road to tyranny, we must never forget, begins with the destruction
of the truth."
------------------------------
From: Ichinin <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: PKI & Crypto kits for palmtop computers required.
Date: Sun, 03 Sep 2000 05:04:31 +0200
Hi.
Looking for cryptokits (Public & ordinary) for PALMTOP computers (MS and
Palmos)
PK's should contain one or more of the following: RSA, DH, ECC.
Cryptos should contain one or more of the following: preferably the AES
contestants, 3DES, IDEA.
One way hashing functions are also required (MD5/SHA-1)
The kits should be easily implemented (Com components are nice) with
existing programming languages.
Regards,
Glenn
(P.S: Note this is NOT an invitation to spam me!, if someone have a
comprehensive list, please post it.)
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Feistel Cipher
Date: 3 Sep 2000 14:12:15 GMT
Martin 'SirDystic' Wolters <[EMAIL PROTECTED]> wrote:
> I'd like to hear, what you think about this cipher, I hope it's at
> least a little bit better than the ones I posted before.
This is not a good cipher.
Firstly, it has the DES complementation property.
Secondly, there's a differential attack which requires about 2^{-25}
chosen plaintext pairs (about 50 million chosen plaintexts). That's not
a lot.
Here's how the differential attack works. Firstly, look at the
structure of round i:
f'_i(x', y')
= y', x' \xor \pi_1 \circ \sigma \circ \kappa_i \circ \pi_0 (y')
where:
* x', y' are the block halves,
* \pi_0 and \pi_1 are the two bit permutations,
* \sigma is the S-box substitution,
* \kappa_i is an XOR with the ith round subkey, and
* \circ denotes composition of functions
That \pi_0 is a pain. Let's remove it. I'll rewrite:
x = \pi_0 (x), y = \pi_0 (y), \pi = \pi_0 \circ \pi_1
f_i(x, y) = y, x \xor \pi \circ \sigma \circ \kappa_i (y)
Quick check:
f_i(\pi_0(x'), \pi_0(y')) =
\pi_0(y'), \pi_0(x') \xor \pi \circ \sigma \circ \kappa_i (\pi_0(y'))
= \pi_0(y'), \pi_0(x') \xor
\pi_0(\pi_1 \circ \sigma \circ \kappa_i (\pi_0(y')))
= \pi_0(y'), \pi_0(x' \xor \pi_1 \circ \sigma \circ
\kappa_i \circ \pi_0 (y'))
which is \pi_0 applied to the results of f'(x', y'), the correct form
for the next round. This modifies the initial permutation and
introduces a final permutation, but they're fixed and can be ignored for
the purposes of cryptanalysis.
We note that \kappa_i is differentially transparent, and since this is
the only difference between the rounds, we can omit it from this part of
the analysis.
We combine the permutation \pi and substution \sigma into a single
operation which we analyse as a group of 8 8 x 64 S-boxes. We discard
output differences from these S-boxes which give rise to multiple active
S-boxes on the output, and then exhaustively search for characteristics
for the entire 16-round cipher constructed from these single-round
characteristics.
The program which did this for me spat out the following characteristic:
plog = 24995
0: 0000000000000000 0000020000000000
1: 0000020000000000 0000000000000000 (02[2] -> 08[3], p = 32/256)
2: 0000000800000000 0000020000000000 (08[3] -> 02[2], p = 64/256)
3: 0000000000000000 0000000800000000
4: 0000000800000000 0000000000000000 (08[3] -> 02[2], p = 64/256)
5: 0000020000000000 0000000800000000 (02[2] -> 08[3], p = 32/256)
6: 0000000000000000 0000020000000000
7: 0000020000000000 0000000000000000 (02[2] -> 08[3], p = 32/256)
8: 0000000800000000 0000020000000000 (08[3] -> 02[2], p = 64/256)
9: 0000000000000000 0000000800000000
10: 0000000800000000 0000000000000000 (08[3] -> 02[2], p = 64/256)
11: 0000020000000000 0000000800000000 (02[2] -> 08[3], p = 32/256)
12: 0000000000000000 0000020000000000
13: 0000020000000000 0000000000000000 (02[2] -> 08[3], p = 32/256)
14: 0000000800000000 0000020000000000 (08[3] -> 02[2], p = 64/256)
15: 0000000000000000 0000000800000000
16: 0000000800000000 0000000000000000
Each line represents a point between rounds of the cipher. The number
on the left is the XOR difference between the blocks at that point; the
notation on the right is the single-round characteristic which will be
exploited in the next round.
I strongly recommend against using this cipher.
-- [mdw]
------------------------------
From: PROdotes <[EMAIL PROTECTED]>
Subject: Re: New cryption method...
Date: Sun, 3 Sep 2000 16:05:49 -0700
> Step 1 - "Switching randomly"
> I presume the algorithm is :
> 1) Get a PRNG and seed it with the key (where do you get the key ?).
The key is an inputed sequence from the keyboard with some math on it...
I simply multiply the numbers and use MOD 999999... that makes a maximum
of 1,000,000 combinations... but for my purpose it's enough... by using
an 1024 bit key the results would be in 2^1024 combinations... as in any
other algorithm.
> 2) Arrange the message as an array of bytes.
> 3) Generate 2 integers with the PRNG
> 4) Consider the two integers as the indexes to the bytes to swap, and swap
> 5) Repeat steps 3 and 4 a fairly big number of times.
Correct...
> Obviously, the receiver of the message will need to do the same, but using
> the random numbers in the reverse order. Otherwise, unscrambling is
> impossible : ...
Yep...
> ...
> So if you scramble a meaningful number of times (at a very minimum, you
> should make a number of swaps the same order of magnitude as the number of
> bytes to swap), the receiver would have to pre-build the random numbers in
> an array, or restart the PRNG at each number. The algorithm would take
> either a big amount of memory (this step roughly requires 2 integers of
> storage for each encrypted byte, that's 8 to 1) or be very slow.
At this state i store the numbers in arays... so the memory usage
grows... the slower warinat would use a very large amount of time and I
think that wouldn't de rational.
> Step 2 - "Convert to black and white"
> ???
It the same as if you would take the printout of the result, scan it and
the process it as a BW picture.
> Step 3 - "Randomly invert bytes"
> What do you mean by "Invert" ?
B->W, W->B
> Steps 4 and 5 - "Mix rows and columns"
> I assume you use a technique similar to step 1, but using whole rows or
> columns at a time. Why do this, as it is more complicated than swapping
> bytes, and less secure (the longer the data structures you move around, the
> more information an attacker has to break your cipher) ?
Well, I swap the rows and colums of the picture... so I swap the bits,
not the bytes anymore...
> > file. so there are ((n*8)!)^2 * n^2 * 2 combinations for scrambling...
> > where n is the fix(sqrt(number of bytes)) + 1.
> Probably not. It depends also on the length of the key, the strength of the PRNG,
Yes... but these is a hypothesis. That's why it's here.
------------------------------
** 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
******************************
