🚀 go-pugleaf

In article <tom.712397505@cluster>, tom@stallion.oz.au (Thomas Essebier) writes:
|> By far not being an expert on cryptology, I would appreciate some 
|> comments on the crypto scheme below. 
|> 
|> Where does it stand in terms of security when compared to transposition 
|> cyphers, DES etc.
|> 
|> My initial thoughts were that other then using a brute force approach,
|> e.g. trying all 2^31 seeds (or so), there is no easy way to deal 
|> with it - but I am probably wrong :-)
|> 
|> I presume that due to its simplicity this sort of crypto approach must
|> be quite well known, its just that in my rather limited explorations of 
|> the field I have not come accros any.
|> 
|> Algorithm:
|> - Create a sequence of random numbers that starts at 'seed' and is known 
|>   to be deterministic and to have a large period. e.g. linear congruential:
|>   X[i+1] = (a*X[i] + c) mod m, choose coefficients as follows 
|>   a = 16807, m = 2,147,483,647 (2^31 - 1), c = 0
|>   #define RANDOM ((unsigned char) (seed = (16807 * seed) % 2147483647))
|>   supposedly has a period of 2^31.
|> 
|> - use the 'key' to choose the first seed, e.g. add up all the bytes or
|>   some such, so that a key >= 4 byte could cover 0-2^31, roughly at least.
|> 
|> - take the the data stream and for each byte 'xor' the LSB of the 'seed'.
|>   A stronger method might be to use 4 byte chunks (assuming seed is 4 bytes)?
|>   The advantage of using xor is that there is that the algorithm is self
|>   reversing. Perhaps it entails some pitfall(s) however?
|> 
|> If anybody could point me to some literature that explains why the above
|> is (un?)reasonably (in?)secure I would be most grateful. Please note that
|> I make no claim to have carefully studied and researched this topic. 
|> I was hoping to avoid all that :-)

The problem with your algorithm is with the know plaintext text.
That means, your opponent knows some of the original plaintext or
makes a good guess of it.
For example, if the plaintext is a letter to someone, you
would expect something like 'Dear Mr ...' or anything alike
in the first few lines of the plaintext.
If I know only 4 Bytes of the plaintext and its position 
(must be divideable by 4) I can easily tell the state of
your random generator at this time (= plaintext word
xor ciphertext word) and decode the following ciphertext.

You could improve your algorithm by:
- Increasing the # of states of your generator,
  e.g. by using an intermediate array:
    r = RANDOM; 
    num = A[index];
    A[index] = r;
    index = r;
    return(num);
- Backcoupling the plaintext into the state of your random
  generator.

Stephan.

In article <tom.712397505@cluster> tom@stallion.oz.au (Thomas Essebier) writes:
>By far not being an expert on cryptology, I would appreciate some 
>comments on the crypto scheme below. 

Linear congruential generator based schemes are very easy to break;
I've even heard Phil Zimmerman tell of encountering an intro crypto
class where breaking them was a homework assignment in the first week.
Everyone thinks them up at one time or another. One technique that
DOES work is a scheme similar to yours based on using
cryptographically strong RNGs, like ones the breaking of which is
equivalent to factoring large numbers. However, I should point out
that no one uses these techniques in practice for the same reason that
people only exchange keys using RSA and use conventional cyphers for
the real work -- too much computation time.

>Where does it stand in terms of security when compared to transposition 
>cyphers, DES etc.

DES is very hard to break. Transposition cyphers, well, that depends
on which one we are talking about.

>If anybody could point me to some literature that explains why the above
>is (un?)reasonably (in?)secure I would be most grateful. Please note that
>I make no claim to have carefully studied and researched this topic. 
>I was hoping to avoid all that :-)

I would suggest that you read some intro to cryptography texts; it
would likely be quite rewarding; the topic is common enough.

--
Perry Metzger		pmetzger@shearson.com
--
		  Just say "NO!" to death and taxes.
			 Extropian and Proud.

In article <tom.712397505@cluster> tom@stallion.oz.au (Thomas Essebier) writes:
>By far not being an expert on cryptology, I would appreciate some 
>comments on the crypto scheme below. 
> [ use a standard linear congruential random number generator (= RNG),
>   primed with the key, to derive a stream of bits, which is then xor-ed
>   with the data ]
>
>Where does it stand in terms of security when compared to transposition 
>cyphers, DES etc.

I'm sorry, but this is a very weak cipher -- it's very easy to break.
There are (at least) two main weaknesses:

(1)	As you described it, there are only 2^32 possible internal
	states of the RNG.  Computers are fast enough today that
	the brute-force attack of trying all of them is feasable
	for any mildly determined opponent.

(2)	The simple structure of a linear congruential RNG makes this
	scheme breakable using a much cheaper and more "elegant"
	attack.  The linear and self-inverse nature of xor
	(i.e. a xor b xor a = b) makes the RNG output stream
	recoverable from the ciphertext only with a bit of work,
	or trivially from a plaintext/ciphertext pair.  Given the
	RNG output stream, Knuth v.2 section 3.6 excercise 7
	describes how to recover the RNG parameters, including the
	starting value = crypto key.

In general, the fundamental lesson of crypto history is that good
cryptosystems are designed *only* by people who have both theoretical
knowledge of, *and* practical experience with, breaking existing
high-quality cryptosystems.  In other words, unless you have a lot
of crypto experience you're unlikely to come up with a system that
would withstand professional attack.

If you simply want a secure cryptosystem, use DES (appropriately,
i.e. in the right mode, with secure keys, and with proper attention
payed to defense against "practical cryptanalysis").  It's secure
against anyone short of a very big corporation or a medium sized
government.  And if Exxon or the FBI *really* want the contents
of your disk drive, they'll probably get it one way or the other...

- Jonathan Thornburg
  <jonathan@einstein.ph.utexas.edu> or <jonathan@hermes.chpc.utexas.edu>
  University of Texas at Austin / Physics Dept / Center for Relativity
  and (for a few more months) U of British Columbia / {Astronomy,Physics}

In article <1992Jul31.034244.9150@chpc.utexas.edu> jonathan@chpc.utexas.edu (Jonathan Thornburg) writes:
>In article <tom.712397505@cluster> tom@stallion.oz.au (Thomas Essebier) writes:
>>By far not being an expert on cryptology, I would appreciate some 
>>comments on the crypto scheme below. 
>> [ use a standard linear congruential random number generator (= RNG),
>>   primed with the key, to derive a stream of bits, which is then xor-ed
>>   with the data ]
>>
>
>In general, the fundamental lesson of crypto history is that good
>cryptosystems are designed *only* by people who have both theoretical
>knowledge of, *and* practical experience with, breaking existing
>high-quality cryptosystems.  In other words, unless you have a lot
>of crypto experience you're unlikely to come up with a system that
>would withstand professional attack.
>
>
>- Jonathan Thornburg
>  University of Texas at Austin / Physics Dept / Center for Relativity
>  and (for a few more months) U of British Columbia / {Astronomy,Physics}


Not True. In fact the principle used by many cipher systems were invented by
invented by amateurs (as well as a lot of garbage).  It takes a 
professional to cast in into a framework were it will be strong. For example,
public key cryptography was not invented by professional codemakers.
It was originally invented by a student at Stanford. Experts took the 
principle and developed it into a strong system.

In contrast, it usually takes  profesional codebreakers to break a system.
Cryptanalysis doesn't seem to be a subject were amateurs thrive.