Simple Encryption Algorithm
Llewellyn Griffiths
Can anyone provide a simple and fast algorithm for the encryption of data
in an embedded product? Since we are using an 8051 in the product, complex
algorithms would take too long to execute.
___
LLEWELLYN GRIFFITHS
Llew Griffiths & Associates Pty Limited
ll...@bigpond.com
ll...@acslink.aone.net.au
"HELP PRIVATE ENTERPRISE SURVIVE - EXPORT AN ECONOMIST".
Zoran Tomicic
In article <01bcc73c$18889260$LocalHost@llga>, big...@llga.com says...
If you need asymetric (private key) encryption I would suggest that
you try BlowFish algorithm. You can find the code in the Dr.Dobbs Journal,
Sept1995.
Regards
Zoran Tomicic
Microtrol Pty Ltd
Don Yuniskis
In article <01bcc73c$18889260$LocalHost@llga>,
Llewellyn Griffiths <big...@llga.com> wrote:
>Can anyone provide a simple and fast algorithm for the encryption of data
>in an embedded product? Since we are using an 8051 in the product, complex
>algorithms would take too long to execute.
You didn't say how cryptographically strong you wanted the algorithm to be!
You also didn't state how the data will be accessed, etc. (i.e. do you want
to be able to randomly access any single byte and be able to decipher it
in constant -- and small -- time?)
Of course you could do something as simple as a caesar cipher (don't laugh!
There are bits of software out there that use caesar(+1) -- talk about
uninspired!)
Assuming you want something that a 10 year old can't easily crack :>
and that you are instead referring to a data *stream*, the simplest
technique is a pseudo-random number generator that you run the data
through. It relies on keeping the geometry of the RNG as a closely
guarded secret but allows the decoding to happen in a few clock cycles.
--don
Fredrik Bredberg
"Llewellyn Griffiths" <big...@llga.com> writes:
> Can anyone provide a simple and fast algorithm for the encryption of data
> in an embedded product? Since we are using an 8051 in the product, complex
> algorithms would take too long to execute.
>
> ___
> LLEWELLYN GRIFFITHS
> Llew Griffiths & Associates Pty Limited
> ll...@bigpond.com
> ll...@acslink.aone.net.au
>
> "HELP PRIVATE ENTERPRISE SURVIVE - EXPORT AN ECONOMIST".
>
>
#include <stdio.h>
#include <string.h>
/*
** From:
**
** Applied Cryptography: Protocols, Algorithms, and Source Code in C
** Bruce Schneier
** John Wiley & Sons, 1994, 618 pp. $44.95
** ISBN 0-471-59756-2
** http://www.ercb.com/ddj/1994/ddj.9405.html
*/
#define SIZE_ROTOR 256
#define SIZE_KEY_UNRAV 60
#define SIZE_USER_KEY 15
#define BLOCK_BYTES 8
static const unsigned char newdes_rotor[SIZE_ROTOR] =
{
32,137,239,188,102,125,221, 72,212, 68, 81, 37, 86,237,147,149,
70,229, 17,124,115,207, 33, 20,122,143, 25,215, 51,183,138,142,
146,211,110,173, 1,228,189, 14,103, 78,162, 36,253,167,116,255,
158, 45,185, 50, 98,168,250,235, 54,141,195,247,240, 63,148,2,
224,169,214,180, 62, 22,117,108, 19,172,161,159,160, 47, 43,171,
194,175,178, 56,196,112, 23,220, 89, 21,164,130,157, 8, 85,251,
216, 44, 94,179,226, 38, 90,119, 40,202, 34,206, 35, 69,231,246,
29,109, 74, 71,176, 6, 60,145, 65, 13, 77,151, 12,127, 95,199,
57,101, 5,232,150,210,129, 24,181, 10,121,187, 48,193,139,252,
219, 64, 88,233, 96,128, 80, 53,191,144,218, 11,106,132,155,104,
91,136, 31, 42,243, 66,126,135, 30, 26, 87,186,182,154,242,123,
82,166,208, 39,152,190,113,205,114,105,225, 84, 73,163, 99,111,
204, 61,200,217,170, 15,198, 28,192,254,134,234,222, 7,236,248,
201, 41,177,156, 92,131, 67,249,245,184,203, 9,241, 0, 27,46,
133,174, 75, 18, 93,209,100,120, 76,213, 16, 83, 4,107,140,52,
58, 55, 3,244, 97,197,238,227,118, 49, 79,230,223,165,153,59
};
char newdes_key_unravelled[SIZE_KEY_UNRAV];
void newdes_block(char *block)
{
register char *keyptr = newdes_key_unravelled;
register char *byteptr = block;
register int count;
#define B0 (*byteptr)
#define B1 (*(byteptr + 1))
#define B2 (*(byteptr + 2))
#define B3 (*(byteptr + 3))
#define B4 (*(byteptr + 4))
#define B5 (*(byteptr + 5))
#define B6 (*(byteptr + 6))
#define B7 (*(byteptr + 7))
for (count = 8 ; count-- ;) {
B4 = B4 ^ newdes_rotor[B0 ^ *(keyptr++)];
B5 = B5 ^ newdes_rotor[B1 ^ *(keyptr++)];
B6 = B6 ^ newdes_rotor[B2 ^ *(keyptr++)];
B7 = B7 ^ newdes_rotor[B3 ^ *(keyptr++)];
B1 = B1 ^ newdes_rotor[B4 ^ *(keyptr++)];
B2 = B2 ^ newdes_rotor[B4 ^ B5];
B3 = B3 ^ newdes_rotor[B6 ^ *(keyptr++)];
B0 = B0 ^ newdes_rotor[B7 ^ *(keyptr++)];
}
B4 = B4 ^ newdes_rotor[B0 ^ *(keyptr++)];
B5 = B5 ^ newdes_rotor[B1 ^ *(keyptr++)];
B6 = B6 ^ newdes_rotor[B2 ^ *(keyptr++)];
B7 = B7 ^ newdes_rotor[B3 ^ *(keyptr++)];
}
void
newdes_set_key_encipher(char *inkey)
{
char *kuserptr, *kunravptr, key[SIZE_USER_KEY];
int outloop = SIZE_KEY_UNRAV / SIZE_USER_KEY;
int inloop, i, inlen;
inlen = strlen(inkey);
if (inlen >= SIZE_USER_KEY) {
strncpy(key, inkey, SIZE_USER_KEY);
} else {
for (i = 0 ; i < SIZE_USER_KEY ; i++)
key[i] = inkey[i % inlen];
}
kunravptr = newdes_key_unravelled;
while (outloop--) {
kuserptr = key;
inloop = SIZE_USER_KEY;
while (inloop--)
*(kunravptr++) = *(kuserptr++);
}
} /* newdes_set_key_encipher */
void
newdes_set_key_decipher(char *inkey)
{
char *kunravptr, key[SIZE_USER_KEY];
int userkeyidx, i, inlen;
inlen = strlen(inkey);
if (inlen >= SIZE_USER_KEY) {
strncpy(key, inkey, SIZE_USER_KEY);
} else {
for (i = 0 ; i < SIZE_USER_KEY ; i++)
key[i] = inkey[i % inlen];
}
kunravptr = newdes_key_unravelled;
userkeyidx = 11;
for (;;)
{
*(kunravptr++) = key[userkeyidx];
userkeyidx++;
if (userkeyidx == SIZE_USER_KEY) userkeyidx = 0;
*(kunravptr++) = key[userkeyidx];
userkeyidx++;
if (userkeyidx == SIZE_USER_KEY) userkeyidx = 0;
*(kunravptr++) = key[userkeyidx];
userkeyidx++;
if (userkeyidx == SIZE_USER_KEY) userkeyidx = 0;
*(kunravptr++) = key[userkeyidx];
userkeyidx = (userkeyidx + 9) % 15;
if (userkeyidx == 12) break;
*(kunravptr++) = key[userkeyidx++];
*(kunravptr++) = key[userkeyidx++];
*(kunravptr++) = key[userkeyidx];
userkeyidx = (userkeyidx + 9) % 15;
}
} /* newdes_set_key_decipher */
int main()
{
char data[16] = "12345678abcdefgh";
/* Set up encipher key */
newdes_set_key_encipher("Hello world!\n");
printf("in data..: %d, %d, %d, %d, %d, %d, %d, %d\n",
data[0], data[1], data[2], data[3],
data[4], data[5], data[6], data[7]);
printf(" %d, %d, %d, %d, %d, %d, %d, %d\n",
data[8], data[9], data[10], data[11],
data[12], data[13], data[14], data[15]);
/* Encrypt 128-bits */
newdes_block(&data[0]);
newdes_block(&data[8]);
printf("encrypted: %d, %d, %d, %d, %d, %d, %d, %d\n",
data[0], data[1], data[2], data[3],
data[4], data[5], data[6], data[7]);
printf(" %d, %d, %d, %d, %d, %d, %d, %d\n",
data[8], data[9], data[10], data[11],
data[12], data[13], data[14], data[15]);
/* Set up decipher key */
newdes_set_key_decipher("Hello world!\n");
/* Decrypt 128-bits */
newdes_block(&data[0]);
newdes_block(&data[8]);
printf("decrypted: %d, %d, %d, %d, %d, %d, %d, %d\n",
data[0], data[1], data[2], data[3],
data[4], data[5], data[6], data[7]);
printf(" %d, %d, %d, %d, %d, %d, %d, %d\n",
data[8], data[9], data[10], data[11],
data[12], data[13], data[14], data[15]);
return 0;
} /* main */
--
Fredrik Bredberg (fr...@enea.se) | Do bear in mind that the opinions
Pager...: + 46 (0)746 457371 | expressed in this mail might be my
Enea Tel: + 46 (0)8 6385104 | own and that they do not necessarily
Enea Fax: + 46 (0)8 6385050 | represent the opinions of my employer.
C.T.Nadovich
d...@rtd.com (Don Yuniskis) writes:
>Assuming you want something that a 10 year old can't easily crack :>
>and that you are instead referring to a data *stream*, the simplest
>technique is a pseudo-random number generator that you run the data
>through. It relies on keeping the geometry of the RNG as a closely
>guarded secret but allows the decoding to happen in a few clock cycles.
So long as you realize that an XOR with a RNG that has a fixed seed is a
chapter 1 homework problem in a Cryptanalysis course. The guys at Ft.
Meade do these sorts of ciphers over coffee breaks.
So I think you're defeating maybe an 18 year old, here.
--
Chris Nadovich +1 215 257 8708 (voice)
http://www.jtan.com/chris +1 215 257 8154 (fax)
73 de KD3BJ SK ..
Leon Heller
In article <01bcc73c$18889260$LocalHost@llga>, Llewellyn Griffiths
<big...@llga.com> writes
>Can anyone provide a simple and fast algorithm for the encryption of data
>in an embedded product? Since we are using an 8051 in the product, complex
>algorithms would take too long to execute.
>
How about a simple bit-wise XOR with a key string. It's not very secure,
but might do for your purposes. It's very fast, and the code is trivial.
Leon
--
Leon Heller: le...@lfheller.demon.co.uk http://www.lfheller.demon.co.uk
Amateur Radio Callsign G1HSM Tel: +44 (0) 118 947 1424
See http://www.lfheller.demon.co.uk/rcm.htm for details of a
low-cost reconfigurable computing module using the XC6216 FPGA
Ralph Reinhold
Llewellyn Griffiths wrote:
>
> Can anyone provide a simple and fast algorithm for the encryption of data
> in an embedded product? Since we are using an 8051 in the product, complex
> algorithms would take too long to execute.
>
> LLEWELLYN GRIFFITHS
> Llew Griffiths & Associates Pty Limited
> ll...@bigpond.com
> ll...@acslink.aone.net.au
>
> "HELP PRIVATE ENTERPRISE SURVIVE - EXPORT AN ECONOMIST".
is for someone to break it. This is not always true because you can
make a pretty complicated algorithm and not really cypher it very deep.
As someone states below, what you do is dependant upon how secure you
want to be. The fixed seed RNG is one simple way...but not very secure.
A second simple way would be to use a three serial polynomial.
Try looking in the crypto use group. They'll probably give you more help
than you need.
Ralph
John A. Limpert
"Llewellyn Griffiths" <big...@llga.com> wrote:
>Can anyone provide a simple and fast algorithm for the encryption of data
>in an embedded product? Since we are using an 8051 in the product, complex
>algorithms would take too long to execute.
Take a look at the "Tiny Encryption Algorithm" or TEA.
Don Yuniskis
In article <EGx70...@kd3bj.ampr.org>, C.T.Nadovich <ch...@jtan.com> wrote:
>d...@rtd.com (Don Yuniskis) writes:
>
>>Assuming you want something that a 10 year old can't easily crack :>
>>and that you are instead referring to a data *stream*, the simplest
>>technique is a pseudo-random number generator that you run the data
>>through. It relies on keeping the geometry of the RNG as a closely
>>guarded secret but allows the decoding to happen in a few clock cycles.
>
>So long as you realize that an XOR with a RNG that has a fixed seed is a
>chapter 1 homework problem in a Cryptanalysis course. The guys at Ft.
>Meade do these sorts of ciphers over coffee breaks.
The seed and RNG topology can be varied -- dynamically if desired.
>So I think you're defeating maybe an 18 year old, here.
I didn't *claim* it was sophisticated -- rather, that it could be
implemented in constant time with overhead of only a few instructions
per byte.
You'd also be quite surprised at how naive most folks are regarding
codes. The number of "coded" files which are trivial to break
speaks to the naivite of the implementers and "public" in general.
--don
Fred Van Andel
Ralph Reinhold <ralph.r....@boeing.com> wrote:
>Llewellyn Griffiths wrote:
>>
>> Can anyone provide a simple and fast algorithm for the encryption of data
>> in an embedded product? Since we are using an 8051 in the product, complex
>> algorithms would take too long to execute.
. (Lines removed)
.
>There are no secure cyphers. The simpler the algorithm...the easier it
>is for someone to break it. This is not always true because you can
>make a pretty complicated algorithm and not really cypher it very deep.
That statement is not entirely true. One of the simplest method is
the one time pad. As long as the key is kept secure it is the only
encryption method absolutely guaranteed to be 100% secure. All the
computing power in the world would not be able to crack it.
Actually that last statement is not entirely true. It is possible to
crack it, unfortunately the cracking algorithm will produce EVERY
possible message of the same length. Now you have to find the correct
one.
Torben AEgidius Mogensen
"Llewellyn Griffiths" <big...@llga.com> writes:
>Can anyone provide a simple and fast algorithm for the encryption of data
>in an embedded product? Since we are using an 8051 in the product, complex
>algorithms would take too long to execute.
I assume you want a secret key encryption method - I doubt public key
encryption can be done cheaply if you want any kind of security.
So what is security for a secret key encryption method? My criteria is
that even when knowing a number of examples of texts in both normal
and excrypted form, it should be computationally expensive to decrypt
a new text.
It has been suggested that you use the key and a PRNG to generate a
sequence of bits that are XOR'ed to the message. This suffers,
however, from the problem that having one example of a text in both
normal and encrypted form will allow you to decode any encrypted text
that is shorter than the example: You just XOR the encrypted message
with both the normal and encrypted version of your example. Hence,
these methods are not of much use.
A better method, which is still relatively cheap to compute, is to use
the key to permute the bits in the message. You will need roughly
2^(n/2) examples, where n is the length of the message, to accurately
find the permutation used, assuming an even distribution of 0's and
1's. Since the number of permutations of a message of length n is n!,
a range of keys that can choose any permutation will make keys too
large for practical use (the keys would be longer than the message).
Hence, you will want a method of computing a selection of permutations
using a (relatively) small key and the length of the message.
One method for that is using a PRNG to generate the permutation: Use
the key as the seed for the PRNG. If n is the length of the sequence
(in bits), do the following:
for i := 1 to n-1 do begin
x := a random number between 0 and n-i (inclusive);
exchange bits i and x+i
end
There are two things that may make this method slow:
1) The time required to find the next random number.
2) The time required to reduce this to the range i..n.
The first problem can be solved by using a shift-register PRNG, which
is fast. The second can be solved by weakening the method slightly:
Instead of reducing to the range 0..(n-1), reduce to the range
0..lower(n-i), where lower(p) is the largest power of two that doesn't
exceed p. This gives
k := lower(n);
for i:=1 to n-1 do begin
x := a random number between 0 and k (inclusive);
exchange bits i and x+i;
if k+i >= n then k := k div 2
end
The last bits in the sequence have a fairly high (though less than
even) chance of staying where they were, so to make this method a bit
better, add a short fixed string to the end of the message before
encryption. 8 bits should do nicely.
Note that encryption is not its own inverse. To invert the encryption
you must run the program backwards, including getting the random
numbers in the reverse order. A shift-register PRNG can be run
backwards (see below), so you must first run it forwards to find the
last seed in the sequence and then run it backwards to get the reverse
sequence. Alternatively, you can store the sequence as it is generated
and simply walk backwards over it. This requires quite a lot of space,
though. If decryption is done more often than encryption, you can use
the backwards method for encryption and the forwards method for
decryption.
If you still find this to expensive, you can permute bytes instead of
bits, but that retains some information regarding the distribution of
characters in the string. If the string has been compressed before
encryption, this shouldn't be too much of a problem, though.
Running shift register PRNG's backwards:
A shift register PRNG is of the form:
if lsb(seed) = 1 then seed := (seed div 2) xor k
else seed := seed div 2
where lsb(x) is the least significant bit of x and k is a constant.
For good choices of k, consult Knuths The Art of Computer Programming,
vol. 3, but it should at the very least have its msb (most significant
bit) set. Then the backwards method is
if msb(seed) = 1 then seed := 2*(seed xor k)
else seed := 2*seed
This is not hard to verify, and uses the property that msb(k)=1.
Torben Mogensen (tor...@diku.dk)
Ralph Reinhold
Fred Van Andel wrote:
>
> Ralph Reinhold <ralph.r....@boeing.com> wrote:
> >Llewellyn Griffiths wrote:
> >>
> >> in an embedded product? Since we are using an 8051 in the product, complex
> >> algorithms would take too long to execute.
> . (Lines removed)
> .
> >There are no secure cyphers. The simpler the algorithm...the easier it
> >is for someone to break it. This is not always true because you can
> >make a pretty complicated algorithm and not really cypher it very deep.
>
> That statement is not entirely true. One of the simplest method is
> the one time pad. As long as the key is kept secure it is the only
> encryption method absolutely guaranteed to be 100% secure. All the
> computing power in the world would not be able to crack it.
>
> Actually that last statement is not entirely true. It is possible to
> crack it, unfortunately the cracking algorithm will produce EVERY
> possible message of the same length. Now you have to find the correct
> one.
encryption. I also stated that this was a generality. ALL GENERALITIES
ARE WRONG. There are some pretty simple algorithms which are pretty hard
to crack.
A OTP is pretty darn secure, but it is not an algorithm. Writing the
code in Navaho would be pretty secure. One of the Department of Defense
arms of NSA was able to break at least one batch of US OTPs from
over-the-air messages in the mid '60s.
NO COMMUNICATIONS IS PERFECTLY SECURE. This was one of the first
lessons on the first day at Army Security Agency School at Ft. Devens
MA. I think it came right after when the breaks were and where the
bathrooms were.
A pair of strings with mutually prime lengths in XOR with the text would
be a computational equivalent of a OTP. A string of characters 107 long
XORed with a string of characters 109 long with overlays at the ends (at
position 108, the first string element 1 would be XORed with the 108th
element of the second string). This in turn would be XORed with the
file. The total file length without repeated code would be 11663
characters. Two strings of 127 and 129 bytes would cover 16383 bytes
without repeating.
Ralph
C.T.Nadovich
Ralph Reinhold <ralph.r....@boeing.com> writes:
>A pair of strings with mutually prime lengths in XOR with the text would
>be a computational equivalent of a OTP. A string of characters 107 long
>XORed with a string of characters 109 long with overlays at the ends (at
>position 108, the first string element 1 would be XORed with the 108th
>element of the second string). This in turn would be XORed with the
>file. The total file length without repeated code would be 11663
>characters. Two strings of 127 and 129 bytes would cover 16383 bytes
>without repeating.
Why is this a OTP, or do you intend to never send more than 16383 bytes
cumulative? That ain't many bytes for a modem, but for a door lock, 16383
lock/unlock commands before repeat may span years.
Keith Lockstone
Leon Heller wrote:
>
> In article <01bcc73c$18889260$LocalHost@llga>, Llewellyn Griffiths
> <big...@llga.com> writes
>in an embedded product? Since we are using an 8051 in the product, complex
>algorithms would take too long to execute.
The TEA block cipher is very simple - try:
http://vader.brad.ac.uk/tea/tea.html
Where it's described along with code in 'C'. It uses 32-bit arithmetic,
but
shouldn't be too difficult to code.
Regards, Keith.
Don Yuniskis
In article <342FDF...@boeing.com>,
Ralph Reinhold <ralph.r....@boeing.com> wrote:
>C.T.Nadovich wrote:
>>
>> Ralph Reinhold <ralph.r....@boeing.com> writes:
>>
>> >A pair of strings with mutually prime lengths in XOR with the text would
>> >be a computational equivalent of a OTP.
>> cumulative?
>
>That ain't many bytes for a modem, but for a door lock, 16383
>lock/unlock commands before repeat may span years.
It depends on whether you can safely assume "1 byte" is a lock
code ;-) THe locks I've had experience with use considerably more
since they are multilevel devices (i.e. perhaps 8 different locks
implemented in a single mechanism). So, 100 bytes might be a better
ballpark number "per combination" -- or, 163.83 combinations
in this case -- about a week! :>
>I don't have the original thread, but I think he/she wanted something
>for a simple application. To me this implies more the door lock than
>the modem application.
Agreed. Or, just something to obfuscate the code...
--don
John Payson
In article <3427F8...@boeing.com>,
Ralph Reinhold <ralph.r....@boeing.com> wrote:
>A OTP is pretty darn secure, but it is not an algorithm. Writing the
>code in Navaho would be pretty secure. One of the Department of Defense
>arms of NSA was able to break at least one batch of US OTPs from
>over-the-air messages in the mid '60s.
The problem was that certain keys were used more than once. For an OTP to
be secure, it is not only necessary that the key never be compromised direct-
ly, but also that it never be used for more than a single transmission.
>A pair of strings with mutually prime lengths in XOR with the text would
>be a computational equivalent of a OTP. A string of characters 107 long
>XORed with a string of characters 109 long with overlays at the ends (at
>position 108, the first string element 1 would be XORed with the 108th
>element of the second string). This in turn would be XORed with the
>file. The total file length without repeated code would be 11663
>characters. Two strings of 127 and 129 bytes would cover 16383 bytes
>without repeating.
The double-vignere sp?) cipher is not secure--not by any stretch of the
imagination. For even an amateur cryptographer, such a cipher is a little
harder to crack than a single-vignere, but not by much--especially if what's
being encrypted is straight English text. If you want to use an OTP and
have it secure, it has to be a REAL one-time-pad. Numbers, generated
randomly and totally independently from each other (not pseudo-random, but
really random, `a la alpha-decay detector) and never used for any purpose
except to encrypt a single message. The moment you use any part of a
one-time-pad twice, BOTH messages encrypted by that part are jeopardized.
--
-------------------------------------------------------------------------------
supe...@mcs.com | "Je crois que je ne vais jamais voir... | J\_/L
John Payson | Un animal aussi beau qu'un chat." | ( o o )
Gordon Couger
I am new to this tread and I went back and pick it up via
Dejanews.
The original question was a simple encryption routine for
and 8051.
While not very secure a fast low overhead method I have
used is to make a char pointer to some place in the program
code and XOR it with the byte to be encrypted and increment
the pointer.
I realize this is not a very secure method but it was good
enough for what I was doing.
Gordon
Gordon Couger W5RED
Sr. Software Specialist, Emeritus
Agricultural Engineering Oklahoma State University
624 Cheyenne. Stillwater, OK 74075-1411
405/624-2855 gco...@ionet.net www.cecils.com/gcouger
John Payson
In article <60ptgp$3...@ion1.ionet.net>,
Gordon Couger <gco...@ionet.net> wrote:
>The original question was a simple encryption routine for
>and 8051.
>
>While not very secure a fast low overhead method I have
>used is to make a char pointer to some place in the program
>code and XOR it with the byte to be encrypted and increment
>the pointer.
>
>I realize this is not a very secure method but it was good
>enough for what I was doing.
It all depends upon the application. If you are merely trying to make
it hard for people to hack the messages in your code, something like you
describe may be suitable (if the program contains *all* of the information
necessary to decrypt the messages, there's not likely to be any good way
to keep them protected). If, on the other hand, you're trying to design
something that will actually be secure, a better system (which relies upon
external inputs to decipher things) is probably indicated.
As for how best to handle easter eggs, that's hard to say; what may be
best if you can manage it would be to have some process that normally
generates seemingly-pseudo-random outputs (e.g. a random dither pattern
on a lightboard, etc.) but whose outputs will be recognizable if the
algorithm is seeded correctly. Tough to make something too secure, though,
without people wondering why your "random blinkie" routine is so complex...
Ralph Reinhold
> >be a computational equivalent of a OTP.
> cumulative?
That ain't many bytes for a modem, but for a door lock, 16383
> lock/unlock commands before repeat may span years.
I don't have the original thread, but I think he/she wanted something
for a simple application. To me this implies more the door lock than
the modem application.
Ralph
Bo Dömstedt
"Llewellyn Griffiths" <big...@llga.com> wrote:
>Can anyone provide a simple and fast algorithm for the encryption of data
>in an embedded product? Since we are using an 8051 in the product, complex
>algorithms would take too long to execute.
Douglas, Rohan T.
"S-Coder for Data Encryption"
Dr. Dobbs Journal,
January, 1990
Bo Dömstedt
Cryptographer
Protego Information AB
Malmoe,Sweden
http://www.protego.se/sg100_en.htm
http://www.protego.se
Ole-Hjalmar Kristensen FOU.TD/DELAB
Ralph Reinhold <ralph.r....@boeing.com> writes:
>
> Llewellyn Griffiths wrote:
> >
> > Can anyone provide a simple and fast algorithm for the encryption of data
> > in an embedded product? Since we are using an 8051 in the product, complex
> > algorithms would take too long to execute.
> >
> > ___
> > LLEWELLYN GRIFFITHS
> > Llew Griffiths & Associates Pty Limited
> > ll...@bigpond.com
> > ll...@acslink.aone.net.au
> >
> > "HELP PRIVATE ENTERPRISE SURVIVE - EXPORT AN ECONOMIST".
> There are no secure cyphers. The simpler the algorithm...the easier it
> is for someone to break it. This is not always true because you can
> make a pretty complicated algorithm and not really cypher it very deep.
>
That's a bit strong. One-time pads are theoretically (and practically)
totally impossible to break, unless you get the key. The only problem
is thta the key is as long as the message.....
Torben AEgidius Mogensen
o...@tfdt-o.nta.no (Ole-Hjalmar Kristensen FOU.TD/DELAB) writes:
>Ralph Reinhold <ralph.r....@boeing.com> writes:
>> There are no secure cyphers. The simpler the algorithm...the easier it
>> is for someone to break it. This is not always true because you can
>> make a pretty complicated algorithm and not really cypher it very deep.
>That's a bit strong. One-time pads are theoretically (and practically)
>totally impossible to break, unless you get the key. The only problem
>is that the key is as long as the message.....
That is not the only problem. A more serious problem is the
"one-time": If you use it twice, you have given cryptographers a good
hook for decrypting both messages.
You will often want to use the same key to encrypt several messages
and still make decryption hard. And you would want it to be difficult
to decrypt other messages even if you know one (or several) example of
a plain text / encrypted text pair. The suggested method of using the
key as the seed to a PRNG and XOR the message with the stream of
numbers produced from the PRNG fails in the latter respect, as you can
obtain a decrypted version of a text by XORing with both the plain and
encrypted text from the example.
I posted a mesage in this thread earlier, suggesting using a random
permutation for encryption. I now have a simpler idea, which exploits
the reversibility of shift-register PRNGs. A shift-register PRNG uses
a key to transform the seed into a new number, using the following
method:
for (i=0; i<N; i++)
if (seed&1) seed = (seed>>1)^key;
else seed = seed>>1;
Where N is the number of bits in the word (both seed and key). It is
required that the key has the most significant bit set. This can be
reversed by
for (i=0; i<N; i++)
if (seed&(1<<(N-1)) seed = (seed<<1)^((key<<1)|1);
else seed = seed<<1;
I have used the C names for bitwise operators: ^ is XOR, | is OR, <<
is shift left (unsigned) and >> is shift right (ditto).
This can be used directly for encryption. I believe it is hard to
guess the key even if you know an instance of plain/encrypted text.
The security increases with the number of bits in a word. If only 8
bits are used, it is basically just alphabet substitution. 16 bits
just requires testing ~32K keys, which is easy. 32 bits is around 2
billion keys, which requires some effort. 64 bits and above should
withstand brute-force key-guessing reasonably well. As a 1-bit change
to the original message will change on average half the bits of a
block in the encoded message, it seems pretty hard to crack. Of
course, I can give no guarantees.
The method is quite easy to implement even on 8-bit micros, requiring
only 1-bit shifts (with carry for doing multi-byte shifts) and bitwise
logical operations. Using 64 bits, it requires 64 iterations, each
using approximately 20 instructions per iteration per 64-bit block in
the message. This gives a total of around 160 instructions per byte.
The encryption/decryption time using the above method grows linearly
with the size of words/blocks. Instead of using block size M*N, you
can make a first pass using M-bit blocks, then construct new M-bit
blocks by combining bits from N adjacent M-bit block and do a second
pass on these. This makes the total time M+N plus the time required
for recombination, and you effectively get a block size of M*N, in the
sense that a single-bit change will affect an M*N size block. It will
probably be a good idea to use different seeds for the two passes and
for the N different M-bit blocks.
For example, you can make a pass using 8-bit blocks and then recombine
8 adjacent 8-bit blocks and then make another pass. A pass using 8-bit
blocks uses approximately 20 instructions per byte, so the total time
is 40 instructions/byte plus the time required for recombination. The
best recombination is to transpose the 8x8 matrix of bits, but that
costs around 130 instructions, so little (if anything) is saved over
using 64-bit blocks. A simpler recombination is to replace each byte
by the XOR of the other 7 bytes (this transformation is its own
reverse). This can be done by XORing each byte with the XOR of all the
bytes, so this requires a total of around 20 instructions. This makes
the grand total roughly 60 instructions per byte, which is less than
half what is required when using 64-bit blocks directly.
16 different 8-bit (or, actually, 7-bit as the msb must be set) keys
are used, which makes brute-force search impractical. Actually, each
byte in the result is affected by only 8 of the 16 keys, so the search
space is "only" 2^56. Likewise, a bit change in the input will "only"
affect 56 of the 64 bits in a block. Hence, the result is somewhat
less secure than using 64-bit blocks directly. I do, however, believe
it is better than using 24-bit blocs, which has comparable cost.
Torben Mogensen (tor...@diku.dk)
Ralph Reinhold
I hate to keep this pot boiling, but the original post was for a simple
algorithm for use in an 80C51 which was secure. I believe that "simple
algorithm for use in an 80C51" and "secure" is a conflict in terms.
Much of the response has to do with plain text English. I don't think
this has anything to do with it. It is extremely unlikely that the user
will be using an 80C51 for plain text English. He/She will have to
answer this. However, if it is not plain text..a priori knowledge of
the form of the data is necissary to break MOST keys.
Much has to do with OTPs. In fact, in this application, OTPs are
impractical. They would be common table keys, which are pretty insecure.
There are three relatively simple methods to provide somewhat secure
data. Hashing codes which consists of serial polynomials, PRNs and
look-up tables which are of long length when compared to the data
stream.
Everybody seems to know what NSA can do on a bad day. However, I
suspect no one looking at the output of an 80C51 would have those
resources.
One case of the 80C51 application which may contain SOME plain text
English is a modem or serial communications interface. In this case, a
more secure method is needed than I have mentioned. However, it only
has to be secure long enough to be of no use to who are trying read
it...not forever. If someone is trying to say shoot at 4:00 and you are
sending it at 3:58, it only has to be secure for no more than 2
minutes. The information is then available from another source. If
someone is trying to transmit credit card numbers, I would not recommend
any simple algorithm.
We can discuss the esoteric until we are blue in the face. The original
poster should know what fits his needs and he should be looking in the
cryptography use-group.
Ralph
Ole-Hjalmar Kristensen FOU.TD/DELAB
tor...@diku.dk (Torben AEgidius Mogensen) writes:
>
> o...@tfdt-o.nta.no (Ole-Hjalmar Kristensen FOU.TD/DELAB) writes:
>
> >Ralph Reinhold <ralph.r....@boeing.com> writes:
>
> >> There are no secure cyphers. The simpler the algorithm...the easier it
> >> is for someone to break it. This is not always true because you can
> >> make a pretty complicated algorithm and not really cypher it very deep.
>
> >That's a bit strong. One-time pads are theoretically (and practically)
> >totally impossible to break, unless you get the key. The only problem
> >is that the key is as long as the message.....
>
> That is not the only problem. A more serious problem is the
> "one-time": If you use it twice, you have given cryptographers a good
> hook for decrypting both messages.
>
> You will often want to use the same key to encrypt several messages
> and still make decryption hard. And you would want it to be difficult
> to decrypt other messages even if you know one (or several) example of
> a plain text / encrypted text pair. The suggested method of using the
> key as the seed to a PRNG and XOR the message with the stream of
> numbers produced from the PRNG fails in the latter respect, as you can
> obtain a decrypted version of a text by XORing with both the plain and
> encrypted text from the example.
>
Well, as the name implies, it should be used only once, otherwise
it's not a one-time pad any more.
I agree that you would often want to use the same key more than
once. Then you should definitely stay away from a one-time pad.
Also, you have to store the key somewhere, as you will not be able to
remember it....
Ole-Hjalmar Kristensen FOU.TD/DELAB
Ralph Reinhold <ralph.r....@boeing.com> writes:
>
> I hate to keep this pot boiling, but the original post was for a simple
> algorithm for use in an 80C51 which was secure. I believe that "simple
> algorithm for use in an 80C51" and "secure" is a conflict in terms.
>
> Much of the response has to do with plain text English. I don't think
> this has anything to do with it. It is extremely unlikely that the user
> will be using an 80C51 for plain text English. He/She will have to
> answer this. However, if it is not plain text..a priori knowledge of
> the form of the data is necissary to break MOST keys.
>
> Much has to do with OTPs. In fact, in this application, OTPs are
I wasn't really trying to argue for using one time pads in this
application, just objected to the idea that there are no secure
ciphers.
Btw, the TEA, or "Tiny Encryption Algorithm", which has been mentioned
by others, looks pretty good if you want something with a reasonable
amount of security, but still pretty simple and fast to implement:
Routine, written in the C language, for encoding with key k[0] - k[3]. Data in v[0] and v[1].
void code(long* v, long* k) {
unsigned long y=v[0],z=v[1], sum=0, /* set up */
delta=0x9e3779b9, n=32 ; /* a key schedule constant */
while (n-->0) { /* basic cycle start */
sum += delta ;
y += (z<<4)+k[0] ^ z+sum ^ (z>>5)+k[1] ;
z += (y<<4)+k[2] ^ y+sum ^ (y>>5)+k[3] ; /* end cycle */
}
v[0]=y ; v[1]=z ;
}
Derek Somerville
Torben AEgidius Mogensen wrote:
> "Llewellyn Griffiths" <big...@llga.com> writes:
>
> >Can anyone provide a simple and fast algorithm for the encryption of
> data
> >in an embedded product? Since we are using an 8051 in the product,
> complex
> >algorithms would take too long to execute.
>
I am not sure if the data to be made secure is transmitted data or
embedded data. If it is the information such as software, algorithms,
data etc that is in the system, then the better approach may be to
change to a secure embedded processor, ie the Dallas DS5002. This has
all the features of the 8051 series plus some, and will protect both
data and software. It also runs considerably faster than the 8051
family, which is a good benefit in its own right. It can also have
software downloaded in-situ, so no changing eproms etc.
--------------------------------------
The plural of 'paradox' is 'paradise'.
--------------------------------------
Derek Somerville der...@pec.co.nz
PEC (NZ) Ltd http://www.pec.co.nz/