Cryptography-Digest Digest #746, Volume #10 Wed, 15 Dec 99 18:13:01 EST
Contents:
Re: Non-linear PRNGs (Mok-Kong Shen)
Re: Non-linear PRNGs (Mok-Kong Shen)
Re: Non-linear PRNGs (Mok-Kong Shen)
Re: discrete logorithm reduction to factoring ("Roger Schlafly")
Re: Non-linear PRNGs (John Savard)
Re: Skytale? (John Savard)
Re: Prime series instead (Re: Pi) (Erik Max Francis)
Re: Deciphering without knowing the algorithm? (Paul Koning)
which is safer for creating session keys (Tom St Denis)
Re: The Code Book (Jim Reeds)
Re: how easy would this encryption be to crack? (Frank Gifford)
Re: discrete logorithm reduction to factoring (Scott Fluhrer)
Re: how easy would this encryption be to crack? (Jerry Coffin)
Off topic -- 4 year old (Sukhoi2000)
Re: Simple newbie crypto algorithmn ([EMAIL PROTECTED])
Re: Better encryption? PGP or Blowfish? (SCOTT19U.ZIP_GUY)
Re: security of 3des ?= des (Paul Schlyter)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Non-linear PRNGs
Date: Wed, 15 Dec 1999 19:44:52 +0100
Tim Tyler wrote:
>
> The BBS PRNG derives its security from the difficulty of
> factoring the modulus into its large prime factors.
>
> The generator described at this thread's head has a modulus of 2^m -
> and multiplying primes together is not even mentioned.
I don't think that all cryptologically good PRNG must follow the
line of BBS. If the cofficients of the polynomial can be shown to
be hard to infer and the bits are statitically good,then one has a
serious candidate of use in applications. Note that BBS takes
only 1 bit from each number generated. The present scheme is
intended, as far as I understand, to use all 32 bits (assuming 32
bit word size). Now one can take the parity of the 32 bits, i.e.
obtaining only 1 bit from each number generated. In this case I am
not quite sure that the present scheme does not offer quite high
security. (Anyway I am not yet aware of any work on analsis about
parity bit sequences.)
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Non-linear PRNGs
Date: Wed, 15 Dec 1999 19:44:22 +0100
Tim Tyler wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> : Let f(x) = a_0 + a_1*x^(1) + a_2*x^(2) + ..... + a_n*x^(n)
> : where x^(k) = x(x-1)(x-2)...(x-k+1).
> : Then the generator u(i) = f(u(i-1)) mod 2^m (m>2) has period
> : 2^m if and only if the following congruences hold:
> : a_0 = 1 mod 2, a_1 = 1 mod 4, a_2 = 0 mod 2, a_3 = 0 mod 4.
>
> [...]
>
> : Question: Has anyone studied such PRNGs from cryptological point
> : of view? I surmise that they are extremely hard for analysis even
> : with moderate values of n.
>
> The reference I was thinking of was from RFC1750:
>
> Not only have linear congruent generators been broken, but techniques
> are now known for breaking all polynomial congruent generators
> [KRAWCZYK].
>
> [KRAWCZYK]: How to Predict Congruential Generators, Journal
> of Algorithms, V. 13, N. 4, December 1992, H. Krawczyk.
>
> http://www.cis.ohio-state.edu/htbin/rfc/rfc1750.html
> http://blitzen.canberra.edu.au/RFC/rfc/rfc1750.html
>
> I /believe/ the generator proposed above *is* simply a polynomial
> congruent generator - if you expand out the "^" operations into their
> component parts.
You don't have to /believe/. Isn't it at first look obvious to you
that f(x) IS polynomial? Isn't BBS based on a polynomial (a quadratic)
and hence according to the above broken?
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Non-linear PRNGs
Date: Wed, 15 Dec 1999 19:44:38 +0100
John Savard worte:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote, in part:
>
> >Question: Has anyone studied such PRNGs from cryptological point
> >of view? I surmise that they are extremely hard for analysis even
> >with moderate values of n.
>
> One thing is clear: the Blum-Blum-Shub algorithm, regarded as secure,
> is closely related to this.
I have only poor knowledge of BBS, hence a question: What can be said
of the period of BBS in general? (Would the period be dependent on
the choice of the seed?) Thanks in advance.
M. K. Shen
------------------------------
From: "Roger Schlafly" <[EMAIL PROTECTED]>
Crossposted-To: comp.theory
Subject: Re: discrete logorithm reduction to factoring
Date: Wed, 15 Dec 1999 10:07:52 -0800
<[EMAIL PROTECTED]> wrote in message
news:8373h1$7vb$[EMAIL PROTECTED]...
> Is it true that discrete log reduces to factoring ?
Unknown. All we know is that known techniques for factoring
have analogous techniques for discrete logs, and vice versa.
The asymptotics are similar, but in the range of cryptographic
interest the discrete log implementations are a lot more
difficult than factoring.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Non-linear PRNGs
Date: Wed, 15 Dec 1999 12:27:41 GMT
Tim Tyler <[EMAIL PROTECTED]> wrote, in part:
>I'd say any notion that the security of BBS also applied
>to the generator described here was /extremely/ premature.
That may be. The generators are related - since they both involve
taking a multiple of the square of the seed - but a mathematical
connection between two generators doesn't automatically imply they
have the same security, I certainly admit.
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Skytale?
Date: Wed, 15 Dec 1999 12:26:02 GMT
John Bottoms <[EMAIL PROTECTED]> wrote, in part:
>The Roman rulers used a skytale to encrypt messages by
>wrapping a strip of cloth around a rod.
Actually, the skytale was used by the Spartans in ancient Greece.
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Erik Max Francis <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Prime series instead (Re: Pi)
Date: Wed, 15 Dec 1999 11:57:34 -0800
Matthew Montchalin wrote:
> Is there any practical value to the number derived from using primes
> instead of odds in that formula? E.g.,
>
> N = 4(1 - 1/3 + 1/5 - 1/7 + 1/11 - 1/13 + 1/17 ... )
You forgot one.
--
Erik Max Francis | icq 16063900 | email [EMAIL PROTECTED]
Alcyone Systems | web http://www.alcyone.com/max/
San Jose, CA | languages en, eo | icbm 37 20 07 N 121 53 38 W
USA | 383 days left | &tSftDotIotE
__
/ \ The death rate is a constant one hundred per cent.
\__/ Camden Benares
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: Deciphering without knowing the algorithm?
Date: Wed, 15 Dec 1999 14:54:57 -0500
CLSV wrote:
> ...
> Not all of "the best cryptoheads in the world" live in the US.
Probably not even a majority...
> Furthermore as I understand it the US export regulations are only
> valid for binaries. You still may export knowledge.
Not necessarily, believe it or not. "Technical data" is also
subject to control. If you're talking about textbooks, or
things like that, then you're right; if not, then you may not be.
> And that is
> what happens on this newsgroup.
Some of the time... :-(
paul
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: which is safer for creating session keys
Date: Wed, 15 Dec 1999 20:10:34 GMT
Which is safer hashing KEY+SALT or SALT+KEY? I meant the actual order
in which the data is stored. [or does it matter at all]. I am using
SHA-1 as the hash btw.
I ask this because I have been fiddling with Peekboo which uses
KEY+SALT format, and I wonder if that is ok. Normally if KEY+SALT were
under 256 bits it wouldn't matter with sha since it expands them with
thourough mixing, however in peekboo I hash the hexidecimal copy of
both so it's actually 576 bits of data being hashed.
Any thoughts?
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Jim Reeds)
Subject: Re: The Code Book
Date: Wed, 15 Dec 1999 20:16:31 GMT
In article <[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> writes:
|> In response to my own post:
|>
|> About half of the perpetual calendars I've found on the web give 15
|> October 1586 as a Saturday, as I also found with the Unix 'cal' that came
|> with my SuSE Linux 6.1. Other sites list the day as a Wednesday.
|>
|> Most Julian day calculators on the give 15 October 1586 as JD 2300622 (one
|> gave JD 2300620). Today, Wednesday, 15 December 1999 is JD 2451528, 150906
|> days since that date, or exactly 21558 weeks since then.
|>
|> So it seems that it probably was a Wednesday that Queen Mary first
|> appeared in court.
|>
|> Warner <[EMAIL PROTECTED]> wrote:
|> > The first sentence of Simon Singh's _The Code Book_ is, "On the morning of
|> > Wednesday, 15 October 1586, Queen Mary entered the crowded courtroom of
|> > Fotheringhay Castle". The calendars I have referred to give this date as
|> > being on a Saturday. I'm interested in hearing comments on this apparent
|> > inconsistency or references to such.
|>
|> > --
Things are even murkier than we thought: the date usually
ascribed for the trial's begining is 14 October 1586.
(References: the on-line edition of the Catholic Encylopedia
and an attorney's list of this-day-in-history events,
http://www.donaldburger.com/october.htm )
No amount of consulting computer programs will really
settle the matter of when the trial began, but an hour in
the public library might.
Everyone knows that only in the Gregorian calendar was 15
October 1586 a Wednesday, and that the Gregorian calendar
was adopted in England only on Thursday 14 September 1752:
the previous day, Wednesday 2 September 1752 was the
last one they used the Julian calendar. Many people also
know that the day-of-the-week situation and the leap-year
situation come back into mesh in the Gregorian calendar every
400 years, so Gregorian 15 October 1586 fell on the same
day of the week as Gregorian 15 October 1986. And, many
people also know that location of the trial, Fotheringhay
Castle, is in England (in Northamptonshire).
--
Jim Reeds, AT&T Labs - Research
Shannon Laboratory, Room C229, Building 103
180 Park Avenue, Florham Park, NJ 07932-0971, USA
[EMAIL PROTECTED], phone: +1 973 360 8414, fax: +1 973 360 8178
------------------------------
From: [EMAIL PROTECTED] (Frank Gifford)
Subject: Re: how easy would this encryption be to crack?
Date: 15 Dec 1999 15:59:28 -0500
In article <[EMAIL PROTECTED]>,
Christoffer =?iso-8859-1?Q?Lern=F6?= <[EMAIL PROTECTED]> wrote:
>Jerry Coffin wrote:
>> Against a threat-model like known-plaintext or chosen-plaintext, this
>> provides essentially no security at all -- once the text you've
>> encrypted is just over double the effective key length, the repetition
>> of the key is obvious.
>...
>So, I did a slight variation, basically introducing another variable just
>counting the position and rotating the bits after the first xor (see my
>other mailing), I was hoping the rotation would hide the byte used to
>xor the paintext. I don't know if this hides the key (the rotation depends
>on one of the keys as can be seen in the algorithm) sufficiently - at
>least xor:ing with byte sequence gotten from sending zeroes as a
>plaintext attack won't work.
>...
>Try this:
>plaintext 14 zeroes gives
>A0 3D 18 C1 E6 40 8E 5F 0C F7 D7 9D 4A 7A
>a simple ascii message (14 characters):
>32 1D 30 F4 EE 68 AE 1A 76 A4 87 35 05 D2
>keys are 11 & 7 bytes long
>
>How easy is this to decipher?
"I AM A TOMATOE"
-Giff
--
Too busy for a .sig
------------------------------
From: Scott Fluhrer <[EMAIL PROTECTED]>
Subject: Re: discrete logorithm reduction to factoring
Date: Wed, 15 Dec 1999 21:06:39 GMT
In article <[EMAIL PROTECTED]>,
"Roger Schlafly" <[EMAIL PROTECTED]> wrote:
><[EMAIL PROTECTED]> wrote in message
>news:8373h1$7vb$[EMAIL PROTECTED]...
>> Is it true that discrete log reduces to factoring ?
>
>Unknown. All we know is that known techniques for factoring
>have analogous techniques for discrete logs, and vice versa.
I thought that the Elliptic Curve Method of factoring had no
known analogous technique for discrete log -- was there a result
I missed?
--
poncho
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: how easy would this encryption be to crack?
Date: Wed, 15 Dec 1999 14:23:36 -0700
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
[ ... ]
> So, I did a slight variation, basically introducing another variable just
> counting the position and rotating the bits after the first xor (see my
> other mailing), I was hoping the rotation would hide the byte used to
> xor the paintext. I don't know if this hides the key (the rotation depends
> on one of the keys as can be seen in the algorithm) sufficiently - at
> least xor:ing with byte sequence gotten from sending zeroes as a
> plaintext attack won't work.
You're still eventually going to get repetition. Ultimately, you can
do all sorts of things to put more key bytes to use, and end up
stretching the effective key length each time you do so.
Unfortunately, you're starting with a basic method that's weak enough
that you've got to stretch the effective key length to (roughly) the
length of the message before it's going to do much good. While I was
only pointing out really simple attacks that render the basic method
too weak to be of much use, Jim Gillogly pointed out that a more
skilled cryptanalyst can mount an attack with only about as much
enciphered text as the total number of bytes in the key. Your keyed
rotation may help some (I haven't tried to analyze it) but unless it's
more sophisticated than I expect, I don't think it's really going to
do a lot of good.
The basic fact is, that as long as you're doing a byte-for-byte
substitution, you're almost certain to end up with a relatively weak
algorithm. If you're willing to use _enough_ key, you can make even a
weak cipher difficult to attack, but right now you're doing very
little to make effective use of the amount of key material you're
using.
> Try this:
> plaintext 14 zeroes gives
> A0 3D 18 C1 E6 40 8E 5F 0C F7 D7 9D 4A 7A
> a simple ascii message (14 characters):
> 32 1D 30 F4 EE 68 AE 1A 76 A4 87 35 05 D2
> keys are 11 & 7 bytes long
>
> How easy is this to decipher?
As long as the total amount of key material is greater than the total
amount of text being enciphered, it certainly _ought_ to be quite
strong. After all, it's easy to prove that an even simpler algorithm
is 100% secure against breakage when the key is as large as the text
be enciphered, as long as the key is carefully enough chosen.
The problem is that right now, you're using 18 bytes of key, which is
a 144-bit key. A 144-bit key is large enough that if you make even
fairly reasonable use of it, that security shouldn't be a problem
regardless of the amount of text you encrypt, even against MUCH more
sophisticated attacks than those I've mentioned in this thread.
At the very least, to strengthen the algorithm, my first piece of
advice would be to try to have each bit of the input affect more than
one bit of the output. Your rotation helps to make it less obvious
which bits of input are related to which bits of output, but unless
I'm missing something, it's still a one-to-one relationship between
the two.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: [EMAIL PROTECTED] (Sukhoi2000)
Subject: Off topic -- 4 year old
Date: 15 Dec 1999 21:34:13 GMT
It is the little things in life that mean so much. If you can, please have
everyone you know send a Christmas card to:
Miss Paige Lane
4538 S. Creek Rd.
Cookeville, TN 38506-7606
She is 4 years old and is dying from cancer, and the only thing she wants for
Christmas is cards.
Thanks.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Simple newbie crypto algorithmn
Date: Wed, 15 Dec 1999 21:39:05 GMT
In article <[EMAIL PROTECTED]>,
Steven Siew <[EMAIL PROTECTED]> wrote:
>
> If you think there is something wrong with my algorithmn security
> wise, tell me so that I can improve on it.
>
> Steven Siew
>
You are asking for free cryptanalysis with no reward. Proving that
your method is insecure would mean spending a lot of time to reach a
conclusion that most readers of your post would immediately suspect --
that you are perhaps a little too keen on your skills for your own good.
I'm not suggesting that you are an idiot, but rather that you assume
the rest of the world to be.
Perhaps if you posted your bank account numbers encrypted with your
method, you might see more interest.
--
Gregor B. Dramkin
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Better encryption? PGP or Blowfish?
Date: Wed, 15 Dec 1999 23:02:54 GMT
In article <[EMAIL PROTECTED]>, James Felling
<[EMAIL PROTECTED]> wrote:
>
>
>"SCOTT19U.ZIP_GUY" wrote:
>
>> In article <8375uj$9ik$[EMAIL PROTECTED]>, molypoly <[EMAIL PROTECTED]>
> wrote:
>> > Ok, I'm a 'newbie' and am trying to understand this. With a "zero
>> >information system" such as PGP, one can easily read the encrypted
>> >file.
>> All a ZERO INFORMATION system means is that if someone
>> has the time all the information needed to break the system is
>> there. Zero additional information is needed to break the system.
>> PGP is such a system. People who compress with bad compression
>> and then use standard emcryption also may fall into this group.
>
>>
>> > If you are using PcCrypto, where the passphrase is not stored
>> >ANYWHERE, then one cannot read the encrypted file. Am I getting this?
>> > Thanks in advance.
>> >
>> I don't know much about PcCrypto. But if it is not a ZERO Knowledge
>> type of encryption then the attacker needs addtional information to break
>> the system. In short even if your message is 1000 times longer than
>> your key. If the person had all the time in the Universe he still with out
>> additional information can not break you system since he would not
>> know the soultion even if he found it. However if the attacker knows
>> additional information such as your an English speaker and there is
>> some high propabilty that you used MSWORD to write a English
>> text then he may use that information to guess a soultion if such a
>> solution exists in the solution space. But in a ZERO information
>> system like PGP given enough time you can with 100% accuracy
>> get the solution to the encrypted file with out any outside information
>> this is something new people to crypto do not undestand.
>>
>> David A. Scott
>
>Alright I am really confused now. I do not understand your terms, much less
> the
>point being driven at. I had thought I did, but it seems that based on this
> posting
>I did not/
>
>What is a Zero information system( as you use the term)?
>
>What is a Zero Knowledge system(as you use the term)?
I am not the best writter in the world. I think we where talking about
a ZERO INFORMATION system. LIke PGP all the information about the
system is out in the open. If one can break RSA you have the anwser to
what is encrypted and you need zero more information to prove you have
the exact soution.
A system this is not a ZERO INFORMATION system is like if you discover
I am always sending 1 of four messages one of the messages is
1) lets go nuke china tomorrow
2)lets surrender to china today
3)lets not do anthing at all
4)lets try to team up with russia
If you know that is all I am sending you still not know what I sent if you
receive a message that only decrypts to these 4 choces you need more
information.
>
>Could you also give examples for each of a system which is one, and an example
> of a
>system which is not?
>
>Thanks.
>
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***
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: security of 3des ?= des
Date: 15 Dec 1999 22:23:21 +0100
In article <83854m$[EMAIL PROTECTED]>,
Frank Gifford <[EMAIL PROTECTED]> wrote:
> In article <[EMAIL PROTECTED]>, Tim Tyler <[EMAIL PROTECTED]> wrote:
>> karl malbrain <[EMAIL PROTECTED]> wrote:
>>: <[EMAIL PROTECTED]> wrote in message
>>
>>:> i was wondering if it has been shown that 3des is more secure
>>:> than des.
>>:>
>>:> my understanding is that if des transformations form a group
>>:> than any composition of des transformations is equivalent to
>>:> a single des encryption,
>>
>>: In the sense that DES is a 64 bit block function that MAPS one input to one
>>: output, yes, you can combine DES operations as a single MAPPING, and there
>>: is no security gain. [...]
>>
>> However you look at it, it's been proven not to be true that any
>> composition of DES transformations is equivalent to a single DES
>> encryption.
>
> Well, you should be clear here. It's true that since DES is not a group,
> that 3-DES cannot be reduced to 1-DES. But that does not imply that it
> is impossible for some (plaintext1, key1, ciphertext1) tupple in N-DES to
> be found as (plaintext1, key2, ciphertext1) in 1-DES.
On the contrary, it is impossible for this NOT to happen -- why?
Because in triple-DES there are 2^112 or 2^168 possible keys
(depending on whether you use a double-length or triple-length key),
but only 2^64 possible ciphertexts to any given plaintext. Thus, for
each given plaintext there must, on the average, be 2^48 or 2^104
different keys (depending on whether you use a double-length or
triple-length key) which produce any given ciphertext.
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: [EMAIL PROTECTED] [EMAIL PROTECTED] [EMAIL PROTECTED]
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
** 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
******************************
