Cryptography-Digest Digest #113, Volume #10 Thu, 26 Aug 99 11:13:03 EDT
Contents:
Re: NEW THREAD on compression (SCOTT19U.ZIP_GUY)
2 person data exchange - best method? ("Shaun Wilde")
Re: cryptographic DLL ("Trevor Jackson, III")
Re: Can americans export crypto when in another country? ("Trevor Jackson, III")
RE: Searching for Source of PGPPhone or Document how it works (Gary)
Re: How Easy Can Terrorists Get Strong Encrypt?
btw (Keith A Monahan)
Re: passphrases (Keith A Monahan)
Re: One-time pad encryption. ("Trevor Jackson, III")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: NEW THREAD on compression
Date: Thu, 26 Aug 1999 12:55:19 GMT
In article <[EMAIL PROTECTED]>, Mok-Kong Shen <[EMAIL PROTECTED]>
wrote:
>SCOTT19U.ZIP_GUY wrote:
>>
>> <[EMAIL PROTECTED]> wrote:
>> >As described in your post, a number of checks are done at the
>> >end of processing to take care of the different possible special
>> >cases such that the scheme can work without trouble. I think that
>> >the following scheme is simpler (hence somewhat easier to program)
>> >and yet achieves all the purposes of yours. It has the following
>> >conventions:
>> >
>> >(1) No input symbol has a Huffman code of all zeros (any number).
>> >
>> >(2) If the last output bit is not at byte boundary, add 0's
>> > till byte boundary.
>> >
>> >(3) After (2) is done, delete all trailing bytes (any number) that
>> > contain all 0's.
>
>>
>> FIrst of all it would not be "one to one". I am not sure how many
>> cases don't map back and forth. For example. I claim that
>> it is a neat fact if
>> 1) any file A when compressed to a B when decompressed A should come
>> back. And any file C when decompressed to D when compressed comes back to C
>> as a quick example what happens to a
>> file C that is defined as 00000000 00000000
>> what is this after it is decompressed and what could possibly compress to
> this
>> file.
>
>I am not sure that I understand you. Is C an input (not compressed)
>file? In that case we have two (8-bit) ASCII characters that are
>the same and that has a certain Huffman code and the file is encoded
>just as any other file. In the other case where C is a compressed
>file, the answer is that such a file cannot exist because of my
>convention (3). It remains to discuss how the program behaves if
>it is nevertheless asked to decompress such a file. From (1) and
>(2) it knows that a sequence of all 0's (and nothing following that)
>means padding. So in this particular example it outputs nothing
>(the ouput file is empty). No error message is issued, since there
>are no hanging bits in the buffer that remain to be decoded. Hence
>there is no 'abnormality' which you fear could be of use to the
>analyst. If you still fell that this could consitute certain clue to
>the analyst, (3) can be changed to be an 'optional' rule, i.e.
>trailing bytes of all 0's may be omitted if the user desires it
>(or let the program make a random decision of doing that).
>
>> 2) In my method you cover all 256 symbols each at start has 8 bit paths. To
>> use your method the all zeros symbol which is never used has to occupy the
>> longest path. So at start 255 symbols have 8 bit paths while the other 1
> would
>> have a 9 bit path.
>
>There is not much difference in efficiency. One constructs the
>Huffman tree this way: Invent an extra symbol (257-th) and give it
>the lowest frequency and keep it always on the left side (I assign 0
>to left) of the tree. So it gets a code of all 0's assigned. This
>extra symbol is never used, of course.
>
>I have considered the compression, decompression and compression
>back processes. There can be no case that could yield anything wrong.
>Note that because of (3), if on decompression the buffer at the
>end of the file is not empty, the program appends as many 0's to
>the buffer as needed to form a valid Huffman code.
>
>If you have counter-examples, please give (a small) one so that
>we can discuss that with paper and pencil alone.
>
>M. K. Shen
>
>>
>> However I think what you have is what most people would do for a small
>> huffman tree. But for one that represents the full 256 character set most
>> would make a minor change. Since it is easy to guarnatee that a huffman tree
>> of 256 leaves will always have a path of 8 or mores zeros. Use the fill zeros
>> which will always be at most 7 in the last byte if needed and there can be
>> no confusion as to the end of the compressed file. This is what I did when
>> I started playing with the Huffman compression since I did not like the extra
>> bytes that the public domain code had.
>> But even this bothered me since I noticed that when one tried to decompress
>> and recompress back you don't always get the same file. Therefore it must
>> be a weakness and one should be able to do more. That is when I came up
>> with current scheme. Like I said I am not done yet and your discussions have
>> made be look deeper. I wish I had a printer. But I have redone the logic of
>> the compression so that the new case fits. I had slowly made changes to the
>> compression version and it had become a monster of logic conditions so I
>> have re thought them. But even then this is first cut. I don't like the fact
> I
>> am currently useing the all zero case as the longest path. I will make a new
>> version that changes the bit 0/1 bit assignments as the tree is built so
> that
>> instead of the all zero case it will use instead as fill the current longest
>> path to a leaf. And instead of the all ones for cutoff it will use the
> current
>> shortest path to leaf from the internal node that it stopped at. This should
>> be exportable since it will be pure compression and not encryption but any
>> one that looks at text compressed by this might be under the illusion that
>> it looks like encryption. When in fact it is meant to be used as a first pass
>> before encryption takes place.
>> However if someone took the starting 256 leaf table and did not use them
>> in normal order. There would be as many arangements as in a 8 bit single
>> cycle table. But not sure how to calulate that:)
>> If one then revesrsed the file end for end and used a second huffman
>> compression again with random starting leaf values. This could be thought
>> of as encryption but I am not sure. Since I will only use a normal nokeyed
>> starting order for normal compression at least for any code I write on the
>> US side of the Mexican border.
>>
>> >http://home.t-online.de/home/mok-kong.shen (new addr.)
Don't add anything else yet. I agree one extra symbol is small.
I agree the scheme will allow any file to be compresed uncompressed
and will compress back again to the original file. But it is not "one to one".
To be "one to one" and useful as a first pass before encryption it should have
in my view the property that. If any A compresses to a file B then
uncompressing B should get A back (yours meets this part as do most
methods). The next part is harder to meet and that is. Any file C when
uncompressed to a file D and then when D is compressed you get file
C back (your scheme does not meet this). The counter example is
to pretend that the file made of only two bytes 00000000 00000000
is a compressed file. How would you uncompress this file with your
method. SHOW ME use any tree you want.
Know you may ask how such a file gets to be even a candidate for
uncompression. This is how. You send a message to your friend. First
you compress the message then you encrypt it. Your friend gets the
message decrypts it and then decompress that result to get original
message. Your enemy also intercpets the encrypted message during
the transmition. When it guess a ( worng key) lets pretend he gets
in the front of the file 00000000 00000000 .... know he tries to decompress
it. He can't becasue this file is not possibly a valid compressed file under
your scheme so the enemy is imediately given information as to why his
guess of the key is wrong. This may lead to a greater reduction than even
the blind testing of keys, THe attacker may even have the math smarts to
eliminate who classes of keys based on the fact they would lead to unreal
compressed files. It would be far safer for you if every file that an attacker
got with a wrong key was a real compressed file. That why the attacker has
to uncompress the file and then decide by exaiming the next output phase as
to weather or not the file had meaning. This is more than a few extra steps.
If he gets an impossible file he KNOWS he has the wrong key. IF he gets
somthing strange he does not know right a way that it is wrong. He has to
rule out other languages oher types of files or even the posssiblity that
these are special files such as just a binary of your secret keys that your
friend needed to decrypt some stuff that he needs for some other program.
The point is if every file that the attacker can get with a false key should
send the attacker farther down the wrong trail. Don't give him the data to
know that a path is false. Make the bastards work
that he is on a fasle trail.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
------------------------------
From: "Shaun Wilde" <[EMAIL PROTECTED]>
Subject: 2 person data exchange - best method?
Date: Thu, 26 Aug 1999 12:23:55 +0100
Hi all,
Please forgive this newbie but I have a query as regards crypto algorithms.
If I have 2 people who wish to exchange information what is the best way to
do so assuming that I have no trustee (holder of public keys) and such that
I can defeat the Man-In-The-Middle attack.
Can I get away with message splitting (interlock-protocol?)? Is there any
problems with this? Is there anything better?
TIA
Shaun Wilde
------------------------------
Date: Thu, 26 Aug 1999 08:55:38 -0400
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: cryptographic DLL
Greg wrote:
> > In fact, it's unclear you'd be breaking Canadian law (the rules about
> > "US-source" stuff are *very* hazy), but it's certain you'd be breaking
> > US law. US Persons (as defined in the EAR) are not allowed to post
> strong
> > crypto to the Internet without a licence, period. It doesn't matter
> where
> > you happen to be when you do it.
>
> I can't buy that. If you go out of the USA with crypto to post it on
> the web, you violate the export rules because you took it with you.
>
> But if you go out and write the code, you do not violate the export
> rules. (Unless you think the government will begin to consider what is
> in your mind a commodity?) In fact, you can go out with the code
> written on paper, type it into a PC in another country, and you have
> not exported any crypto. This is exactly what PGP Inc does today.
>
> If you post crypto code on an international server with internationally
> developed code, there is no export taking place.
>
> I could take every bit of my elliptic curve cryptosystem software save
> one file that could sit on about 100 lines, type in the lines while in
> flight to Europe or Mexico from a print out, then have a fully
> operational nuclear strength cryptosystem ready to post to a web site
> when I arrive. I have not exported any regulated software in the
> process. And NSA has already declared that the other files are not
> regulated by the EAR.
>
> I am actually thinking of doing this, though a lot of preparations
> would have to be made, like finding a site in Mexico, that I can easily
> and cheaply use. I am just no there yet.
My understanding of the legal situation is limited, but I looked into this
issue with an eye toward overseas development. I found that crossing the US
border with non-printed machine readable source code is only one of the
restricted acts that constitute "export". It appears that a US citizen may
not work overseas to develop strong crypto, which is why, as I understand
it, RSA had to hire foreign nationals to staff their overseas development
project rather than sending US staff out of the country. I also found that
US citizens were forbidden to assist non-US citizens (& non-greencard
holders) in developing strong crypto.
The only legal path for unlicensed export of strong cypto was printed, in
any format, even bar codes (to avoid OCR problems), transmitted between
staffs that do not overlap. I.e., if a US citizen accompanies the printed
material it is assumed that the citizen is transmitting key information,
otherwise why make the trip?
Caveats:
- the law is not what it written; the law is what is enforced (US Supreme
Court dicta)
- this assessment is ~18 months old.
- this assessment was formed by an amateur, not a professional
My hope is the Berstein case illuminates the arbitrary and capricious nature
of the EAR.
------------------------------
Date: Thu, 26 Aug 1999 10:07:21 -0400
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Can americans export crypto when in another country?
I believe that US citizens suffer from the US crypto regs in the same way
they suffer from the US tax regs. Contrary to most national tax systems,
the IRS tries to collect tax from ll US citizens no matter where they
reside. Similarly, the US crypto regs prohibit US citizens from
contributing to unlicensed non-US crypto systems no matter where they
perform the work.
Michael D. Crawford wrote:
> Hi,
>
> I'm an American citizen, presently living in the US, and I've been
> wanting for a while to port Speak Freely to the Be operating system.
> See http://www.speakfreely.org and http://www.be.com
>
> Speak Freely includes encryption, so if I port that while I'm in the US
> I can't contribute my changes back to the original source archives,
> which are in Switzerland.
>
> But I may be moving to Canada in a few months (I'm marrying a Canadian
> woman). Once I'm in Canada, as long as I create my port of the crypto
> software while I'm in Canada (so I never bring the crypto Speak Freely
> into the US, and don't take it back out again), can I export the crypto
> back to Switzerland without violating US laws?
>
> I expect to travel to the US frequently on business and it would be a
> drag to get arrested for some free software work I do while in Canada.
>
> Canada itself has some export controls, but according to the Crypto Law
> Survey at:
>
> http://cwis.kub.nl/~frw/people/koops/lawsurvy.htm
>
> crypto is not export controlled if the software is in the public domain,
> which is the case for the original speak freely and will be true for my
> changes.
>
> Mike
>
> --
> Michael D. Crawford
> GoingWare - Expert Software Development and Consulting
> http://www.goingware.com
> [EMAIL PROTECTED]
>
> Tilting at Windmills for a Better Tomorrow.
------------------------------
From: Gary <[EMAIL PROTECTED]>
Subject: RE: Searching for Source of PGPPhone or Document how it works
Date: Thu, 26 Aug 1999 10:06:44 -0400
Similar method to PGP phone:
A sesion key is securely randomly generated.
This key is securely exchanged before the start of the communication using
RSA
(PGP) or Diffie Hillman.
Compress analog to digital along the lines of cell phone compression (GSM
etc).
Then symmetrically encrypt this digital data using RC4, TEA etc with the
session key.
Send this data.
Data is received, deciphered with session key and decompressed.
The libraries for audio compression and symmetric encryption are already in
the Windows 32 libraries. I don't know how fast they are for real time.
However a voice mail system could easily be implemented using this, even if
slow.
>===== Original Message From [EMAIL PROTECTED] (Hartmut Schroeder) =====
>Hi,
>while working on an standalone Cryptophone the Idea comes in mind makeing
>it compatible with existing Solutions (even PC-Based).
>
>The only worth of implementing Solution seem to be PGPPhone but it seems
>that develoment has been stopped?!?
>
>It also seem that there's no Source avail. Is that true?
>
>I don't require the Source but a Document how the communication Protocol
works
>will tell me if and how we can implement this.
>Has anybody seen such a Document and can point me to it?
>
>Regards H.Schroeder
>
>
>Hartmut Schroeder MMS Communication AG
>mailto:[EMAIL PROTECTED] Eiffestrasse 598
>http://www.mms.de/~hacko 20537 Hamburg, Germany
>Phone: +49 40 211105-40 Fax: +49 40 210 32 210
>UTM 32U0569835 5934083 WGS84
============================================================
Get your FREE web-based e-mail and newsgroup access at:
http://MailAndNews.com and http://MailAndNews.co.uk
Create a new mailbox, or access your existing IMAP4 or
POP3 mailbox from anywhere with just a web browser.
============================================================
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: How Easy Can Terrorists Get Strong Encrypt?
Date: 26 Aug 99 14:01:28 GMT
Tramm Hudson ([EMAIL PROTECTED]) wrote:
: I could see no restrictions placed upon export to "hostile"
: countries. Can you please point to the section that places
: any limits on export? Or is "every compiler" a bit too broad?
The latter. I would think that it would be clear that I meant the typical,
usual, shrink-wrapped high price stuff. But it's true that gcc exists, and
does largely cancel that half of the argument - as I did note.
John Savard
------------------------------
From: [EMAIL PROTECTED] (Keith A Monahan)
Subject: btw
Date: 26 Aug 1999 14:12:23 GMT
FYI - it sucks trying to brute force your own password. When I came up
with the password, I had no idea its biggest enemy would be me.
Keith
------------------------------
From: [EMAIL PROTECTED] (Keith A Monahan)
Subject: Re: passphrases
Date: 26 Aug 1999 14:39:07 GMT
I happened to be looking through Applied Cryptography(ISBN 0471117099)
and to summarize Bruce S gives us reasons not to on page 183.
"No encryption key should be used for an indefinite period"
- "The longer a key is used, the greater chance it will be comprised"
- "The longer a key is used, the greater loss if it IS comprised"
- "The longer a key is used, the more tempting it is for someone
to attempt the bruteforce/dictionary attack"
- "It is generally easier to do cryptanalysis with more ciphertext
encrypted with the same key."
I responded earlier to this post with a couple of those answers, and
I wanted to provide some credible support.
Keith
[EMAIL PROTECTED] wrote:
: It has been said that it's wise to change your passphrase often to stay
: secure.
: However, consider this:
: Lets assume you pick a very good passphrase that has sufficient entropy
: (i.e. many random characters, numbers, and punct.) that you can easily
: remember. Since this passphrase cant be guessed or brute forced in a
: resonable time, your data will remain secure for a long time.
: But, if there is a hole in your implementation such that the key can be
: recovered (like a key logger, swapfile, slack disk, EMI, etc.), then it
: doesn't matter how often you change your passphrase, you're screwed!!
: Therefore, as long as you have no holes and a very good passphrase, you
: don't have to change it.
: Any opinions?
------------------------------
Date: Thu, 26 Aug 1999 09:44:13 -0400
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: One-time pad encryption.
rosi wrote:
> Guess, it just would not leave us. :)
>
> While hanging off the other thread (thinking what the heaven I meant),
> old dust in my head got stirred up. More precisely the 'secret expansion'
> part.
>
> I believe (though have to go back and think carefully, lest there are holes)
> MTP is near possible and quite 'practical'. To be not so pompous, there
> may not be perfectness but, IMO, near perfectness (will give a slightly
> better description). However, one-wayness should be guaranteed.
>
> Like OTP, there is no magic. There ARE assumptions.
> 1. The bits generated should be 'truly' random.
> 2. The bandwidth is still needed for the transfer of the pad(s)
> 3. (As MTP) an initial secret needs to be securely established and,
> just as the pad of OTP, it needs to be secured. (But no worry
> when openly distribute its multi-time used version, yet of course
> authentication is needed, but hopefully no conjecture involved)
>
> This applies the notions of Perfect Secrecy and (non-compressing) one-
> way functions.
>
> Near perfectness is in the following _sense_: a pad is not as long as the
> message to be protected but, e.g. is alway short of one bit which will be
> made up by the parity of the pad (or part of the pad) for an encryption
> instance.
>
> I can find myself wrong. If others already have similar thoughts, please
> point out or declare. Likely that is the case.
>
> --- (My Signature)
I've speculated on ways to gracefully degrade an OTP into an MTP. The core idea
is to shroud the actual OTP by a bit selector.
Consider the "truly" random keypad as a set of individual bits -- an entropy
pool. For each message to be encrypted uniformly select bits from the pool
until you have as many key bits as there are bits in the message. These bits
are the message key. Use the typical Cipher = Plain XOR Key encryption process.
If the receiver has a copy (out of band) of the pool, and uses the same bit
selection algorithm (PRNG) decryption is the same as encryption.
In this approach the pad is not the key. The key is constructed from the pad.
The entropy of the pad is gradually reused, but the structure/sequence of the
pad is not used. Each message probably shares key bits with every other
message, so the system of messages is not perfect security.
This approach eliminates one of the troublesome aspects of OTP systems which is
message key size == messatge text size. In fact one could use a pool smaller
than the smallest message.
An interesting aspect of this approach is that there are two parts of the system
to hide. The entropy pool has to be treated just like an OTP keypad. The PRNG
seed has to be treated just like the message key of a symmetric cipher. So it
would be possible to produce "shrouded PGP" by using the symmetric message key
as a seed for an entropy pool bit selector PRNG.
Note carefully that this kind of system is NOT a One-Time Pad. The key resuse
starts within the very first message! In theory, the first two bits are
related. The term I've been using for this is "degraded OTP".
Mathematically, the degree is degradation is log (sum message sizes) /
log(entropy pool size). This ratio defines the degree of theoretical
compromise. I suspect, but have not proven, that a degradation ratio < 1 is
equivalent to a true OTP.
---- New topic: Shrouded PRNG
Rather than consider the PRNG bit selector as the shroud for the OTP keypad, the
entropy pool can be considered as shroud for the PRNG. This makes it possible
to scalably add entropy (non-determinism) to a deterministic algorithm.
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
