Cryptography-Digest Digest #887, Volume #10 Tue, 11 Jan 00 23:13:01 EST
Contents:
Q: Block algorithms with variable block size (Mok-Kong Shen)
Re: Questions about message digest functions (lordcow77)
Re: "1:1 adaptive huffman compression" doesn't work (SCOTT19U.ZIP_GUY)
Encryption Keys ("Paul Roy")
Re: Modular Inverse with RSA (Frank the root)
Re: Singh Enigma - Stage 2 ("Pete")
Re: Modular Inverse with RSA ("Alan")
Re: Clearer (hopefully?) example of 1-1 problem. ("Douglas A. Gwyn")
Re: Cryptography in Tom Clancy (Arturo)
Re: "1:1 adaptive huffman compression" doesn't work (Tim Tyler)
Re: Questions about message digest functions (Tim Tyler)
Re: frequency analysis with homophones ("Douglas A. Gwyn")
Re: The Cipher Challenge from the Code Book ("Douglas A. Gwyn")
Re: AES & satellite example (Jerry Coffin)
Re: About DES algorithm. (Jerry Coffin)
Re: AES & satellite example (Nicol So)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Q: Block algorithms with variable block size
Date: Wed, 12 Jan 2000 01:39:31 +0100
Are there block encryption algorithms in the literature that
have block sizes that are variable, i.e. user choosable (maybe with
some constraints)? I believe that such a parametrization could be
quite valuable, though it might not be easy to do with the
techniques that underly certain currently well-known algorithms.
Thanks.
M. K. Shen
------------------------------
From: lordcow77 <[EMAIL PROTECTED]>
Subject: Re: Questions about message digest functions
Date: Tue, 11 Jan 2000 16:35:08 -0800
In article <[EMAIL PROTECTED]>, Tim Tyler <[EMAIL PROTECTED]> wrote:
> As I understand it, usually the work required to break the
> construction
> depends on how large the original primes are - rather than on the
> size
> of the hash (provided the latter is not too large for the
> generating
> primes in question).
> Also note that the construction may be repeated a number of times,
> using
> multiple keys and multiple private primes.
> To clarify, is it your objection that it's too labor intensive to
> find
> primes that are sufficiently large, and to apply such operations
> in series
> enough times to the point where the level of security offered
> roughly equals that of an ordinary hash?
> Such a construction may be very slow - and difficult for a user to
> verify
> it is operating as claimed - but I'm not sure it is necessarily
> weak.
You seem to have the acquired skill of ignoring the points raised by
other people and attacking strawman arguments that were never made. For
what rational reason would a person want to use a hash function that is
slower, takes more memory, possibly less secure, and more difficult to
implement than the conventional hash functions are PRFs? You have yet
to present a reasoned argument for your assertion that such a hash
function is neccesarily more secure than a PRF. There's nothing bad
about being wrong once in a while and admitting it.
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: "1:1 adaptive huffman compression" doesn't work
Date: Wed, 12 Jan 2000 02:22:44 GMT
In article <[EMAIL PROTECTED]>, Mok-Kong Shen <[EMAIL PROTECTED]>
wrote:
>John Savard wrote:
>>
>> I can achieve that if I don't have to go to byte boundaries. I can
>> achieve that if I'm allowed to use random padding with a length
>> indicator. But trying to do it David Scott's way, that condition can
>> no longer be achieved (well, I can always XOR my last byte with a
>> checksum of the rest of the message to at least mask the bias...).
>
>I am not quite sure whether one couldn't even attempt to 'define'
>the 1-1 problem away with a 'convention'. That is, if on compression
>the last code symbol does not fill to a byte boundary, then the
>software has to do filling with bits that do not form a valid code
>symbol and it is 'required' by convention that the filling is
>to be random, say dependent on the system clock. Now if one
>compresses one and the same file twice, the results are identical
>with the exception of the filling bits. This way I suppose the
>original argument for 1-1 in the case of the analyst using wrong
>keys to decrpyt (i.e. the argument of thereby leaking some information
>to him because of non-1-1) no longer applies. Certainly I admit
>that what I described is a 'trick', but it works for the purpose at
>hand, doesn't it? Or there could be technical problems of realizing
>that 'convention' that I haven't yet seen? Thanks.
>
>M. K. Shen
The problem with adding random informaion is that when you decompress
you have to know what is random so the compressor does not mistakenly
use some of the data to compress. For eample your doing huffman coding
the old way. Your symbol last symbol compressed its in bit postion 2 of the
last byte. How do you add random data so the compressor does not use some
of it. It is far better to use the 1-1 compressor in the first place. ALso
is Dan V. still there did he check the 2000 1 10 version of the software yet?
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website NOT FOR WIMPS
http://members.xoom.com/ecil/index.htm
Scott rejected paper for the ACM
http://members.xoom.com/ecil/dspaper.htm
Scott famous Compression Page WIMPS allowed
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
"The road to tyranny, we must never forget, begins with the destruction of the
truth."
------------------------------
From: "Paul Roy" <[EMAIL PROTECTED]>
Subject: Encryption Keys
Date: Wed, 12 Jan 2000 01:28:08 GMT
Hello All ---
I found this on Hacker News. Rather disturbing? Comments?
Proteus
*****----------******
Encryption Keys Easily Found On Systems
contributed by evenprime
Researchers at nCipher in Cambridge, England have found a way to easily find
encryption keys on target systems. The technology centers on this: There is a
general assumption that encryption keys will be impossible to find because
they are buried in servers crowded with similar strings of code. What the
researchers discovered, however, is that encryption keys are more random than
other data stored in servers. To find the encryption key, one need only search
for abnormally random data.
ZD Net
------------------------------
From: Frank the root <[EMAIL PROTECTED]>
Subject: Re: Modular Inverse with RSA
Date: Wed, 12 Jan 2000 02:04:49 GMT
Ryan Phillips wrote:
>After reading Applied Crypto I'm still confused on creating a private
>key
>with RSA. if d=e^(-1) mod ((p-1)(q-1)), how do you calculate d.
>
>so if p = 47, q = 71, (p-1)(q-1) = 3220,
>choose e at random that abides by the prime rules, e = 79 (just for
>this case).
>now solve:
>d =79^(-1) mod 3220 , the answer is 1019
>
>How do you get the answer 1019, and if someone could include another
>example
>that would be great.
>
>Thanks for your time.
>
>- -Ryan Phillips
Hum.... Is it possible that more than one private key exist???? I can
see that the integers 4239, 7459, 10 679, 17 119, 20 339, 23 559, and
maybe others satisfy the "ed mod Phi(n) = 1" relation.
Frank
--
Ceux qui r�vent le jour, savent des choses qu'ignorent ceux qui
r�vent la nuit.
------------------------------
From: "Pete" <[EMAIL PROTECTED]>
Subject: Re: Singh Enigma - Stage 2
Date: Wed, 12 Jan 2000 02:08:30 -0000
Reply-To: "Pete" <[EMAIL PROTECTED]>
"al-Kindi" <[EMAIL PROTECTED]> wrote in message
news:85b3bk$v06$[EMAIL PROTECTED]...
: Oh well, another altruistic impulse wasted... :)
It was a good idea and much appreciated! (Until I saw the other URL
though....)
Pete.
--
"Stop prying eyes, encrypt that data!" - Crime Prevention Bureau, Hong Kong
Police.
PGP Key ID: 0x3F8C42DF
The International PGP Home Page - http://www.pgpi.org
------------------------------
From: "Alan" <[EMAIL PROTECTED]>
Subject: Re: Modular Inverse with RSA
Date: Tue, 11 Jan 2000 18:27:02 -0800
Use the Extended Euclidean Algorithm
to find the inverse.
Ryan Phillips <[EMAIL PROTECTED]> wrote in message
news:85ef2v$[EMAIL PROTECTED]...
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> After reading Applied Crypto I'm still confused on creating a private
> key
> with RSA. if d=e^(-1) mod ((p-1)(q-1)), how do you calculate d.
>
> so if p = 47, q = 71, (p-1)(q-1) = 3220,
> choose e at random that abides by the prime rules, e = 79 (just for
> this case).
> now solve:
> d =79^(-1) mod 3220 , the answer is 1019
>
> How do you get the answer 1019, and if someone could include another
> example
> that would be great.
>
> Thanks for your time.
>
> - -Ryan Phillips
>
> -----BEGIN PGP SIGNATURE-----
> Version: PGP 6.5.2
>
> iQA/AwUBOHrA6uB/yjQQFbPXEQJ8BACdGLo5g13iKQN/4mlo9cg5/HAbP4wAn1rX
> kRdCMBKcQFvwgnwcmXDk+jhe
> =Wsew
> -----END PGP SIGNATURE-----
>
>
>
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Clearer (hopefully?) example of 1-1 problem.
Date: Wed, 12 Jan 2000 02:41:15 GMT
Gary wrote:
> Compressed data can be seperated into 2 streams.
> A) Data from the original uncompressed data.
> B) Codes.
> eg Run length encoding example
You're letting yourself be misled into thinking that one example
(RLE) typifies the entire class of compression algorithms. It is
easy to create an example of a compression algorithm that does
*not* embed "the original uncompressed data" in the output.
------------------------------
From: [EMAIL PROTECTED]=NOSPAM (Arturo)
Subject: Re: Cryptography in Tom Clancy
Date: Tue, 11 Jan 2000 08:00:15 GMT
On Mon, 10 Jan 2000 17:10:25 GMT, [EMAIL PROTECTED] (Johnny Bravo)
wrote:
>On Sat, 08 Jan 2000 14:33:07 -0700, Shawn Willden <[EMAIL PROTECTED]>
>wrote:
>
> Hey, if you were in a city that was about to be nuked in 20 minutes
>and if you decrypted a 128 bit message it saves your life... :)
>
... i�d better kiss my son goodbye than waste my life in such
a desperate attempt. There�s a highetr likelyhood of a meteoroid
smashing right through the nuke warhead.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: "1:1 adaptive huffman compression" doesn't work
Reply-To: [EMAIL PROTECTED]
Date: Wed, 12 Jan 2000 02:04:34 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
: John Savard wrote:
:> I can achieve that if I don't have to go to byte boundaries. I can
:> achieve that if I'm allowed to use random padding with a length
:> indicator. But trying to do it David Scott's way, that condition can
:> no longer be achieved [...]
: I am not quite sure whether one couldn't even attempt to 'define'
: the 1-1 problem away with a 'convention'. That is, if on compression
: the last code symbol does not fill to a byte boundary, then the
: software has to do filling with bits that do not form a valid code
: symbol and it is 'required' by convention that the filling is
: to be random, say dependent on the system clock. [...]
This is pretty much the same technique as John Savard proposed.
It works to the extent that you can generate genuinely random bits.
If your bits are not completely random then you still have problems.
You also wind up with a non-deterministic compressor. The system
fails to exploit the range of the compressor to itsgreatest possible
extent. It is no longer portable to embedded environments with no
obvious reliable source of genuinely random noise available.
The system would probably work /fairly/ well in practice. But since
the ending of Huffman files (and Arithmetic files for that matter)
appears to have been completely solved, I see no reason for introducing
such possible sources of error.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
LSD melts in your mind, not in your hand.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Questions about message digest functions
Reply-To: [EMAIL PROTECTED]
Date: Wed, 12 Jan 2000 01:54:36 GMT
David A Molnar <[EMAIL PROTECTED]> wrote:
: Tim Tyler <[EMAIL PROTECTED]> wrote:
:> : Think about what happens if e and phi(n) are not relatively prime.
:> This doesn't produce any noticable effect at this point - it seems that
:> they would be, by design.
: An example of "RSA with e and phi(n) not relatively prime" is the Rabin
: function. For message m, the ciphertext c = m^2 mod n. Since phi(n) =
: (p-1)(q-1) for n = pq, 2 is a factor of phi(n) and hence 2 and
: phi(n) are not relatively prime. This is not a bijection [...]
The designer of the function gets to choose e (the fixed key used for the
particular hash in question). He also gets to choose p and q. Thus he
is in the perfect position to ensure that e and (p - 1)(q - 1) *are*
relatively prime.
That's how it seems to me anyway.
:> I'm happy to agree that an individual with no knowledge of the
:> (discarded) private key has no way to easily verify that the structure
:> is performing as it should be.
: That much is true. If you are willing to do a little bit of work before
: discarding the private key, however, you might produce a non-interactive
: zero-knowledge proof that the public key is correctly formed and so the
: function is bijective. Then even after the private key is discarded,
: the proof could be used to convince everyone that the function really
: is bijective.
A fascinating avenue I am unlikely to have considered exploring.
Thanks for contributing.
[snip a permutation using exp, mod, and a prime modulus]
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
People who live in stone houses shouldn't throw glasses.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: frequency analysis with homophones
Date: Wed, 12 Jan 2000 03:18:14 GMT
[EMAIL PROTECTED] wrote:
> I've found quite a bit of interesting material about HMM's on the
> Internet, but I'm lacking a good example of how these could be applied
> in cryptanalysis. Can you refer me to a text or other source?
Unfortunately there are no good examples on line (that I know of).
There was a paper in an early issue of Cryptologia, as I recall,
but it didn't pick a very good example. In 1998 I got the Agency
to declassify (with minor redaction) a fairly good example, "An
Application of PTAH to the Voynich Manuscript" by Mary E. D'Imperio,
NSA Tech. J., XXIV, 2 (Spring 1979), pp. 65-92, but it isn't yet
available on line.
When one applies this technology to a homophonic substitution, the
ciphertext is used to "train" a HMM (using the maximum-likelihood
criterion). If the model was a priori constrained to have its number
of states equal to an appropriate number of categories for the
plaintext alphabet (e.g. four, which could turn out to correspond to
{hard_consonant, soft_consonant, vowel, separator}), the result will
be a reasonably good assignment of the cipher symbols to the
categories. (If there is a *lot* of ciphertext, one could make the
categories be just the individual plaintext letters.) The transition
matrix would make it evident which category is which; running the
model on a large volume of known plaintext could serve as a way to
"calibrate" the transition behavior.
Note that this process does not use any a-priori knowledge of the
characteristics of the plaintext; the categories develop in the
course of fitting the model to the observed data. There are
occasions when this is the best one can do; at other times, it would
be better if the process were able to factor in a-priori known
population statistics of the system being modeled. But the standard
method (Baum-Eagon-Welch) doesn't do that.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: The Cipher Challenge from the Code Book
Date: Wed, 12 Jan 2000 03:24:49 GMT
> > >begin 644 DEBUGGER.BIN
> > > (-&>`_EU-_/$`
> > ><blank line>
> > >end
Staffan Ulfberg wrote:
> Well, but a space works as well as a back-quote, and I suppose that's
> what Singh used. Of course, in print a space doesn't show very well
> at the end of a line...
That was what I assumed.
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: AES & satellite example
Date: Tue, 11 Jan 2000 20:32:21 -0700
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
[ ... ]
> I think there is a basic assumption here that the new cipher would be
> delivered, encrypted under the old, insecure cipher.
I don't think anybody's (quite) crazy enough to assume that.
> This is not a
> sound assumption. Executable algorithm code is generally signed, such
> that the target satellite will reject any attempt to upload bogus
> algorithm code. The code may also be encrypted and separate algorithms
> are generally used to secure code.
This simply shifts the problem rather than curing it.
> For example, I know of systems where classified algorithm code in
> encrypted under an algorithm specific to that function and the
> encrypted code image is signed under another algorithm specific to
> that purpose. Both of these algorithms that protect the code from
> substitution and disclosure are dedicated to these functions, not used
> for anything else and can not be replaced.
This probably helps a little, but only a little. The only real
improvement is that the algorithm used to protect code is (presumably)
only used relatively rarely, restricting an opponent's access to known
plaintext. Since the code to implement a new algorithm is presumably
inspected far more closely than routine traffic, it's also likely to
reduce or even eliminate an opponent's possibility of introducing
chosen plaintext into the system. OTOH, an opponent might be able to
get known or chosen plaintext in areas such as error messages, thus
reducing even this minor advantage.
IOW, if you're going to allow updating of the code, you certainly want
to use a separate algorithm, but even at best this is only a _minor_
improvement, not a real cure for the fundamental problem.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: About DES algorithm.
Date: Tue, 11 Jan 2000 20:36:26 -0700
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
[ ... ]
> For a description of DES, see FIPS publication 46-1 (or higher,
> I forgot):
> Data Encryption Standard.
At least the last time I looked, the current version was FIPS 46-2.
That, however, is likely to change soon if it hasn't already -- NIST
had a proposed draft of FIPS 46-3 available a while back, and I see
little reason to believe that it wouldn't be accepted. In case you
care, FIPS 46-3 replaces DES with 3DES; the basic algorithm remains
unchanged.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: AES & satellite example
Date: Tue, 11 Jan 2000 22:45:39 -0500
Reply-To: see.signature
Frank Gifford wrote:
>
> In article <[EMAIL PROTECTED]>, Nicol So <see.signature> wrote:
> >
> >Are you sure it is indeed difficult (or not possible) to update the
> >(hardware) encryption implementation on satellites? (I can think of a
> >fairly obvious yet secure solution to the problem).
>
> And fast? Sure a Space Shuttle can be sent up with a new cipher-on-a-board,
> but those take quite a while to get going.
Yes, pretty obvious, secure, and fast! (Unless you thought I was joking,
you wouldn't really believe that I was proposing to send the Shuttle).
As an application to justify multiple AES algorithms, I don't think
satellites are a good example. You don't *need to* have multiple
hardware implementations to guard against undiscovered weaknesses in
your cipher. For commercial communication satellites, which are
generally not endpoints of communication, you don't need to encrypt the
inband traffic. Encryption/decryption can be done at the
uplinks/downlinks. Encrypting and authenticating the commands do not
need such a high level of performance as to *require* a hardware
implementation. If you want algorithm replaceability and performance,
you can implement encryption using reconfigurable hardware, such as
FPGAs. Depending on the complexity of the algorithm, it may be possible
to implement the entire algorithm using FPGAs or something similar, or
you can use them to speed up some critical steps.
You can argue that in some applications, you may need to have very high
encryption throughput, such as encrypting sensitive data obtained by
remote sensors on board the satellite. But FPGA and hybrid FPGA/software
implementations are precluded as alternatives to multiple hardware
implementations only if the performance requirements are such that FPGAs
won't encrypt fast enough, and ASICs happen to. But even if that's true,
there are techniques to cut down the requirements on raw encryption
performance.
If you try hard enough, you might be able to find a set of assumptions
that would preclude reconfigurable hardware as a means to recover from
undiscovered algorithm weaknesses, but how theoretical do you want to
get?
If you rely on having multiple hardware algorithm implementations as a
recovery strategy, how do you choose what algorithms to include? How do
you deal with the possibility that a previously unknown cryptanalytic
technique will compromise entire classes of algorithms, including all of
the several you've chosen?
At this point, somebody may wonder how we're going to secure the
replacement algorithm against tampering. I'll just say it can be done
and it's not that hard. And it doesn't need to rely on crypto algorithms
of unknown strength.
> Having multiple ciphers as backups is almost certainly a good idea as long
> as they are all believed to be strong, and there is a way to securely tell
> the satellite to stop using a given cipher.
If you want to argue for a position by drawing on real-life examples, it
helps to verify that your premises are indeed true.
--
Nicol So, CISSP // paranoid 'at' engineer 'dot' com
Disclaimer: Views expressed here are casual comments and should
not be relied upon as the basis for decisions of consequence.
------------------------------
** 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
******************************
