diamond.txt

DIAMOND2加密算法的原代码

Substitution

In each substitution round, each byte of the input block is 
replaced with the contents of the substitution array for that 
round, byte position, and byte value. For decryption, the same 
operation is performed with the inverse substitution array. In a 
hardware implementation, this is can be done quickly by simply 
addressing static RAM. Note that the substitution arrays used in 
the Diamond Encryption Algorithm are different from the S-Boxes 
used in ciphers like DES, in that (1) they are much larger, (2) 
there are more of them, and (3) they are not used in conjunction 
with a simpler operation with a key that could be solved for 
with differential cryptanalysis.

Permutation

Between each substitution round, a fixed permutation is 
performed. The purpose of this permutation step is to increase 
the effective block size of the cipher by making each output 
byte a function of 8 input bytes by simply selecting one bit 
from each of 8 input bytes. Every bit of the input block is used 
exactly once in the output block. In a hardware, this can be 
done with literal wire crossings. In software, efficiency is 
gained by ensuring that every bit ends up in the same position 
relative to a byte boundary as where it started.

The specific permutation used for encryption takes the least 
significant bit of each byte from the input byte in the same 
position. The next most significant bit is taken from the input 
byte indexed as one byte higher (mod 16). The next most 
significant bit is taken from the input byte indexed as two 
higher (mod 16), and so on. For decryption, the inverse of this 
operation is the same, except the byte positions used are one 
byte lower (mod 16) instead of higher.

After 2 rounds, every output byte is a function of 8 input bytes 
and all key bytes (if the key is less than 4080 bytes, which is 
likely). After 3 rounds, every output byte is a function of 15 
input bytes and the key. After 4 rounds, every output byte is a 
function of every input byte and the key. The minimum of 6 
additional rounds are intended to make cryptanalysis more 
difficult.

CRYPTANALYSIS OF DIAMOND

In the design of Diamond, several types of cryptanalytic attacks 
were considered. The reasons why I currently consider each of 
them to be computationally infeasible are listed below. If 
anyone finds an attack on Diamond that is better than a brute 
force attack on the key, please let me know. The following 
consists of rough order of magnitude estimations and hand 
waving, but they are of value anyway. To construct more exact 
proofs, actual construction of all of the cryptanalytic attacks 
that your opponent might try is required. It is conjectured that 
actual construction of the attacks mentioned would be much more 
complex than the following estimates indicate.

Brute Force

Exhaustive key search can be made intractable (beyond the reach 
of any likely enemy) by choosing a key length of around 120 
bits. A loose lower bound of the cost of exhaustive key search 
can be placed with the following generous assumptions. Assuming 
a massively parallel machine can perform a trillion decryptions 
per second (with different keys) on each of a billion 
processors, then an exhaustive key search would take an average 
of about 42 million years. The user may wish to use smaller key 
sizes in some applications to save in key management costs, 
while still maintaining adequate protection for the value of the 
specific data. Larger keys than 128 bits probably do not 
contribute significantly to the over-all security of a system of 
data protection, because of some other attacks on data security 
that are possible. If you do want to use a much larger key, 
increasing the number of rounds to greater than 10 is 
recommended.

Another form of brute force attack that is available with block 
ciphers is the precomputed dictionary attack. The idea here is 
to create a database of one very probable plain text block 
encrypted under all possible keys. Sort the resulting cipher 
text/key pairs by cipher text value and store it in a table. 
Then to attack a piece of cipher text, look up the possible key 
in the table and try it on the rest of the message. This may 
take several iterations, but would be likely to succeed if you 
could store so much data. The problems here are, of course (1) 
time to generate the table, and (2) sorting and storing the 
table.

Note that the defined lower bound on Diamond key size of 40 bits 
is not very secure against a brute force attack.

Analytical Attack with Chosen Plain Text

An analytical attack involves solving for the contents of at 
least one of the substitution arrays. If one array could be 
isolated by selecting carefully chosen inputs and outputs, then 
its contents could be solved for. Once this was done, this 
knowledge could be used to solve for additional substitution 
arrays. The problem with this attack is that because every 
output byte is a function of every input byte and at least 112 
substitution arrays, this decomposition is difficult. I 
conjecture that a loose lower bound on the complexity of this 
kind of attack is that it would take more operations than 256  
2x, where x is the number of arrays in the dependency chain for 
each byte. For a 10 round Diamond implementation, this would be 
an approximate total of 256  16(2112 + 296 + 280 + 264 + 248 + 
233 + 218 + 210 +22)  2  1037 operations. This is about as hard 
as solving for a 124 bit key with a precomputed plain text 
attack, but even less practical.

Differential Cryptanalysis

Attacking Diamond with a form of differential cryptanalysis as 
described in [6] does not work directly. A similar approach 
using differences in known plain text values would have some 
value in reduced Diamond variants with 3 or fewer rounds, but 
would be no better than the analytical attack discussed above 
for 10 or more rounds.

Solving for the Key from an Array

If you could solve for one substitution array, and knew (or 
guessed) the length of the key, a method might be constructed to 
directly solve for the key from the contents of one substitution 
array. This reduces the strength lower bound estimate for an 
analytical attack on a 10 round Diamond system to about 256  
2112  1036, or about as strong as a 120 bit key.

Bypassing the Algorithm

In any security system, care must be taken to avoid the 
possibility that the hardware and/or software doing the 
encryption and decryption is not tampered with or replaced. For 
very high security applications, a hardware device that is 
implemented on a tamper resistant chip in a tamper resistant 
enclosure is preferable to a pure software implementation. Care 
must also be taken to ensure that the sensitive data is 
physically secure when in plain text form. Key management, 
although it is beyond the scope of this paper, is also a 
critical concern.

DIAMOND LITE

Where software speed and table space are critical, a variant of 
Diamond that has a block size of 8 bytes (64 bits) and a minimum 
of four rounds (8 recommended) is a reasonable compromise. This 
variant has the advantage that every bit of the output is a 
function of every bit of the input and every bit of the key 
after only two rounds. At least four rounds are needed, however, 
to ensure that the algorithm is strong enough to justify keys of 
about 64 bits. This only requires 8192 bytes of table space and 
offers faster speed in software than the full Diamond with a 16 
bit block size.

It is conjectured that Diamond Lite with 8 rounds and a key 
length of 128 bits is at least equivalent in security to the 
IDEATM cipher, and more secure than the aging DES algorithm.

LEGAL ISSUES

The Diamond and Diamond Lite Encryption Algorithms may be used 
for any legal purpose without payment of royalties to the 
inventor or his employer, however the names "Diamond Encryption 
Algorithm" and "Diamond Lite Encryption Algorithm" are Trade 
Marks owned by the inventor, and may not be used in connection 
with any algorithm that does not comply with the specifications 
given herein and in the sample programs written by the inventor. 
The Diamond Encryption Algorithm is the same as the MPJ and MPJ2 
Encryption Algorithms, with the exception of some of the key 
expansion algorithm. Some governments may restrict the use, 
publication, or export of strong encryption technology.

CONCLUSION

Diamond and Diamond Lite are two of several alternatives to the 
aging and now relatively insecure DES algorithm. Source code for 
a software implementation of Diamond in C is available from the 
author for a minimal shipping and handling charge or for free 
electronic transfer where allowed by law. Contact the author at 
one of the addresses below for details. Comments, questions, and 
reports of possible weaknesses should be sent to the author at:

        Mike Johnson
        PO BOX 1151
        LONGMONT CO 80502-1151
        USA

        BBS: 303-938-9654
        Internet mail: [e-mail]
        Internet ftp:csn.org//mpj/README.MPJ
        CompuServe: 71331,2332

REFERENCES

[1]     Michael J. Wiener, "Efficient DES Key Search," 
Bell-Northern Research, PO Box 3511 Station C, Ottawa, Ontario, 
K1Y 4H7, Canada, 20 August 1993.

[2]     Theodor Brggemann and Hoger Brk, "Der 
Verschlsselungsalgorithmus IDEATM," Ascom Tech AG, Fachbereich 
Kryptologie, Ziegelmattstrasse 1, CH - 4503 Solothurn, 
Switzerland.

[3]     Xuejia Lai and James L. Massey, "Markov Ciphers and 
Differential Cryptanalysis," in Advances in Cryptology  
EUROCRYPT '91, Springer-Verlag, pp 17-38.

[4]     Xuejia Lai "Detailed Description and a Software 
Implementation of the IPES Cipher," Institut fr Signal- und 
Informationsverarbeitung, ETH Zrich.

[5]     Michael Paul Johnson, "Beyond DES: Data Compression and 
the MPJ Encryption Algorithm," Master's Thesis at the University 
of Colorado at Colorado Springs, 1989. Available by anonymous 
ftp to csn.org in /mpj or on the author's BBS at 303-938-9654.

[6]     Eli Biham and Adi Shamir, Differential Cryptanalysis of 
the Data Encryption Standard. New York: Springer-Verlag, 1993.

[7]     C Programmers Guide to NetBIOS, Howard W. Sams & Co., 
Inc.

[8]     Rick Sternbach and Michael Okuda, Star Trek the Next 
Generation Technical Manual, New York: Pocket Books, 1991.

[9]     Xuejia Lai and James L. Massey, "A Proposal for a New 
Block Encryption Standard," in Advances in Cryptology --
EUROCRYPT '90, Springer-Verlag, pp 389-404., 1990.

Copyright (C) 1994 Michael Paul Johnson.  All rights reserved.