From: lwloen@rchland.vnet.ibm.com (Larry Loen)
Subject: Re: Encryption algorythm/code needed...
Date: Tue, 15 Dec 1992 17:49:20 GMT
Distribution: na
Reply-To: lwloen@rchland.vnet.ibm.com
Disclaimer: This posting represents the poster's views, not necessarily those of IBM
Organization: IBM Rochester

In article <1992Dec11.113831.2520@doug.cae.wisc.edu>, mccullou@cae.wisc.edu (Mark McCullough) writes:
|> 
|> In article <1992Dec09.200208.11243@rchland.ibm.com>, lwloen@rchland.vnet.ibm.com (Larry Loen) writes:
|> |> In article <1992Dec7.160128.18678@sbcs.sunysb.edu>, clane@csws2.ic.sunysb.edu (Charles F Lane) writes:
|> |> |> In article <Byt18n.6Cr@andy.bgsu.edu> jzawodn@bgsu.edu (jeremy zawodny) writes:
|> |> |> >I am writing a small program to help secure some computers from
|> |> |> >unauthorized access.  I have alread writen the interface and
|> |> |> >unsername/password checking routines.  Now what I need is a way to encrypt
|> |> |> >the usernames and passwords.  The code need not be extravagent...  I only
|> |> |> >need to encrypt single words (letters and numbers both).
|> |> |> >
|> |> |> >I can use either Pascal, C, or C++ code.
|> |> |> >Thanks for any help!
|> |> |> >Jeremy
|> |> |> >Jeremy Daniel Zawodny                           Computer Science Undergraduate
|> |> |> >                      Bowling Green State University
|> |> |> A very easy way to encrypt data is to use a random number generator.  Suppose
|> |> |> you have a string "CHAIR".  Assign a value to your random number generator's
|> |> |> seed.  Then add random(256) to the ord of the first character (C, in this
|> |> |> case), then random(256) + ord("H"), random(256) + ord("A"), etc.  When adding
|> |> |> the random number you should wrap around if the sum is > 255.  In tp just
|> |> |> disable range checking.  Decrypting is just as easy -- reassign the original
|> |> |> seed value and subtract the "random" number rather than adding.  Code (TP) to
|> |> |> encrypt/decrypt a string follows:
|> |> |> 
|> |> |> procedure EncryptString(var s : string; seed : LongInt);
|> |> |> var i : word;
|> |> |> begin
|> |> |>  RandSeed := seed;
|> |> |>  {$R-}
|> |> |> (* ^^^--Disable range checking.  To be honest, I'm not sure if this is the   *)
|> |> |> (*      proper directive for disabling range checking.  Or if range checking *)
|> |> |> (*      can be disabled locally.  Check your manual because mine's not with  *)
|> |> |> (*      me right now!							     *)
|> |> |> 
|> |> |>  for i := 1 to ord(s[0]) do s[i] := s[i] + random(256);
|> |> |> 
|> |> |>  {$R+}
|> |> |> (* ^^^--Enable range checking, see above comment *)
|> |> |> end;
|> |> |> 
|> |> |> procedure DecryptString(var s : string; seed : LongInt);
|> |> |> var i : word;
|> |> |> begin
|> |> |>  RandSeed := seed;
|> |> |>  {$R-} (* See above comment *)
|> |> |>  for i := 1 to ord(s[0]) do s[i] := s[i] - random(256);
|> |> |>  {$R+} (* See above comment *)
|> |> |> end;
|> |> |> 
|> |> |> That's it!  Apply the method to data other than strings, as well.  Just be sure
|> |> |> to pass the same value to the seed parameter of both procedures.  No one will
|> |> |> be able to decipher the encrypted string without knowing the algorithm AND 
|> |> |> the seed value.  This is a guess because I never tried, but don't writeln
|> |> |> an encrypted string to the screen because it may have control characters in
|> |> |> it.
|> |> |> 
|> |> |> -- 
|> |> |>                           | "So who is this Al Gorithm guy they keep
|> |> |> Charles F. Lane           |  mentioning in my Computer Science classes?"
|> |> |> clane@Libws1.ic.sunysb.edu|
|> |> 
|> |> Unfortunately, this is a well known _poor_ encryption algorithm.
|> |> 
|> |> Encryption and its subject, cryptology, has a lot of suprising twists and
|> |> turns and is generally counter-intuitive.  For one thing, the people 
|> |> one is trying to defeat are dishonest people and will get past any barrier
|> |> by hook or by crook.
|> |> 
|> |> Mr Lane has re-invented a known cipher that has been solved many times.
|> |> It is a worthy concept; it just happens not to work very well.
|> |> One problem:  If someone is at all serious about the penetration attempt,
|> |> one can expect them to get their hands on the source code.  Even if the
|> |> "seed" is customized for each instalation, the above code fragment is
|> |> enough to permit overall failure under a variety of circumstances that I
|> |> will omit in the interests of space.  I can't predict all of them, but
|> |> the odds against success using the scheme above are so high as to make
|> |> further analysis not worth it.  The only people this kind of scheme defeats
|> |> would also be defeated by simply XORing each byte with 0x55.  I should
|> |> also point out that this scheme has been re-invented so many times, it
|> |> might be simply "tried out" by an opponent even with no source code.  This
|> |> sort of thing is often tried, because really good schemes take so long to
|> |> solve, it is easy to try the known, weak ones in parallel.
|> |> 
|> |> I suggest anyone interested in adding encryption to their application
|> |> for any reason first consult the many fine books now available on the 
|> |> subject.  It is easy to add stuff that looks really good that is really
|> |> worthless.
|> |> 
|> |> I've seen this basic problem this twice today; it is almost worth adding a 
|> |> note to the FAQ.  Cryptology is not an easy place to do re-use and it is kind
|> |> of a special case all around.  Here are some good, 
|> |> widely available references:
|> |> 
|> |>     H. F. Gaines, Cryptanalysis, Dover, 1956 [originally 1939, as
|> |>         Elementary Cryptanalysis]
|> |> 
|> |>     Abraham Sinkov, Elementary Cryptanalysis, Math. Assoc. of Amer.,
|> |>         1966
|> |> 
|> |>     D Denning, Cryptography and Data Security, Addison-Wesley, 1983
|> |> 
|> |>     Alan G. Konheim, Cryptography:  A Primer, Wiley-Interscience, 1981
|> |> 
|> |>     Meyer and Matyas, Cryptography:  A New Dimension in Computer Data
|> |>         Security, John Wiley & Sons, 1982.
|> |> 
|> |> There are also some legal issues, different for each country, on using
|> |> encryption technology in products.  Export and Import can be problems, even
|> |> for schemes which aren't any good.
|> |> 
|> |> Any of the references should give enough information to the aspiring designer 
|> |> to have an idea of what they are getting into.  Meyer and Matyas or
|> |> Denning are probably the most relevant to what I've seen here, but all should
|> |> help out a lot.
|> |> 
|> |> -- 
|> |>    Larry W. Loen        |  My Opinions are decidedly my own, so please
|> |>                         |  do not attribute them to my employer
|> 
|> The basic technique, frequently known as a one time cypher pad, is one of
|> the most secure algorithms of all.  The algorithm above doesn't work, but
|> a slight modification does.  You create say a 20 element long array of
|> random numbers, in some range greater than or equal to 256.  In other 
|> words, generate random numbers between 0 and some number larger than
|> 256.  Put each number in the program itself, and destroy your copy of
|> those numbers.  Then you do add the ord of each character to the appropriate
|> random number and put it mod 256.  You need to generate two procedures,
|> one to code, the other to uncode, so you need to put in the numbers twice.
|> The key to keeping this secure is that the random number string must
|> be made unreadable by compilation, ie, can not be read from a file.
|> The larger the range of random numbers, the harder to crack the code.
|> 
|> Note, that the algorithm I described isn't easy to code, but it is 
|> secure, you can't see my random numbers, and I can safely store the
|> encrypted version on disk.  I load the encrypted version, unencrypt, and
|> compare with what they have entered.  This takes a loading the entire 
|> list of passwords, but that isn't too hard.  If you really want to make
|> it secure, make the unencryption, a variation of the encryption algorithm.
|> i.e. don't make a separate unencryption, make a special procedure that
|> calls the encryption to unencrypt.
|> :)M^2

Nope, sorry, it really is not that easy.  I've been here before.  I say
"this is a known poor encryption".  Then, the poster patches it up.  Then,
I say, "but it still doesn't work" and it gets patched again.  Eventually,
one of us gives up, usually me, but the system still isn't any good.  This
basic idea set is very attractive to beginners, but has never yet led to a
working system that one can count on to defeat a serious, intelligent, 
knowledgable opponent.

Crypto just isn't that easy.  The conditions for a one-time pad are
very tough to arrange and the circumstances cited above _do not qualify_.  
Your new scheme is a little improved, but is still vulnerable.  It
has only a superficial resemblance to a one-time pad.  Let's
not debate it here -- you can come up with any number of schemes
but you've gotta go out and learn how to do what you want to do.  A true
one-time pad is probably not feasible in this application.  True one-time
pads are _provably_ indecipherable, but achieving its proper environment 
is _so_ cumbersome, it cannot be used in many applications.  That's why DES 
and RSA are around at all; if one-time pads worked so easily, it'd be the 
only thing used.  Anything other than a _true_ one time pad is just another
proposed cipher system and is more or less vulnerable compared to others.

There's a lot of people, here and there, that have studied crypto more seriously 
than I have (and I have studied it a long time).  They will make mincemeat of 
the above scheme.  Under the right circumstances, I may be able to defeat
your scheme.  For example, are the starting seeds the same for every
file?  If so, all I need is two to ten different files and I don't care how
you generate your "random" numbers or where you store them.  Will the same
bytes of a given file get XORed with the same value?  Then I can probably
defeat your scheme by getting access to the system as the lowliest user and
simply change my password two to ten times.  Even if you 
avoid those mistakes, there are a dozen others that basically can be
expected to blast this scheme to bits.  You are unlikely to avoid all of
them, because you don't know what they are.  There _is_ no security without
studying it.  You can't fake it.  At the least, you have to have experience
in breaking ciphers to invent them.  I know this sound annoying, but it happens
to be true.  If you doubt it, I suggest reading David Kahn's excellent book
"The Codebreakers", available in hardcover in most libraries.  After you've
finished a few chapters of it, you will realise that it is easy to _seem_
to have encrypted something and hard to have really _done_ it.

Sorry to be so annoying about it, but I've been here many times with many
intelligent people.  It still takes a while to sink in.  It looks sooo easy. . .

-- 
   Larry W. Loen        |  My Opinions are decidedly my own, so please
                        |  do not attribute them to my employer
Newsgroups: comp.lang.c