adam@misoft.UUCP (05/20/87)
I have been thinking about the one really secure encryption technique,
where the text is exclusive-ored with a random string used once only. To
regenerate the text, the recipient uses her copy of the random string, which
had been sent previously by a secure method. The random string is discarded by
both parties.
I am implementing a short C program to do this, but the one real pain
with this method is sending random strings to your various correspondants. So,
for a less secure method, I propose to generate the random string by exclusive-
oring any combination of n text and binary files held on computer:
e.g. exor /bin/sh /bin/crypt /etc/termcap | exor my_text
At the other end, the recipient types the same command line to decode the text.
All you have to do now is send the key (/bin/sh /bin/crypt /etc/termcap) by a
secure method. The other caveat is that the sender's and receiver's machines
share identical files (which is reasonably common between machines of the same
make running the same o.s.).
Does anyone have any comments as to the security of this method? It would
obviously be more secure using a common but unique random file owned by the two
parties, in combination with the standard system files.
-Adam.
/* If at first it don't compile, kludge, kludge again.*/krs@amdahl.UUCP (05/22/87)
In article <581@gec-mi-at.co.uk> adam@gec-mi-at.co.uk (Adam Quantrill) writes: > > I have been thinking about the one really secure encryption technique, >where the text is exclusive-ored with a random string used once only. >[...] >for a less secure method, I propose to generate the random string by exclusive- >oring any combination of n text and binary files held on computer: >[...] > The other caveat is that the sender's and receiver's machines >share identical files (which is reasonably common between machines of the same >make running the same o.s.). > >Does anyone have any comments as to the security of this method? It would >obviously be more secure using a common but unique random file owned by the two >parties, in combination with the standard system files. Bad news, I'm afraid. Even standard Un*x executables change when .h's are altered in a system. We ran a couple of sysgens from the *same* tapes, on the *same* system, and the kernels were different because the configuration data had been altered (add a new type of device to the configuration, and even the *contents* of the kernel will change). I wouldn't even count on the "standard" commands in machines of identical hardware running the same levels of the O/S release matching -- add a configuration change here and a local mod there and you have *no* *idea* what the binaries will look like. ...Kris -- Kristopher Stephens, | (408-746-6047) | {whatever}!amdahl!krs Amdahl Corporation | | -or- krs@amdahl.amdahl.com [The opinions expressed above are mine, solely, and do not ] [necessarily reflect the opinions or policies of Amdahl Corp. ]
simsong@mit-amt.UUCP (05/26/87)
In article <581@gec-mi-at.co.uk> adam@gec-mi-at.co.uk (Adam Quantrill) writes: >So, >for a less secure method, I propose to generate the random string by exclusive- >oring any combination of n text and binary files held on computer: > >e.g. exor /bin/sh /bin/crypt /etc/termcap | exor my_text > ... >Does anyone have any comments as to the security of this method? It would >obviously be more secure using a common but unique random file owned by the two >parties, in combination with the standard system files. > -Adam. Yes, there is a very serious problem with this method. How many different binaries are there on a system? 500? 1000? How many different ways are you going to combine them? Two? Three? I could simply compare the cyphertext message against all of them. How long would it take? Two minutes? Ten? An hour? This doesn't sound "completely secure" to me, especially when I can automatically veryify if I have the correct key or not. I'm afraid that you really have to send the random pattern seperately. Sorry. There is no easy way around this.
devine@vianet.UUCP (Bob Devine) (05/26/87)
In article <581@gec-mi-at.co.uk>, adam@gec-mi-at.co.uk (Adam Quantrill) writes: > > e.g. exor /bin/sh /bin/crypt /etc/termcap | exor my_text > > Does anyone have any comments as to the security of this method? First make sure that the files are identical! Remember that termcap (and terminfo) files vary greatly from site to site. The executable files may differ too; they certainly are different for different releases, for different machines and maybe for different configurations of same machine (compiler may insert floating point code depending on whether a fp processor is available). For better results you should not always start at the first byte of the files -- lseek in a random amount. Depending on your security needs you could select a single file that is unchanging, a spelling dictionary might be adequate. What becomes the secret key is where in the file you start from. Either send that information or have a shared, secret function that generates the same start position for sender and receiver. And don't forget that the executable files may be page-aligned. That is, at the 1k (or whatever) boundaries there will have been lots of preceding zeros. Xor using zeros gives you unmodified plain text.
hansen@mips.UUCP (05/27/87)
In article <581@gec-mi-at.co.uk> adam@gec-mi-at.co.uk (Adam Quantrill) writes: >So, >for a less secure method, I propose to generate the random string by exclusive- >oring any combination of n text and binary files held on computer: > >e.g. exor /bin/sh /bin/crypt /etc/termcap | exor my_text This method is quite similar to using a common book (dictionary, bible, romance novel) as a source of code strings. The security depends on the secrecy of the algorithm for generation of the code strings and secrecy of the selection of source material. The source material itself isn't secret at all, and divulging the algorithm (as you just did) makes the system highly insecure. The choice of source material is also vulnerable to attack if the choice can be inferred from knowlege of the parties involved (e.g. rabid UNIX freaks, working on Suns) - best to use something more obscure. -- Craig Hansen Manager, Architecture Development MIPS Computer Systems, Inc. ...decwrl!mips!hansen
gwyn@brl-smoke.UUCP (05/27/87)
In article <581@gec-mi-at.co.uk> adam@gec-mi-at.co.uk (Adam Quantrill) writes:
-for a less secure method, I propose to generate the random string by exclusive-
-oring any combination of n text and binary files held on computer:
-e.g. exor /bin/sh /bin/crypt /etc/termcap | exor my_text
-Does anyone have any comments as to the security of this method? It would
-obviously be more secure using a common but unique random file owned by the two
-parties, in combination with the standard system files.
Making allowances for the incorrect command in the example,
if you plan to encrypt many messages with this scheme, you
had better provide for a variable key to select the specific
XORs and starting offsets. Otherwise one can simply "stack"
several messages and the underlying plaintext frequency
characteristics will shine through (and once the general system
is cracked, cryptanalysis of further messages is reduced to
simple decipherment). Brute-force searches are not necessary.
Even the variable key introduces the problem of how to keep
it associated with the encrypted files (or transmitted to the
recipient, if encrypting for file transmission). Anyone
knowing the general system who can also latch onto the
specific keys is also in the position of a simple decipherer.
Note that the XOR stream you use is no better than simply taking
yay many (truly) random bits and putting them in a protected
file, so the added complexity of combining non-random files is
rather pointless. (Send your recipient a copy of the file on
a couriered magtape.)
I highly recommend working your way through the first two
volumes of Military Cryptanalytics (Callimahos & Friedman),
including working all the problem sets AND ESPECIALLY heeding
their advice for proposers of new cryptosystems, before trying
to design a new cryptosystem. These books are now available
from Aegean Press (4 volumes since the appendices are bound
separately); they've done a commendable job of reprinting, and
although these books are not inexpensive they're indispensible
for the serious cryptanalytics student. (Get the "library"
binding if you can afford it; I have the paperbacks and although
they're not bad I fear they may lose pages under heavy use,
since the pages are glued individually to the binder rather
than being sewn in signatures.) Aegean Press also reprints
several other classics of cryptography; someone not long ago
posted an abridged list, address, etc. but I could repeat it..john@hpcvlo.HP.COM (John Eaton) (05/29/87)
<<<< < For better results you should not always start at the first byte of < the files -- lseek in a random amount. Depending on your security needs < you could select a single file that is unchanging, a spelling dictionary < might be adequate. What becomes the secret key is where in the file you < start from. Either send that information or have a shared, secret function < that generates the same start position for sender and receiver. Better results for who? If you have a 100 Mbyte dictionary then you only have to search through 100 million keys for an exhaustive search. Thats trivial. Plus the non random nature of a dictionary can also be used to break it. John Eaton !hplabs!hp-pcd!john
mat@mtx5a.UUCP (m.terribile) (06/01/87)
> ... > Note that the XOR stream you use is no better than simply taking > yay many (truly) random bits and putting them in a protected > file, so the added complexity of combining non-random files is > rather pointless. (Send your recipient a copy of the file on > a couriered magtape.) > > I highly recommend working your way through the first two > volumes of Military Cryptanalytics (Callimahos & Friedman), > including working all the problem sets AND ESPECIALLY heeding > their advice for proposers of new cryptosystems, before trying > to design a new cryptosystem. ... I've not read the books in question, but for a less imposing and more interesting introduction, there's the classic *The Code Breakers* by David Kahn. Interspersed with all of the history is enough material on breaking encryption to show why a lot of obvious schemes are very weak, along with notes on the consequences of refusing to believe how weak they are. The black chambers were breaking polyalphabetics two and three centuries ago, (and simple formal methods of attack were developed in the 19th century) but even in 1917, Scientific American claimed that running-key polyalphabetics were unbreakable. Ouch! For a would-be code maker, *The Code-Breakers* is highly recommended. -- from Mole End Mark Terribile (scrape .. dig ) mtx5b!mat (Please mail to mtx5b!mat, NOT mtx5a! mat, or to mtx5a!mtx5b!mat) (mtx5b!mole-end!mat will also reach me) ,.. .,, ,,, ..,***_*.
hes@ecsvax.UUCP (Henry Schaffer) (06/01/87)
We've had a number of postings about selecting some long bit stream (a compact disk or a dictionary, ...) and xor'ing it with the message. While a compact disk may "sound" secure (:-) because of the long bit string it contains - cracking the encrypted message is *not* equal in difficulty to guessing a (random) bit string of that length. Ignoring the issue of randomness of the file contents, the guessing issue is no harder than choosing the correct disk or file, plus maybe an offset into the disk. The offset probably has fewer possibilities than the choice of the disk, but still has fewer possibilities than does the (relatively short) key used in such methods as the DES. E.g., the 56 bit key in the DES has 2^56 or about 7 x 10^16 possibilities. It would take an *unusually* large file (a million gigabytes) to have that many offsets - or to have a million files to choose from (each a gigabyte) and then an offset into the file. None of the examples given comes anywhere close to this magnitude. So it doesn't appear that we have a good substitute for the one-time-pad. --henry schaffer n c state univ
gwyn@brl-smoke.ARPA (Doug Gwyn ) (06/02/87)
In article <1802@mtx5a.UUCP> mat@mtx5a.UUCP (m.terribile) writes: >... there's the classic *The Code Breakers* by David Kahn. That is indeed a good introduction to the field, but it won't make one a cryptanalyst. Be sure to get the original, UNABRIDGED hardcover edition instead of the abridged paperback. You can probably find this in your public library, since it was a best-seller when it came out (was that in 1967? -- something like that).
devine@vianet.UUCP (06/03/87)
In article <1290002@hpcvlo.HP.COM>, john@hpcvlo.HP.COM (John Eaton) writes: >< For better results you should not always start at the first byte [...] > > Better results for who? If you have a 100 Mbyte dictionary then you only have > to search through 100 million keys for an exhaustive search. Thats trivial. > Plus the non random nature of a dictionary can also be used to break it. When I wrote 'better' I meant 'better' not 'perfect'. Using a code book that is easily read by anyone is never going to give top level security. However, it is an easy step that would give a little more trouble to those listening in. Note that a 100 Mb file yields more than 100 million possible bit strings because the strings do not have to byte aligned.