Cryptography-Digest Digest #787, Volume #10 Thu, 23 Dec 99 18:13:00 EST
Contents:
need help with randomly generated numbers ([EMAIL PROTECTED])
Re: Of one time pads, plaintext attacks, and fantasy (John Savard)
Re: Q: transcendental pad crypto (Vernon Schryver)
Re: More idiot "security problems" (lordcow77)
Re: More idiot "security problems" (Eric Lee Green)
Re: need help with randomly generated numbers (Eric Lee Green)
Re: need help with randomly generated numbers (CLSV)
Re: need help with randomly generated numbers ("Robert C. Paulsen, Jr.")
Re: Q: BBS ("Matt Timmermans")
Re: NEW PROGRAM = FREEDOM ("Thomas J. Boschloo")
Re: need help with randomly generated numbers (JCA)
Re: More idiot "security problems" (Guy Macon)
Re: Classic Cryptanalysis Tools Needed (Jim Gillogly)
Re: More idiot "security problems" (Dan Day)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: need help with randomly generated numbers
Date: Thu, 23 Dec 1999 17:08:18 GMT
i dont know much about encryption,but it would be nice if you could
answer my question or explain why its not possible.
lets imagine i have about a hundred valid 14-digit numbers out of maybe
1-3 million valid ones. how can I find the algorithm which was used to
generate these numbers and extrapolate new valid ones?
is there any program to calculate the relationship between randomly
generated numbers?
thanks
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Of one time pads, plaintext attacks, and fantasy
Date: Thu, 23 Dec 1999 10:29:22 GMT
Dave Hazelwood <[EMAIL PROTECTED]> wrote, in part:
>Algorithmic encryption on the other hand yields the answer to all
>messages when it is factored, can be brute forced or otherwise
>compromised.
But an XOR stream cipher that isn't a true OTP is "algorithmic".
It is true that public-key systems have a serious weakness: everything
depends on the assumption that a certain mathematical problem is
difficult.
Plain block ciphers can be brute-forced, but they also can be designed
to have pretty large keys.
Stream ciphers can be better, but they can't just be based on some
really simple math trick, like using an "OTP" based on starting with
the 1000th digit of sqrt(27+Euler's constant), or the complex zeroes
of the Riemann zeta function.
Why not use the digits from a phone book as an "OTP" key? That's
something that might baffle many adversaries, but it's probably one of
the first things the NSA would try.
There are ways to avoid the kind of limitation that I think is
worrying you, but using a silly little trick instead of an algorithm
isn't what's going to make things any better.
http://www.freenet.edmonton.ab.ca/~jsavard/co041205.htm
illustrates something that perhaps you may find appealing.
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (Vernon Schryver)
Subject: Re: Q: transcendental pad crypto
Date: 23 Dec 1999 10:49:25 -0700
In article <[EMAIL PROTECTED]>,
Paul Koning <[EMAIL PROTECTED]> wrote:
>John,
>
>Since your ISP is defective, I'll post this here rather than sending
>you mail. (It seems to be rejecting mail from here as being
>from a "uu.net dialup". It isn't, of course. UUnet is our backbone
>provider, I think. Silly reason to reject mail anyway. You may
>want to get a more competent ISP.
I've found the DUL the second most effect defense against spam, after
rejecting email with envelope Mail_From values pointing to free email
providers. That some people can't manage to implement accurate filters
against dialups is tiresome, but not as tiresome as spam.
Many of the entries listed in http://www.mail-abuse.org/dul/ are there
because the owners of the addresses have reported them, specifically
including UUnet for UUnet dialups. Some ISP's (again, specifically
including UUNET) have in the past published their dial-up blocks so that
they could be blocked while working on installing filters against port 25
traffic in their remote access servers.
I agree that an ISP filtering port 25 is even more offensive than spam
targets permanently filtering blocks of addresses, both merely because
ISP's can't be bothered to impose real penalities on their spamming
customers. But such is life.
Vernon Schryver [EMAIL PROTECTED]
------------------------------
From: lordcow77 <[EMAIL PROTECTED]>
Subject: Re: More idiot "security problems"
Date: Thu, 23 Dec 1999 10:20:34 -0800
In article <[EMAIL PROTECTED]>, "Trevor Jackson, III"
> > You could just shuffle the order of the items and check if
> they are in
> > order. If not shuffle again.
> I suppose this would be worse than O(N!). More like O(2^(N-1)).
> Let's see, if we use a universal compression mechanism on the
> elements does it raise the work
> factor to O(2^N) ?
Isn't O(n!) > O(2^n)? I though that factorials grew faster as n become
arbitrarily large than any exponential function of n?
* 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: Eric Lee Green <[EMAIL PROTECTED]>
Subject: Re: More idiot "security problems"
Date: Thu, 23 Dec 1999 11:54:25 -0700
"Trevor Jackson, III" wrote:
> Dan Day wrote:
> > On 19 Dec 1999 00:18:36 GMT, [EMAIL PROTECTED] (Xcott Craver) wrote:
> > > Now, if the program is capable of decrypting the data too,
> > > then you have a problem.
> >
> > But I believe that that's the case under discussion here. Eric
> > was talking about copy-protection schemes, wherein a program keeps
> > part of itself encrypted or otherwise "locked", but the program
> > itself knows how to "unlock" itself when it thinks it's running
> > on an authorized machine.
> >
> > By definition, it seems to me, such a program "is capable of
> > decrypting the data" that it needs.
> >
> > Eric's point is that such a system can always be broken just
> > by "looking over its shoulder" as it does its dirty work on itself.
>
> The analysis process may require access to the original machine, so a simple
> copy of the program is not enough. If the attacker can perform the attack on
> a legitimate machine the program can always be modified to suit. But if the
> attacker has only the program (binary), it is not always possible.
"Cracker" groups generally buy a legal copy (or otherwise possess one) of the
program they intend to attack, then develop attacks based on that single legal
copy and then propogate their attack via their web sites and/or virii. In the
case we're talking about, a password stored on disk was masked in order to
protect it from casual viewing. This password had to be unmasked to plain text
in order to send it over the network to an IMAP server. Given this, it doesn't
matter if the password was masked with a simple XOR or with 256-bit-key
TwoFish, anybody who "looked over the shoulders" of the running program could
similarly decrypt it. Given that fact, it made no sense to mask it with
anything more complex than a simple XOR mask.
I will agree that if you can't get the program to run at all (because you
don't have a licence key), you may have difficulty "looking over its
shoulder", but cracker groups rarely lack for license keys.
-Eric Lee Green [EMAIL PROTECTED]
http://members.tripod.com/e_l_green
------------------------------
From: Eric Lee Green <[EMAIL PROTECTED]>
Subject: Re: need help with randomly generated numbers
Date: Thu, 23 Dec 1999 11:58:15 -0700
[EMAIL PROTECTED] wrote:
> i dont know much about encryption,but it would be nice if you could
> answer my question or explain why its not possible.
> lets imagine i have about a hundred valid 14-digit numbers out of maybe
> 1-3 million valid ones. how can I find the algorithm which was used to
> generate these numbers and extrapolate new valid ones?
The general mechanism is to reverse-engineer the program that is generating
those numbers. If you're just fetching numbers off the net, you're pretty much
out of luck, but the NSA etc. have plenty of "black ops" types who specialize
in obtaining copies of encryption hardware and software to be
reverse-engineered.
It helps if you also manage to infect the machine doing the generating with a
virus that reports the internal state of the generator. And there's other
things I could think of with a few minutes of spare time.
Note that I'm no expert here, I'm sure the real experts up in Maryland are
giggling by now. But I do recommend that you go read the Yarrow paper at
http://www.counterpane.com for some examples of attacks against PRNG's.
-Eric Lee Green [EMAIL PROTECTED]
http://members.tripod.com/e_l_green
------------------------------
From: CLSV <[EMAIL PROTECTED]>
Subject: Re: need help with randomly generated numbers
Date: Thu, 23 Dec 1999 19:24:49 +0000
[EMAIL PROTECTED] wrote:
> i dont know much about encryption,but it would be nice if you could
> answer my question or explain why its not possible.
It is not possible to answer your question,
and I will explain why not :-)
> lets imagine i have about a hundred valid 14-digit numbers out of maybe
> 1-3 million valid ones. how can I find the algorithm which was used to
> generate these numbers and extrapolate new valid ones?
Which of the following things are you asking:
- I have 100 valid numbers and 1 million more, I want to know which
one gets chosen next;
- I have 100 valid numbers, there are 1 million more plus
N million invalid numbers I want to know what are the valid numbers;
- a combination of both.
> is there any program to calculate the relationship between randomly
> generated numbers?
If the specific pseudo-random method is weak enough a relationship
could be found. Well, that is as close as I could get to giving an
answer.
Regards,
CLSV
------------------------------
From: "Robert C. Paulsen, Jr." <[EMAIL PROTECTED]>
Subject: Re: need help with randomly generated numbers
Date: Thu, 23 Dec 1999 13:38:25 -0600
[EMAIL PROTECTED] wrote:
>
> i dont know much about encryption,but it would be nice if you could
> answer my question or explain why its not possible.
> lets imagine i have about a hundred valid 14-digit numbers out of maybe
> 1-3 million valid ones. how can I find the algorithm which was used to
> generate these numbers and extrapolate new valid ones?
> is there any program to calculate the relationship between randomly
> generated numbers?
> thanks
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
Can't be done. At least without knowing some additional information
about the numbers.
The problem is that relationships (formulae) can be invented that
produce *any* sequences of numbers. A multitude of formulae can be
invented for any given sequence. Thus, you could come up with a lot
of answers, no one of which is more "correct" than any of the others.
As an example, assume you have only four numbers (a,b,c,d) and that
they represent two points on a plane: (a,b) and (c,d). You could
assume that the two points define a straight line and therefore other
valid number pairs are valid if they fall on the same straight line.
But, you could also identify any number of circles (or parabolas, etc.)
that also pass through those same two points. Which formula is the
correct one (straight line, various circles, various parabolas, etc.)?
Unless you make some assumptions about those four numbers you have
no way of knowing what the "correct" answer is.
--
____________________________________________________________________
Robert Paulsen http://paulsen.home.texas.net
If my return address contains "ZAP." please remove it. Sorry for the
inconvenience but the unsolicited email is getting out of control.
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: Q: BBS
Date: Thu, 23 Dec 1999 13:50:11 -0500
The period of s^(2^i) mod n is phi(phi(n)) if 2 is a generator mod phi(n)
and s is a generator mod n. Othewise, the period will be shorter, and you
may want to pick a different seed (if s isn't a generator) or modulus (if 2
isn't a generator).
------------------------------
From: "Thomas J. Boschloo" <[EMAIL PROTECTED]>
Crossposted-To: alt.privacy.anon-server
Subject: Re: NEW PROGRAM = FREEDOM
Date: Thu, 23 Dec 1999 19:06:32 +0100
Steve K wrote:
>
> On Wed, 22 Dec 1999 18:11:03 +0100, "Thomas J. Boschloo"
> <[EMAIL PROTECTED]> wrote:
>
> >Maybe this cannot be avoided, as freedom (unlike jbn) filters mail and
> >everything at a very low OS level.
>
> It can easily be avoided, just re-write the network component of
^^
+------ collisions between a local firewall and freedom
> Freedom to function as a proxy, and have the user apply proxy settings
> in their browser and mail clients. Why they did not do this, is a
> great mystery to me. So is the absense of criticism from government
> agencies... nah, that's just the paranoia talking.
And how about IRC, Telnet and News?
And how about user friendlyness? Ever tried to find the http proxy
settings in the lattest MS Internet Explorer 5.x? Ever explained to a
simple user what a proxy is (like the add blocking www.webwasher.com)
and why they might need it? Not all computer users are as literate as
you (and maybe me, altough I don't use a firewall).
Hi,
Thomas
--
Boycot Intel Pentium III <http://www.bigbrotherinside.com/>
PGP key: http://x11.dejanews.com/getdoc.xp?AN=453727376
Email: boschloo_at_multiweb_dot_nl
------------------------------
From: JCA <[EMAIL PROTECTED]>
Subject: Re: need help with randomly generated numbers
Date: Thu, 23 Dec 1999 11:51:58 -0800
[EMAIL PROTECTED] wrote:
> i dont know much about encryption,but it would be nice if you could
> answer my question or explain why its not possible.
> lets imagine i have about a hundred valid 14-digit numbers out of maybe
> 1-3 million valid ones. how can I find the algorithm which was used to
> generate these numbers and extrapolate new valid ones?
You can't. You can trivially design two (or more) distinct algorithms
that generate that first sequence of one hundred numbes, but that differ
from that point on.
> is there any program to calculate the relationship between randomly
> generated numbers?
What do you mean? Their correlation?
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: More idiot "security problems"
Date: 23 Dec 1999 16:36:23 EST
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Trevor Jackson, III) wrote:
>
>Well, it's possible that I'm repeating a Programming Legend kind of story, but
>the contest was definitely restricted to fielded systems. Otherwise you'd have
>the time penalties of spacially abusive algorithms included.
>
I once programmed an embedded system to use StupidSort on a small
and fixed list of items to be sorted for the operator display.
StupidSort goes like this:
Randomize list
Is ilist sorted?
Exit if it is,
Go to beginning if it isn't.
It worked fine on my 4 item list!
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Classic Cryptanalysis Tools Needed
Date: Thu, 23 Dec 1999 22:03:02 +0000
John Savard wrote:
> Boaz Lopez <[EMAIL PROTECTED]> wrote, in part:
> >Leslie Wagner wrote:
> >> Does anyone have any crib dragging and shotgun hill climbing
> >> routines or programs thay can share?
>
> >Yes, there is a click and drag crib spreadsheet available from
> >ATRA Corp. The multidimensional sorting utility is automatic.
> >The so called "shotgun hill climbing" is implemented using
> >an expandable disk-cache scheme, with unlimited volume. Based on
> >the Koligranikova-Samolian Recursion, the hill-climbing is
> >the matrix expansion while the shotgun section depletes the
> >candidate list. It was $129 when I bought by Crypto-Pak for
> >Windows 98.
Gee, is it April already?
> I saw a recent reference in another thread to the power of the
> "shotgun hill-climbing" technique. Web sites describing it?
Not in detail, but for the basic idea see:
http://www.pbs.org/wgbh/nova/decoding/rupp.html
which has a pointer to the issue of The Cryptogram which describes
it in detail (Nov-Dec 1995).
--
Jim Gillogly
1 Afteryule S.R. 2000, 22:01
12.19.6.14.11, 13 Chuen 19 Mac, Third Lord of Night
------------------------------
From: [EMAIL PROTECTED] (Dan Day)
Subject: Re: More idiot "security problems"
Date: Thu, 23 Dec 1999 22:40:03 GMT
On 22 Dec 1999 16:59:53 -0800, [EMAIL PROTECTED] (David Eppstein)
wrote:
>It's also possible to get exponential or worse time if you really work
>at it e.g. go through all the permutations until you find one in the
>right order. But O(n^6)? In a fielded algorithm?
I've always liked the coined word "pessimal" (as opposed to "optimal")
for an algorithm that is about as bad as it can possibly be.
As far as bad fielded algorithms go, the worst one I ever discovered
myself (and then fixed with extreme prejudice) was at a major
international petroleum services and software company (which shall
remain nameless). The application was loading map data, which
simply consisted of lat/long coordinates of the major terrain features.
And even on a high-end Sun Unix box, it took FOREVER to load what
seemed like a not very large amount of map data.
No one else had ever bothered to examine the reason why in the
two years that the system had been up and running, so I took it upon
myself to fire up a profiler and see where it was wasting its time.
To make a long story short, it was spending 97% of its runtime checking
the clock several million times, and then writing the current time
to disk...
Every damned time it stored another lat/long coordinate, it:
1) Called the system time/date routine, in order to timestamp
the change to the database.
2) Converted the system time/date format to a custom time/date
format, using a convoluted "tear it apart and then put it
back together again" algorithm that involved a ridiculously
high number of 64-bit integer math calculations -- and since
the system didn't support 64-bit integer math, it had to
do the math via twiddling permutations of 8-bit integer bytes.
3) Attach the time/date stamp to the lat/long coordinate, and
write it to disk.
4) Since the database also kept a "last changed" marker at
the database file level, it then turned around and:
a) Called the system date time routine again.
b) Twiddled the bytes of the date/time again.
c) Wrote the date/time to the "last time file X was changed"
record of the "master file index" file.
5) Then, as if that wasn't bad enough already, since the previous
step involved changing the "master file index" file, *ITS*
"last changed" marker had to be updated too, so:
a) Call the system date/time routine again.
b) Twiddle the bytes again.
c) Write the date/time to the "last time the master index
was changed" record.
Repeat for next 100,000 coordinates...
After I cleaned this up, the map file loads went from 45 minutes
to 1.4 minutes...
And yes, we're way off topic now.
--
"How strangely will the Tools of a Tyrant pervert the
plain Meaning of Words!"
--Samuel Adams (1722-1803), letter to John Pitts, January 21, 1776
------------------------------
** 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
******************************
