Cryptography-Digest Digest #30, Volume #12 Wed, 14 Jun 00 21:13:01 EDT
Contents:
Re: On using compression as proper means of encryption (Mok-Kong Shen)
Re: On using compression as proper means of encryption (Mok-Kong Shen)
Re: On using compression as proper means of encryption (Mok-Kong Shen)
Another beginner question ("Cheri & Mike Jackmin")
Re: small subgroups in Blum Blum Shub (Mok-Kong Shen)
Re: Finding prime numbers (AllanW)
Re: Another beginner question (tomstd)
Re: On using compression as proper means of encryption (Tim Tyler)
Re: Can we say addicted? (Tim Tyler)
Re: Application specific SBoxes in Blowfish? (Andru Luvisi)
Re: Application specific SBoxes in Blowfish? (tomstd)
Re: Comments/analysis requested: stream cipher derived from hash function (SHA-1)
(Tim Tyler)
Re: Another beginner question (Andru Luvisi)
Re: Diffie's New directions in Cryptography (Paul Rubin)
Re: Digits of pi in Twofish (Vernon Schryver)
Re: On using compression as proper means of encryption ("Douglas A. Gwyn")
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On using compression as proper means of encryption
Date: Thu, 15 Jun 2000 01:24:53 +0200
[EMAIL PROTECTED] wrote:
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> > Use a PRNG (crypto strength unessential) with a key as
> > seed to generate a sequence of symbols (length of sequence
> > determined by PRNG) to initialize an adaptive Huffman
> > compression algorithm, taking care that all symbols of the
> > plaintext alphabet are input at least once. The output in
>
> How does the receiver know the Huffman table? I *think* the table is
> sent with the data in most applications, and unless a fixed table is
> used (ie, fixed for that application, not adaptive on input data) then
> the table needs to be sent along as well. Would you simply send the
> table over encrypted with some other form (PK, symmetric)? At that
> point, why not just send the regular table over encrypted with PK or
> symmetric?
It is symmetric cryptography. Both partners share a secret key. This
key is used as the seed of an agreed upon PRNG. The opponent
may know the PRNG but not the key. In the initialization phase the
PRNG generates a sequence of symbols to be input to the adaptive
Huffman algorithm. Thus the algorithm is in a certain state (i.e. it
obtains its internal table via the PRNG) when it starts to handle the
plaintext. That state can't be determined by the opponent since he
doesn't have the seed of the PRNG. There is never any table that is
transmitted from the sender to the receiver.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On using compression as proper means of encryption
Date: Thu, 15 Jun 2000 01:24:44 +0200
Anton Stiglic wrote:
> My I suggest something to you?
>
> You seem to have allot of ideas, which might be interesting,
> but the posts in which you express does ideas are very
> lengthy. Personally, I haven't read one of them because I
> don't want to spend that much time. It would be nice if
> you could go straight to the fact and express your ideas.
> If something is missing, someone will ask you.
Many thanks for your suggestion. I'll take heed to avoid
things that really could be cut. However, I am of the humble
opinion that presentation of motivations or some historical
backgrounds is just as essential for the majority of readers as
explanation of the bare and dry 'kernel' of an article. Anyway,
in journal publications it is commonplace to have an introduction
section illustrating why one wants to deal with a certain topic and
what has already been done on that, etc. etc. While I am aware
that there are certainly readers who desire very terse expositions,
I am afraid that others wouldn't see from a too short version what
it actually serves in the first place and consequently entirely neglect
it. I am extremely sorry if I continue to fail to gain you as my
esteemed reader.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On using compression as proper means of encryption
Date: Thu, 15 Jun 2000 01:25:05 +0200
"SCOTT19U.ZIP_GUY" wrote:
> Acatually it is an idea I propsed a long time ago and can be
> easily implmented using the 1-1 compression programs at my site,
> the "key" or "conditioning table" would be the contentents of
> the condition file. However even though it could be used for
> encryption if would be far better as a first pass before encryption.
> Since it is not "true" encryption you would need a much longer
> "key" or "condtion" file that would have to be kept secret than
> the short leys people commonly use for regular encryption.
Why is it not 'true' encryption? Could you please elaborate on
that? In fact it IS my point that compression can serve as 'true'
encryption. You could at most argue it is weaker than some well-
known block ciphers and hence need a bit longer keys to provide
comparable strength. But even that argument has to be substantiated
and I don't yet see how the argument is going to be. Now you
apparently used a fairly big file (long key) to do your 'conditioning'
and have consequently the disadvantage of management (keeping
that big file and having it shared by the partner). I use instead a
PRNG (to achieve the same effect that the big file does) and need
only a single short key comparable to the common block ciphers.
That could well make an essential difference in practice. (A short
session key can be readily and securely transmitted, while a big file
poses problems in that.) Further, using a PRNG allows dynamic
injection of random bits into the resulting stream, which, as I pointed
out, can substantially enhance the strength of the scheme.
M. K. Shen
------------------------------
From: "Cheri & Mike Jackmin" <[EMAIL PROTECTED]>
Subject: Another beginner question
Date: Wed, 14 Jun 2000 19:25:18 -0400
Consider a simple cipher in which SHA-1 (or a similar message digest)
was used to generate a series of key blocks from the preceding
ciphertext. How would this cipher be vulnerable?
For example, suppose I want to encrypt a message of arbitrary length.
I take user's the password, run it through SHA-1 to produce a 128 bit
key, and XOR this key against the first 128 bits of the message to
produce my first block of ciphertext. I then take this block of
ciphertext, run it through SHA-1 to generate my next 128 bits of key,
and so on.
Since I have never heard of this method being used, I have to assume
it has some sort of weakness which renders it unsuitable.
This approach is appealing because it would be so easy to implement
and to test, but the primary reason for my question is just a nagging
curiosity; I honestly can't even guess as to why this method wouldn't
be secure, but I'm sure you folks could spot the flaw right away.
Thanks
Michael Jackmin
Software Developer
RP Solutions, Inc.
(607) 257-7778
PGP Public Key ID: 0x14D84603 Size: 2048/1024 DH/DSS
(4A4E CB75 C4A4 2585 D953 D855 FA9F 0D98 14D8 4603)
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: small subgroups in Blum Blum Shub
Date: Thu, 15 Jun 2000 01:33:38 +0200
[EMAIL PROTECTED] wrote:
> Another question --- When playing around with Blum Blum Shub, using
> small primes, I noticed very short cycles before repetition.
The issue was discussed in the group some time back. You may like
to read Terry Ritter's article:
http://www.io.com/~ritter/ARTS/CRNG2ART.HTML
M. K. Shen
------------------------------
From: AllanW <[EMAIL PROTECTED]>
Subject: Re: Finding prime numbers
Date: Wed, 14 Jun 2000 23:18:18 GMT
> AllanW <[EMAIL PROTECTED]> wrote:
> > I suppose that's true. But it's unlikely on it's face. Finding
> > prime factors without knowing the primes would seem to be like
> > guessing how to spell a word without knowing the alphabet.
Bob Silverman <[EMAIL PROTECTED]> wrote:
> Do us a favor. Go read about the subject before making any
> further "guesses". Read Knuth Vol 2.
>
> Modern factoring algorithms do not do trial division.
> Further, even if one *did* do it that way, it is not necessary
> to compute *any* primes. Instead, one would construct a (say)
> 8-spoke or 48 spoke (or larger) wheel and divide by all integers
> on the wheel.
>
> For example: the numbers less than 30 and co-prime to it are:
> 1,7,11,13,17,19,23,29. One uses this to construct a sequence of
> integers co-prime to 2,3 and 5 and uses *this* sequence as candidates
> for trial division. One trial divides with some composites, but so
> what? Try to trial divide only by primes is SLOWER than allowing some
> composites in the sequence. You can extend the wheel to include the
> primes 7,11,13 etc. The pre-computation is small. The only constraint
> is storage.
I'm not familiar with the names "wheel" and "spoke." But I did
discover on my own a technique that closely matches what you've
described, so I'm reasonably sure that it is the same thing.
The point of an 8-spoke wheel, then, is to avoid candidate
primes (or in your case, candidate factors) which are
multiples of 2, 3, or 5. You expressed these values as
1,7,11,13,17,19,23,29
but I've been using
6,4,2,4,2,4,6,2
which I'm sure you recognize as the delta values, starting one
position further down your wheel.
Taking this further, a 48-spoke wheel would contain primes
less than 2*3*5*7=210, and would avoid multiples of 2, 3, 5,
or 7. Or going much further, a 92160-spoke wheel would
contain primes less than 2*3*5*7*11*13*17=510510, and would
avoid multiples of 2, 3, 5, 7, 11, 13, or 17.
> But trying to break an RSA key by trial division is worse
> than hopeless.
If you want to know if a number is prime or composite, finding
a factor quickly is more important than finding prime factors.
As I understood it, though, the public key and private key were
both created from a simple formula with two prime numbers. So
we don't just want to find a factor, we want to find prime
factors. Or I suppose you could go by HOW MANY factors you
find; three or more factors means that we haven't got the
public/private keypair. Still, a simple declaration that the
number isn't prime is not complete.
If I'm wrong about this, please tell me; I'll eagerly study
any feedback you can give me. After all, isn't sci.crypt
precisely the forum to ask such questions? Or have I somehow
insulted your intelligence by asking too simple of a question?
--
[EMAIL PROTECTED] is a "Spam Magnet," never read.
Please reply in newsgroups only, sorry.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Subject: Re: Another beginner question
From: tomstd <[EMAIL PROTECTED]>
Date: Wed, 14 Jun 2000 16:36:56 -0700
In article <[EMAIL PROTECTED]>, "Cheri & Mike
Jackmin" <[EMAIL PROTECTED]> wrote:
>
>Consider a simple cipher in which SHA-1 (or a similar message
digest)
>was used to generate a series of key blocks from the preceding
>ciphertext. How would this cipher be vulnerable?
>
>For example, suppose I want to encrypt a message of arbitrary
length.
>I take user's the password, run it through SHA-1 to produce a
128 bit
>key, and XOR this key against the first 128 bits of the message
to
>produce my first block of ciphertext. I then take this block of
>ciphertext, run it through SHA-1 to generate my next 128 bits
of key,
>and so on.
Well if I have a block of ciphertext I can find the rest of the
plaintexts... For example
K = 128 bit key
P1 = plaintext
C1 = P1 xor H(K)
K = C1
repeat as required...
I just need C1 now to find P2 from C2..
Tom
* 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: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: On using compression as proper means of encryption
Reply-To: [EMAIL PROTECTED]
Date: Wed, 14 Jun 2000 23:02:52 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
: I like therefore to describe in the following a concrete
: encryption scheme based on compression:
IMO, "concrete" would be providing pseudocode, that lets somebody
construct an implementation of your cypher - or working code.
: Use a PRNG (crypto strength unessential) with a key as
: seed to generate a sequence of symbols (length of sequence
: determined by PRNG) to initialize an adaptive Huffman
: compression algorithm, taking care that all symbols of the
: plaintext alphabet are input at least once. The output in
: this initialization phase is discarded. Then start feeding
: symbols of the plaintext into the algorithm. Use the result
: as ciphertext. Decryption amounts to a corresponding
: decompression after doing the same initialization.
: The security of the scheme is based on the fact that the
: opponent has no knowledge of the state of the compression
: algorithm at completion of the initialization phase.
Um - have you actually done this?
I can't think why it might be strong.
Try encrypting a big file of zeros using this technique :-(
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Be good, do good.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Can we say addicted?
Reply-To: [EMAIL PROTECTED]
Date: Wed, 14 Jun 2000 23:09:53 GMT
Anton Stiglic <[EMAIL PROTECTED]> wrote:
:> Mike Rosing <[EMAIL PROTECTED]> wrote:
:> : http://www.terracom.net/~eresrch/float/rho3.png [...]
: Yeark, a microsoft application url?
What, a PNG?
Portable Network Graphics: http://sunhe.jinr.dubna.su/docs/w3c/Graphics/PNG/
If you've been asked if you are sure you want to run this program, that's
probably because your browser's having a brain-dead day.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Breast is best.
------------------------------
From: Andru Luvisi <[EMAIL PROTECTED]>
Subject: Re: Application specific SBoxes in Blowfish?
Date: 14 Jun 2000 16:48:11 -0700
"Sam Simpson" <[EMAIL PROTECTED]> writes:
[snip]
> My aim is to have a new version of Blowfish totally incompatible with
> existing implementations....
[snip]
I wouldn't expect that there would be any problems, but why?
If I had the choice of buying something compatible with other
implementations, or something which would lock me into working with
other products from a particular vendor, I would choose the compatible
option any day. I doubt I'm the only one who feels this way. Why
would you want to alienate us?
Andru
--
==========================================================================
| Andru Luvisi | http://libweb.sonoma.edu/ |
| Programmer/Analyst | Library Resources Online |
| Ruben Salazar Library |-----------------------------------------|
| Sonoma State University | http://www.belleprovence.com/ |
| [EMAIL PROTECTED] | Textile imports from Provence, France |
==========================================================================
------------------------------
Subject: Re: Application specific SBoxes in Blowfish?
From: tomstd <[EMAIL PROTECTED]>
Date: Wed, 14 Jun 2000 17:05:37 -0700
In article <[EMAIL PROTECTED]>, Andru Luvisi
<[EMAIL PROTECTED]> wrote:
>"Sam Simpson" <[EMAIL PROTECTED]> writes:
>[snip]
>> My aim is to have a new version of Blowfish totally
incompatible with
>> existing implementations....
>[snip]
>
>I wouldn't expect that there would be any problems, but why?
>
>If I had the choice of buying something compatible with other
>implementations, or something which would lock me into working
with
>other products from a particular vendor, I would choose the
compatible
>option any day. I doubt I'm the only one who feels this way.
Why
>would you want to alienate us?
If you want to use a "Brand X" version of Cipher Y, then you are
unique. Sometimes you can hype this. If for example you
are ... um Microsoft and you take Blowfish. Well you change pi
to e and call it MicroBlow, Got your own cipher :)
I don't think it's a good idea simply because you would have to
ensure that all Brand X'es are secure...
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
Crossposted-To: sci.crypt.random-numbers
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Comments/analysis requested: stream cipher derived from hash function
(SHA-1)
Reply-To: [EMAIL PROTECTED]
Date: Wed, 14 Jun 2000 23:35:07 GMT
In sci.crypt.random-numbers Lon Willett <[EMAIL PROTECTED]> wrote:
Some humble observations.
: The point of this construction is to use it as the basis of a PRNG, with
: backtracking attacks algorithmically prevented. Other stream ciphers that
: I'm aware of don't have the property that they can't be run "in reverse".
I find the ideas behind constructing PRNGs which cannot be run backwards
very interesting.
I don't believe it's considered so important in a PRNG for use as a stream
cypher as for some other uses - e.g. key generation.
: The simple stream cipher description is:
[snip]
: Iterative step (generate the next N bits of output):
: Output[i] = S1[i] xor S2[i]
: S1[i+1] = hash(S1[i]: S2[i])
: S2[i+1] = hash(S2[i]: S1[i])
There's no guaranteed minumum period - consequently there's a chance of
short cycles and weak keys.
Also, I have a concern relating to irreversibility. Hash functions - by
their nature - map more than one input to the same output. This has the
effect of losing information present in the seed. Iterating such a
procedure may cause gradual "entropy drainage" from the internal state -
and significantly reduce the eventual expected cycle size.
I'm not certain if this is important - but I'm pretty sure it can be
avoided:
An alternative strategy that makes runnung the generator backwards
difficult, but retains a bijective property that ensures no entropy from
the seed is destroyed involves the use of a public key encryption
algorithm. A public key is generated, and the private key is
*destroyed*. The internal state of the generator is regularly encrypted
with the public key. Since the private key is not available, the
generator can't be run backwards - without determining what the private
key is.
If this step is performed frequenty, it will have a significant speed
penalty.
Also - following the maxim that no component of your RNG that could
be varied should remain fixed, the public key may need occasional
refreshment - a process that is likely to be *extremely* slow.
: Other RNGs seem to assume that enough entropy can be collected before
: they remix their pools to prevent backtracking attacks. I would like
: to make backtracking attacks "hard", even in the absence of any new
: entropy, and this seems to be the simplest way of doing it.
This seems a desirable goal - but I'm not sure how important is is in
practice. Occasional reseeding may be sufficient to prevent /most/
back-tracking opportunities. If there's expense involved in making sure
backtracking even a single step is impossible, it may not be worth it.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ VIPAR GAMMA GUPPY.
------------------------------
From: Andru Luvisi <[EMAIL PROTECTED]>
Subject: Re: Another beginner question
Date: 14 Jun 2000 17:21:57 -0700
"Cheri & Mike Jackmin" <[EMAIL PROTECTED]> writes:
[snip]
> For example, suppose I want to encrypt a message of arbitrary length.
> I take user's the password, run it through SHA-1 to produce a 128 bit
> key, and XOR this key against the first 128 bits of the message to
> produce my first block of ciphertext. I then take this block of
> ciphertext, run it through SHA-1 to generate my next 128 bits of key,
> and so on.
[snip]
This isn't so good, but with a teeny modification it becomes Output
Feedback Mode, and is just fine.
In this context, + means concatination.
IV is a random initialization vector.
Pad_0 = Ciphertext_0 = IV
Pad_i = Hash(key + Pad_{i-1})
Plaintext_1 is the first block of plaintext.
Ciphertext_i = Plaintext_i XOR Pad_i
Andru
--
==========================================================================
| Andru Luvisi | http://libweb.sonoma.edu/ |
| Programmer/Analyst | Library Resources Online |
| Ruben Salazar Library |-----------------------------------------|
| Sonoma State University | http://www.belleprovence.com/ |
| [EMAIL PROTECTED] | Textile imports from Provence, France |
==========================================================================
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Diffie's New directions in Cryptography
Date: 15 Jun 2000 00:45:51 GMT
In article <8i8d24$4dd$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
>Hi,
> From where will I get an online copy of the original "New directions
>in cryptography" by Diffie and Hellmann?
>
>Here is a description of the paper
>�New directions in cryptography�,
>IEEE Transactions on Information Theory, 22
>(1976), the IEEE 22nd Annual Symposium on Foun-dations
>of Computer Science,
>
>Thank you in advance,
>Vijil
It's reprinted in "Contemporary Cryptology" (IEEE Press, edited by
Gus Simmons) and in many other places too. It's a classic paper, well
worth reading.
------------------------------
From: [EMAIL PROTECTED] (Vernon Schryver)
Subject: Re: Digits of pi in Twofish
Date: 14 Jun 2000 18:27:15 -0600
SHEESH!--I can't take it any longer.
An unjustified belief in the safety, sanctity, or other wonderfulness of
digits of pi or of the golden mean is no less of a groundless superstition
than unjustified suspicion of evil intent in the choice of any other
constant. If some constants are more suitable than others, then why would
you expect arbitrary digits to among the good choices intead of the bad?
Isn't one the mantras of this newsgroup that arbitrary DES S-boxes are
likely to be worse?
It's not as if there are two parties, one picking constants and the other
picking cyphers. If you assume the cypher designer is evil, then you
cannot assume the choice of the constant and how the cypher uses it are
independent. If the cypher designer can cheat by picking a naughty
constant with an innocent cypher, then the designer can also cheat by
picking an innocent constant with a naughty cypher.
Can you not think of an "obvious," apparently "innocent" way to derive
weak DES S-boxes or any other naughty value you need from the first digits
of pi? What if you pick the first bunch of digits of pi starting after
the 10th, 100th, 1000th, or some other "obvious" and "innocent" starting
digit? If you were naughty and needed a trap-door constant for your evil
cypher, do you really think you could not find it somewhere among the
digits of the golden mean, pi, e, the speed of light, and the many other
"innocent" constants an educated person has had to memorize by age 25?
Never mind which constants are normal in some base of your evil choosing,
or creativity in apparently arbitrary choices in how you convert those
digits into binary numbers or gates.
Digits of e, pi or the golden mean are fine when you need an arbitrary
irrational or transcendental number or string of digits and have no reason
to choose any other digits. (As Knuth says, the golden mean is cool for
multipicative hash functions.) On the other hand, believing the choice
of one of those automatically confers any virtue on a cypher is silly.
Absent explicit weaknesses, a rational person accepts "the birthdays of
my parents and grandparents" or "my favorite number today" as readily as
"pi because it's pi." Never mind overriding explanations such as
"I looked at the mixing for 1000 other numbers, but I prefer this one."
Vernon Schryver [EMAIL PROTECTED]
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: On using compression as proper means of encryption
Date: Thu, 15 Jun 2000 01:03:56 GMT
Here is a compromise suggestion: When initiating a new topic,
start by stating the theme without any historical or technical
elaboration, then skip a line and begin to elaborate. E.g.
Has anybody looked into the connection between Good transforms
and Fast Fourier transforms?
The Good transform was invented ...
The trick that both transforms use to short-cut computation ...
------------------------------
** 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
******************************
