Cryptography-Digest Digest #750, Volume #10      Thu, 16 Dec 99 17:13:00 EST

Contents:
  Q: BBS (Mok-Kong Shen)
  Re: Q: BBS (David A Molnar)
  Re: Deciphering without knowing the algorithm? (Paul Schlyter)
  Peekboo V2 (Tom St Denis)
  Not Quite Identity-Based RSA Variant (John Savard)
  Re: BBS ("Michael Scott")
  Re: Simple newbie crypto algorithmn (SCOTT19U.ZIP_GUY)
  Re: Deciphering without knowing the algorithm? (CLSV)
  Re: Deciphering without knowing the algorithm? ("Steve Feldman")
  More idiot "security problems" (Eric Lee Green)
  Re: Simple newbie crypto algorithmn (Johnny Bravo)
  Re: Q: BBS ("Baruch Even")
  Re: Q: BBS (Tim Tyler)
  Re: Deciphering without knowing the algorithm? (drickel)
  Re: Prime series instead (Re: Pi) (SDpikachu)
  Re: Q: BBS (Mok-Kong Shen)
  Re: Q: BBS (Mok-Kong Shen)
  Re: Invitation to our homepage (Keith A Monahan)
  Edgar Allan Poe Crypto Challenge. ("DM")

----------------------------------------------------------------------------

From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Q: BBS
Date: Thu, 16 Dec 1999 19:34:20 +0100

The present question stems from a follow-up of mine in another thread.

The interation underlying BBS:
 
    X_(i+1) = (x_i)^2  mod n 

ultimately cycles. From any seed X_0 there may be an initial
unrepeated segment in the sequence generated, but after that it 
goes into a loop. It is trivial to see the existence of such loops.
An element belonging to a loop of length 2 satisfies 

    x^4 = x  mod n 

Generally, an element belonging to a loop of length m satisfies

    x^(2^m) = x  mod n 

Question: Does this signify anything to the security offered by BBS?

M. K. Shen

------------------------------

From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Q: BBS
Date: 16 Dec 1999 18:43:33 GMT

Mok-Kong Shen <[EMAIL PROTECTED]> wrote:

> Question: Does this signify anything to the security offered by BBS?

Well, if you start over in a cycle, you will output the same bits, 
and this will be bad. So you should know how long the cycle is for your
particular instance of the generator. The last part of the BBS paper
covers methods for determining parameters which yield maximum-length
cycles. Terry Ritter also has an article in Cryptologia (?) and some 
discussion on his web page as to how to determine the cycle length
of given parameters.

It's an interesting kind of problem - if you implement a BBS in say,
Scheme, and keep iterating it, you can actually play with a lot of 
different parameters and notice that some work and some don't. and you can
notice that if n isn't a blum integer, then your least sig bit is not
particularly random at all...

-David


------------------------------

From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: Deciphering without knowing the algorithm?
Date: 16 Dec 1999 19:02:45 +0100

In article <[EMAIL PROTECTED]>, CLSV  <[EMAIL PROTECTED]> wrote:
 
> "SCOTT19U.ZIP_GUY" wrote:
> 
>> I know enough to know that you don't understand C "very"
>> well if you can't follow a simple C program. 
> 
> Have you ever seen the winners of the obfuscated C
> programming contest? Those are small and simple programs.
> Yet they are really hard to read.
 
These programs are far from typical small and simple C
programs.  The authors have deliberately abused C as much as
they can, in order to make the code as unreadable as possible
(that's what the contest is about).
 
-- 
================================================================
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

------------------------------

From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Peekboo V2
Date: Thu, 16 Dec 1999 19:09:32 GMT

Well V2 is out... some of the additions/changes include the chat
client, new layout, new session key construction, slightly easier to
follow source code etc..

In case you don't know, peekboo is my free Win95/98/NT Cryptographic
Toolset.

You can check it out on the web at

http://www.cell2000.net/security/peekboo/index.html

Tom


Sent via Deja.com http://www.deja.com/
Before you buy.

------------------------------

From: [EMAIL PROTECTED] (John Savard)
Subject: Not Quite Identity-Based RSA Variant
Date: Thu, 16 Dec 1999 12:29:38 GMT

It would seem that the security of RSA would not be decreased if,
after choosing one prime, I chose the second prime so that the
product, a very long number, began with a string giving my identity.

If so, I see a possible "benefit"; since the moduli starting with such
a string are a subset of possible moduli, there would be fewer
possible moduli having a given checksum.

Of course, that won't _really_ provide any benefit in security, at
least not one I can see - a restricted search for collisions will turn
up results as quickly as an unrestricted one, so key certificates
aren't improved. But perhaps there's some use...

John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm

------------------------------

From: "Michael Scott" <[EMAIL PROTECTED]>
Subject: Re: BBS
Date: Thu, 16 Dec 1999 19:54:07 -0000

I think that if a cycle can be found, then the modulus can be factored.

So the randomness, and non-cycling nature of the generator are both
predicated on the difficulty of factoring the modulus, and hence cycling
will not be a problem, assumuing factoring the modulus is difficult.

Mike Scott

Mok-Kong Shen <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> The present question stems from a follow-up of mine in another thread.
>
> The interation underlying BBS:
>
>     X_(i+1) = (x_i)^2  mod n
>
> ultimately cycles. From any seed X_0 there may be an initial
> unrepeated segment in the sequence generated, but after that it
> goes into a loop. It is trivial to see the existence of such loops.
> An element belonging to a loop of length 2 satisfies
>
>     x^4 = x  mod n
>
> Generally, an element belonging to a loop of length m satisfies
>
>     x^(2^m) = x  mod n
>
> Question: Does this signify anything to the security offered by BBS?
>
> M. K. Shen



------------------------------

From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Simple newbie crypto algorithmn
Date: Thu, 16 Dec 1999 20:51:54 GMT

In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Johnny Bravo) 
wrote:
>On Thu, 16 Dec 1999 14:57:51 GMT, [EMAIL PROTECTED] (Terry Ritter) wrote:
>
>>Certainly individuals can play it any way they want, but to imply that
>>Science is just too busy to address improvements in a cipher seems to
>>me to be an arrogant bridge too far. 
>
>  He is implying no such thing.  I'll relate an anecdote I've come
>across at some point (I forget where).
>
>"A beginner cipher designer creates a new system and takes it to a
>cryptanalyst he knows.  Doing the designer a favor he looks it over
>and points out a weakness after a few minutes.  Two days later he
>brings it back with that one weakness fixed, a few minutes later he
>finds another problem.  A few days later the designer comes back
>again.  After half an hour the cryptanalyst writes stuff on three
>pieces of paper and seals them in three envelopes and says "There are
>three breaks in your system all related to standard attacks on
>ciphers, you can have any one envelope, don't come back until you can
>tell me what is in the other two."
>
>  Sure, we are willing to look at new ideas, but if you want beginner
>level cryptanalysis on your cipher, do it yourself.  There is no

   What is this "WE" white man crap. From the quality of your posts
I would say it would be more of a favor for the beginning not to hear from
you since you don't seem to exhibit much knowledge of crypto in the
first place.


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: CLSV <[EMAIL PROTECTED]>
Subject: Re: Deciphering without knowing the algorithm?
Date: Thu, 16 Dec 1999 19:56:13 +0000

Paul Schlyter wrote:
 
> CLSV  <[EMAIL PROTECTED]> wrote:
 
> > "SCOTT19U.ZIP_GUY" wrote:

> >> I know enough to know that you don't understand C "very"
> >> well if you can't follow a simple C program.

> > Have you ever seen the winners of the obfuscated C
> > programming contest? Those are small and simple programs.
> > Yet they are really hard to read.
 
> These programs are far from typical small and simple C
> programs.

Well all entries are small and some do quite ordinary things
like calculating Pi or some prime numbers.

> The authors have deliberately abused C as much as
> they can, in order to make the code as unreadable as possible
> (that's what the contest is about).

I have to admit that my example was a bit over-the-top.
Nevertheless using C to present a crypto algorithm is not
really a good thing unless you can make it fit on one
80x25 page (uncompressed and unobfuscated).

Regards,

        CLSV

------------------------------

From: "Steve Feldman" <[EMAIL PROTECTED]>
Subject: Re: Deciphering without knowing the algorithm?
Date: Thu, 16 Dec 1999 14:11:00 -0600

Newbie here.   Go easy on me.

It it fact that NSA reads emails regularly?

I thought that something like triple DES was not feasibly crackable.
Besides, if I sent some mail or other transmission of multiple files,
binary, say, how would they have any idea that a given binary was encrypted
information as opposed to some binary data?

Another question - if something non-exportable like triple DES was used to
encrypt a file I send, should I expect NSA to come knocking on my door the
next day?

Increasingly curious about this fascinating subject,

Steve

>   Yes it is possible and it happens all the time. If one can recieve large
>amounts of traffic that appears to have a patteren one con run test to see
>what method was done. Fortunately for the NSA most mehtods in popular
>use broadcast what is being used. IF one used PGP the message would
>have PGP headers. Very few methods in popular use. Actually even bother
>with encrypting files that are not multiples of various lengths so even the
>file lengths give clues as to what system is being used.




------------------------------

From: Eric Lee Green <[EMAIL PROTECTED]>
Subject: More idiot "security problems"
Date: Thu, 16 Dec 1999 13:43:36 -0700

I'm beginning to get a good picture of which security consulting firms are
reputable and which are not. The reputable ones quietly do their jobs. The
disreputable ones issue press releases intended to scare people, such as the
"NSA Key" scare, or the current one, "Netscape EMAIL passwords insecure". 

http://www.cnn.com/1999/TECH/computing/12/16/netscape.crack.idg/index.html

Let's get this straight. Those passwords are sent across the network IN PLAIN
TEXT every time that the user logs into an IMAP or POP3 EMAIL server, and you
can  but this "security expert" at "Reliable Software Technologies Corp."
(hmm, is this a one-man outfit?) doesn't ever mention that, instead focusing
on how the keys are stored in the registry? 

So exploiting this requires physical access to the machine. But if an attacker
has physical access to the machine, he can just install Back Orifice and grab
your password that way! 

Seems to me this is yet another fake "scare" intended to rustle up business
for a "security consultant". The only real lesson to be learned is the obvious
one: Don't use the same password for your EMAIL that you use for your login! 

-- Eric Lee Green  http://members.tripod.com/e_l_green

------------------------------

From: [EMAIL PROTECTED] (Johnny Bravo)
Subject: Re: Simple newbie crypto algorithmn
Date: Thu, 16 Dec 1999 15:46:13 GMT

On Thu, 16 Dec 1999 20:51:54 GMT, [EMAIL PROTECTED]
(SCOTT19U.ZIP_GUY) wrote:

>   What is this "WE" white man crap. 

  If you want to separate into groups, I'll stick with the group of
people who know that 8 bits of data has more than 7 possible states.

http://www.deja.com/[ST_rn=ps]/getdoc.xp?AN=550929165&fmt=text

>From the quality of your posts

  LOL, you are one to talk about posting quality.  

>I would say it would be more of a favor for the beginning 

  That should be beginners, not beginning.

>not to hear from
>you since you don't seem to exhibit much knowledge of crypto in the
>first place.

  Quite a case of the pot calling the kettle black.

  Johnny Bravo
 

------------------------------

From: "Baruch Even" <[EMAIL PROTECTED]>
Date: Thu, 16 Dec 99 23:15:39 +0200
Reply-To: "Baruch Even" <[EMAIL PROTECTED]>
Subject: Re: Q: BBS

On Thu, 16 Dec 1999 19:34:20 +0100, Mok-Kong Shen wrote:

[snipped]

>Generally, an element belonging to a loop of length m satisfies
>
>    x^(2^m) = x  mod n 
>
>Question: Does this signify anything to the security offered by BBS?

This answer is based on info from the book "Cryptography: Theory and
practice" by Douglas Stinson, p.370-373. Though the mistakes, if any, are
wholly mine.

Since our seed a Quadratic Residue (QR) and our calculations are always
s_i=(s_(i-1))^2 mod n, which is a 1-1 function, we get that BBS is a
permutation on the subgroup QR(n), from which we get that it's period can be
pretty long,  the upper bound is half of phi(n)=(p-1)(q-1)  (*) which should
be pretty high.

(*) note that n=pq where p,q are large primes.

If I may try my hand at it, I think that |QR(n)| is exactly this upper bound
since in the group Z_n(star) we have that half of the numbers are QR since we
can take a generator g of the group and all its exponents which are even are
QR and those with odd exponent are not QR. (This needs to be proved better,
but I believe I did something like that or close enough in one of my late
exercises in a crypto course, so I allow myself to rely on this, I would be
glad to be corrected if I'm wrong).

Thus we get that BBS is a permutation on QR(n) and that the size of QR(n) is
exactly phi(n) which is pretty large for a large n, so to answer the question
the period is large enough not to pose a danger. Even then from knowing the
period it is hard to find the next bit, that is unless you have s_i.

The results stated in Stinson's book are that the BBS security is equivalent
to the problem of finding if x is in QR(n) which is believed to be hard.

Baruch


---
  [EMAIL PROTECTED]

place a dot between the ch and ev



------------------------------

From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Q: BBS
Reply-To: [EMAIL PROTECTED]
Date: Thu, 16 Dec 1999 21:10:18 GMT

Mok-Kong Shen <[EMAIL PROTECTED]> wrote:

: The interation underlying BBS: X_(i+1) = (x_i)^2  mod n ultimately cycles.

[...]

: Question: Does this signify anything to the security offered by BBS?

Not really.  Any deterministic PRNG with a finite internal state must
eventually cycle.
-- 
__________
 |im |yler  The Mandala Centre  http://www.mandala.co.uk/  [EMAIL PROTECTED]

Be different.  Act normal.

------------------------------

From: drickel <[EMAIL PROTECTED]>
Subject: Re: Deciphering without knowing the algorithm?
Date: Thu, 16 Dec 1999 13:23:17 -0800

In article <AHb64.269$qj7.2526@client>, "Steve Feldman"
<[EMAIL PROTECTED]> wrote:
> Newbie here.   Go easy on me.
> It it fact that NSA reads emails regularly?

Unknown.  Probably true that they read selected email regularly.  There
are supposed to be limits as to which communications they can monitor
(they aren't supposed to monitor communications within the US between
US citizens, or something like that).  They claim not to have the
resources to monitor more than a small fraction of current
communications.  Believe what you will; they're paid to lie.

> I thought that something like triple DES was not feasibly
> crackable.

There are a number of ciphers out that nobody who is talking knows how
to crack.  That doesn't stop people from believing that some super
spook agency knows hows to read them.

> Besides, if I sent some mail or other transmission of multiple
> files,
> binary, say, how would they have any idea that a given binary was
> encrypted
> information as opposed to some binary data?

You could speculate that NSA or whomever had context
analyzers--programs that would examine plaintext for suspicious
strings, that would run non-plaintext through some common checks to
look for jpegs, gifs, executables, headers from common compression
programs and would flag things that were sufficiently suspicious for
more in-depth analysis.

> Another question - if something non-exportable like triple DES was
> used to
> encrypt a file I send, should I expect NSA to come knocking on my
> door the
> next day?

I doubt it.  If you sent it to a known or suspected terrorist group you
might come to the attention of some other government groups.  If they're
any good, you'd never notice (until too late).

> Increasingly curious about this fascinating subject,
> Steve

Fun to speculate about, but fairly pointless.  If they're doing it,
we'll never know, and wouldn't be able to do anything it, regardless.


david rickel


* 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: SDpikachu <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Prime series instead (Re: Pi)
Date: Thu, 16 Dec 1999 01:09:36 -0000

At Wed, 15 Dec 1999 11:57:34 -0800, Erik Max Francis <[EMAIL PROTECTED]> 
said:
> 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.
Yes, but 1 isnt a prime, so it should have been:

N = 4(1/2 - 1/3 + 1/5 - 1/7 + 1/11 - 1/13 + 1/17 ... )

That was a completely pointless post... why do I bother?
-- 
¸¸,ø¤º°`Liyang Hu/DenseBoy°º¤ø,¸¸,ø¤º°http://www.nerv.cx/`°º¤ø,¸¸
|  The subspace W inherits the other 8 properties of V.         |
|    And there aren't even any property taxes.                  |
|      -- J. MacKay, Mathematics 134b                           |

------------------------------

From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: BBS
Date: Thu, 16 Dec 1999 22:48:58 +0100

Baruch Even wrote:
> 
> On Thu, 16 Dec 1999 19:34:20 +0100, Mok-Kong Shen wrote:
> 
> [snipped]
> 
> >Generally, an element belonging to a loop of length m satisfies
> >
> >    x^(2^m) = x  mod n
> >
> >Question: Does this signify anything to the security offered by BBS?
> 
> This answer is based on info from the book "Cryptography: Theory and
> practice" by Douglas Stinson, p.370-373. Though the mistakes, if any, are
> wholly mine.
> 
> Since our seed a Quadratic Residue (QR) and our calculations are always
> s_i=(s_(i-1))^2 mod n, which is a 1-1 function, we get that BBS is a
> permutation on the subgroup QR(n), from which we get that it's period can be
> pretty long,  the upper bound is half of phi(n)=(p-1)(q-1)  (*) which should
> be pretty high.
> 
> (*) note that n=pq where p,q are large primes.
> 
> If I may try my hand at it, I think that |QR(n)| is exactly this upper bound
> since in the group Z_n(star) we have that half of the numbers are QR since we
> can take a generator g of the group and all its exponents which are even are
> QR and those with odd exponent are not QR. (This needs to be proved better,
> but I believe I did something like that or close enough in one of my late
> exercises in a crypto course, so I allow myself to rely on this, I would be
> glad to be corrected if I'm wrong).
> 
> Thus we get that BBS is a permutation on QR(n) and that the size of QR(n) is
> exactly phi(n) which is pretty large for a large n, so to answer the question
> the period is large enough not to pose a danger. Even then from knowing the
> period it is hard to find the next bit, that is unless you have s_i.
> 
> The results stated in Stinson's book are that the BBS security is equivalent
> to the problem of finding if x is in QR(n) which is believed to be hard.

But the period of the least significant bit could be much less than
the period of the congruence relation. Or can that never happen
with the Blum integers as n?

M. K. Shen

------------------------------

From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: BBS
Date: Thu, 16 Dec 1999 22:48:48 +0100

David A Molnar wrote:
> 
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> 
> > Question: Does this signify anything to the security offered by BBS?
> 
> Well, if you start over in a cycle, you will output the same bits,
> and this will be bad. So you should know how long the cycle is for your
> particular instance of the generator. The last part of the BBS paper
> covers methods for determining parameters which yield maximum-length
> cycles. Terry Ritter also has an article in Cryptologia (?) and some
> discussion on his web page as to how to determine the cycle length
> of given parameters.
> 
> It's an interesting kind of problem - if you implement a BBS in say,
> Scheme, and keep iterating it, you can actually play with a lot of
> different parameters and notice that some work and some don't. and you can
> notice that if n isn't a blum integer, then your least sig bit is not
> particularly random at all...

I haven't read the literatures you gave. However, literatures
like Schneier's AC says only the following:
  
   First find two large prime numbers, p and q, that are congruent
   to 3 modulo 4. The product of those numbers, n = p*q, is a
   Blum integer.  ..............

without mentioning other constraints, i.e. further conditions
about the choice of p and q. (I understand that your 'parameters'
consist of p and q only.)

It would be nice, if you would like to help a bit more for my (quick)
understanding: For a single Blum integer, there may correspond a 
number of loops that are obtained through using different seeds. 
These loops may have different lengths. Without putting constraints 
on the choice of seeds, one has to ensure that the minimum of these
loop lengths is larger than a certain value that one needs. Is that
right? Further, the loop length of the congruence relation is 
certainly the upper bound of the corresponding loop length of the 
least significant bit. What one really needs to ensure is the minimum
length of loops of the least significant bit, not that of the 
congruence relation. Do the literatures you mentioned give 
precise rules for the choice of the parameters (p and q) for that
and provide useful estimates of the minimum loop length of the
least significant bit?

Thanks in advance.

M. K. Shen

------------------------------

From: [EMAIL PROTECTED] (Keith A Monahan)
Subject: Re: Invitation to our homepage
Date: 16 Dec 1999 21:51:12 GMT

Just in time for Christmas! I always want a PNEUMATIC drill!

Keith

(ÁÖ)»ó¾Æ´º¸Åƽ ([EMAIL PROTECTED]) wrote:
: DEAR SIR,

: WE ARE PLEASED TO VISIT YOUR HOME PAGE.
: WE ARE ALSO PLEASED TO INTRODUCE OURSELVES  AS LEADING MANUFACTURES
: AND EXPORTERS OF PNEUMATIC EQUIPMENTS IN SOUTH KOREA.
: WE EXPORT OUR PRODUCTS TO OVER 40 COUNTRIES IN THE WORLD.
: WE HOPE YOU TO VISIT  OUR INTER-NET HOME PAGE THROUGH  THE FOLLOWING
: ADDRESS.

:  http://www.sang-a.com/

: IF YOU CLICK OUR HOME PAGE, WE ARE SURE THAT YOU CAN GET A GOOD
: INFORMATION ABOUT OUR PRODUCT.
: THANK YOU FOR YOUR KIND ATTENTION.

:  SANG-A PNEUMATIC CO., LTD



------------------------------

From: "DM" <[EMAIL PROTECTED]>
Subject: Edgar Allan Poe Crypto Challenge.
Date: Thu, 16 Dec 1999 14:02:35 -0800

Any one ever check it out? Thoughts?

Here's the URL:
http://www.bokler.com/eapoe.html


=====
DM





------------------------------


** 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
******************************

Reply via email to