Cryptography-Digest Digest #566, Volume #13 Sat, 27 Jan 01 05:13:00 EST
Contents:
no joke (adam)
Re: Dynamic Transposition Revisited (long) ("John A. Malley")
Re: Dynamic Transposition Revisited (long) (Benjamin Goldberg)
Re: KASUMI Analysis? (Was: Re: 3G crypto algorithms) ("Scott Fluhrer")
Re: no joke ("Michael Brown")
Re: Encryption Program ("Markus Hahn")
Re: Dynamic Transposition Revisited (long) (Mok-Kong Shen)
Re: Dynamic Transposition Revisited (long) (Mok-Kong Shen)
Re: Encoded serial number:Help! ("Michael Brown")
Help with algorithm needed ("Michael Brown")
----------------------------------------------------------------------------
From: adam <[EMAIL PROTECTED]>
Subject: no joke
Date: Sat, 27 Jan 2001 06:19:44 GMT
I found this on a bulletin board and decided to try it. A little while
back, I was browsing through news groups, I just like you are now, and
came across an article
similar to this that said you could make thousands of dollars within
weeks with only an initial investment of $6.00! So I thought, "Yeah
right, this must be a scam", but
like most of us, I was curious, so I kept reading. Anyway, it said that
you send $1.00 to each of the 6 names and address stated in the article.
You then place your
own name and address in the bottom of the list at #6, and post the
article in at least 200 newsgroups. (There are thousands) No catch, that
was it. So after thinking it
over, and talking to a few people first, I thought about trying it. I
figured: "what have I got to lose except 6 stamps and $6.00, right?"
Then I invested the measly
$6.00. Well GUESS WHAT!!... within 7 days, I started getting money in
the mail! I was shocked! I figured it would end soon, but the money just
kept coming in. In
my first week, I made about $25.00. By the end of the second week I had
made a total of over $1,000.00! In the third week I had over $10,000.00
and it's still
growing. This is now my fourth week and I have made a total of just over
$42,000.00 and it's still coming in rapidly. It's certainly worth $6.00,
and 6 stamps, I have
spent more than that on the lottery!! Let me tell you how this works and
most importantly, why it works....Also, make sure you print a copy of
this article NOW, so
you can get the information off of it as you need it. I promise you that
if you follow the directions exactly, that you will start making more
money than you thought
possible by doing something so easy! Suggestion: Read this entire
message carefully! (print it out or download it.) Follow the simple
directions and watch the money
come in! It's easy. It's legal. And, your investment is only $6.00 (Plus
postage) IMPORTANT: This is not a rip-off; it is not indecent; it is not
illegal; and it is virtually
no risk - it really works!!!! If all of the following instructions are
adhered to, you will receive extraordinary dividends. PLEASE NOTE:
Please follow these directions
EXACTLY, and $50,000 or more can be yours in 20 to 60 days. This program
remains successful because of the honesty and integrity of the
participants. Please
continue its success by carefully adhering to the instructions. You will
now become part of the Mail Order business. In this business your
product is not solid and
tangible, it's a service. You are in the business of developing Mailing
Lists. Many large corporations are happy to pay big bucks for quality
lists. However, the money
made from the mailing lists is secondary to the income which is made
from people like you and me asking to be included in that list. Here are
the 4 easy steps to
success: STEP 1: Get 6 separate pieces of paper and write the following
on each piece of paper "PLEASE PUT ME ON YOUR MAILING LIST." Now get 6
US
$1.00 bills and place ONE inside EACH of the 6 pieces of paper so the
bill will not be seen through the envelope (to prevent thievery). Next,
place one paper in
each of the 6 envelopes and seal them. You should nowhave 6 sealed
envelopes, each with a piece of paper stating the above phrase, your
name and address, and a
$1.00 bill. What you are doing is creating a service. THIS IS ABSOLUTELY
LEGAL! You are requesting a legitimate service and you are paying for
it! Like most
of us I was a little skeptical and a little worried about the legal
aspects of it all. So I checked it out with the U.S. Post Office
(1-800-725-2161) and they confirmed
that it is indeed legal! Mail the 6 envelopes to the following
addresses: #1) S.Preston 1289 Huron St. London, ON,
Canada N5Y 4L6 #2) Beaner 12 Windsor Cres., North Bay, Ontario, Canada
poh 1p0 #3) Shane 82 Pawnee Rd. London, ON, Canada N5V 2S8 #4) Jason 123
Garvin Ave., Elyria, Ohio, 44035 #5) C. Atkinson 6 Richmond Drive,
Basking Ridge, NJ 07920 #6 Adam 5234 Huntington Ave. Richmond, CA
94804 STEP 2: Now take the #1 name off the list that you see above,
move the other names up (6 becomes 5, 5 becomes 4, etc...) and add YOUR
Name as number 6 on the list. STEP 3: Change anything you need to, but
try to keep
this article as close to original as possible. Now, post your amended
article to at least 200 newsgroups. (I think there are close to 24,000
groups) All you need is
200, but remember, the more you post, the more money you make! This is
perfectly legal! If you have any doubts, refer to Title 18 Sec. 1302 &
1341 of the Postal
lottery laws. Keep a copy of these steps for yourself and, whenever you
need money, you can use it again, and again. PLEASE REMEMBER that this
program
remains successful because of the honesty and integrity of the
participants and by their carefully adhering to the directions. Look at
it this way. If you are of integrity,
the program will continue and the money that so many others have
received will come your way. NOTE: You may want to retain every name and
address sent to
you, either on a computer or hard copy and keep the notes people send
you. This VERIFIES that you are truly providing a service. (Also, it
might be a good idea to
wrap the $1 bill in dark paper to reduce the risk of mail theft.) So, as
each post is downloaded and the directions carefully followed, six
members will be reimbursed
for their participation as a List Developer with one dollar each. Your
name will move up the list geometrically so that when your name reaches
the #1 position you
will be receiving thousands of dollars in CASH!!! What an opportunity
for only $6.00 ($1.00 for each of the first six people listed above)
Send it now, add your own
name to the list and you're in business! ---DIRECTIONS ----- FOR HOW TO
POST TO NEWSGROUPS------------ Step 1) You do not need to re-type this
entire letter to do your own posting. Simply put your cursor at the
beginning of this letter and drag your cursor to the bottom of this
document, and select 'copy' from
the edit menu. This will copy the entire letter into the computer's
memory. Step 2) Open a blank 'notepad' file and place your cursor at the
top of the blank page.
>From the 'edit' menu select ' paste '. This will paste a copy of the
letter into notepad so that you can add your name to the list. Step 3)
Save your new notepad file as
a .txt file. If you want to do your postings in different settings,
you'll always have this file to go back to. Step 4) Use Netscape or
Internet explorer and try searching
for various newsgroups (on-line forums, message boards, chat sites,
discussions.) Step 5) Visit these message boards and post this article
as a new message by
highlighting the text of this letter and selecting paste from the edit
menu. Fill in the Subject, this will be the header that everyone sees as
they scroll through the list of
postings in a particular group, click the post message button. You're
done with your first one! Congratulations...THAT'S IT! All you have to
do is jump to different
newsgroups and post away, after you get the hang of it, it will take
about 30 seconds for each newsgroup! **REMEMBER, THE MORE NEWSGROUPS YOU
POST IN, THE MORE MONEY YOU WILL MAKE!! BUT YOU HAVE TO POST A MINIMUM
OF 200** That's it! You will begin receiving money from
around the world within days! You may eventually want to rent a P.O.Box
due to the large amount of mail you will receive. If you wish to stay
anonymous, you can
invent a name to use, as long as the postman will deliver it. **JUST
MAKE SURE ALL THE ADDRESSES ARE CORRECT.** Now the why part: Assume for
example you get a 7.5% return, which is very conservative. 1) when you
mail out 200 letters, 15 people will send you $1.00 2) those 15 mail out
200 letters, 225
people will send you $1.00 3) those 225 mail out 200 letters, 3,375
people will send you $1.00 4) those 3,375 mail out 200 letters, 50,625
people will send you
$1.00 5) those 3,375 mail out 200 letters, 759,375 people will send you
$1.00 By now your name has dropped off the list, but so far you have
received at least
$759,375.00!! With an original investment of only $6.00! AMAZING! When
your name is no longer on the list, you just take the latest posting in
the newsgroups,
and send out another $6.00 to names on the list, putting your name at
number 6 again. And start posting again. The thing to remember is: do
you realize that
thousands of people allover the world are joining the internet and
reading these articles everyday?, JUST LIKE YOU are now!! So, can you
afford $6.00 and see if
it really works?? I think so... People have said, "what if the plan is
played out and no one sends you the money? So what! What are the chances
of that happening
when there are tons of new honest users and new honest people who are
joining the internet and newsgroups everyday and are willing to give it
a try? Estimates are
at 20,000 to 50,000 new users, every day, with thousands of those
joining the actual internet. Remember, play FAIRLY and HONESTLY and this
will really work.
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: Dynamic Transposition Revisited (long)
Date: Fri, 26 Jan 2001 23:08:54 -0800
AllanW wrote:
> I think John A. Malley was trying to find the number of
> possible outputs of the PRNG and compare it to the number of
> states of the bit-balanced plaintext block. There is more than
> one way to do the shuffle, but if you're selecting N numbers
> of value 0 to (N-1) then there are N**N possibe outputs for
> the PRNG, and (N!)/((N/2!)(N/2!)) possible states for the
> plaintext.
>
Yes, that's true, I wanted to understand the relationship between the
number of possible outputs of the PRNG compared to the number of states
of the bit-balanced blocks, and since a predictable (not
cryptographically secure) PRNG is used, were there statistical
vulnerabilities in the permutation selections.
I started with the high-level description of the Dynamic Transposition
cipher:
(1) Collect plaintext data in bit-balanced (or almost
bit-balanced) blocks.
(2) Shuffle the bits in those blocks under the
control of a keyed pseudorandom sequence.
Three errors on my part propagated though the thread of discourse with
Mr. Ritter:
1. I did not understand the requirement that one out of the possible N!
permutations of the N-bit bit-balanced block be 'randomly' applied to
the current N-bit block with independence from the permutations applied
to previous blocks (or as independently as possible). So a random
permutation out of N! is applied to each block (as a goal.)
2. I immediately grabbed my copy of Knuth's "The Art of Computer
Programming, Seminumerical Algorithms", Vol. 2 upon a quick read of the
original "Dynamic Transposition Revisited" post to read about the
Shuffling Algorithm P, and there in the text I read the cautionary
paragraph that Algorithm P cannot generate more than m distinct
permutations when driven by a recursive (output feedback) that takes on
only m distinct output values. Here my imagination fixed on PRNGs using
generators on finite fields. Such a PRNG based on Z*_p where p is prime,
for example, makes an output sequence containing every value from 1 to
p-1, once, in some order, before repeating. Such a PRNG could generate
every value from 1 to N! but each value (permutation) would occur only
once and would never reappear until the PRNG cycled. This was
consistent with misunderstanding 1) above.
All statements I made about the number of outputs and number of possible
sequences of permutations were predicated on the use of a PRNG that
outputs each possible permutation once and only once before its output
cycle repeats. I thought this would be a weakness with an
implementation of a DTC, but Mr. Ritter already knew that and never had
any intention to use such a PRNG.
3. I overlooked the fact a PRNG can generate multiple instances of the
same output value if it maps more than one internal state to the same
output value. (The canonical model cited in the thread, from a paper by
Prof. Pierre L'Ecuyer, "Uniform Random Number Generation", in the Annals
of Operations Research, 1994, shows this with the function G that maps
internal states of the PRNG to output symbols.) So in fact a PRNG could
get close (but never exactly match) the goal behavior of generating one
random permutation out of N!, independently for each block of plaintext,
only if it had >> N! states.
I understand these points now.
Thanks for your help, too :-)
Now I'm spending time trying to understand Mr. Ritter's statement about
the additive PRNG and the canonical PRNG model in L'Ecyuer's paper,
"Unfortunately, this model does not completely fit an Additive RNG, at
least in the sense of providing insight as to which RNG values are
going to be correlated,"
which threw me, since L'Ecuyer addresses the additive PRNG in that paper
but never says anything about it differing in any sense from the
canonical model in the paper.
It's best I go off and read some more :-)
John A. Malley
[EMAIL PROTECTED]
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Dynamic Transposition Revisited (long)
Date: Sat, 27 Jan 2001 07:48:41 GMT
John Savard wrote:
>
> On Fri, 26 Jan 2001 21:52:58 GMT, [EMAIL PROTECTED] (Terry Ritter) wrote,
> in part:
>
> >That is not a semantic argument, or a philosophical question -- it is
> >the real situation. For example, perhaps we could show that a
> >certain amount of information is necessary to distinguish between our
> >real RNG and the theoretical ideal. Then if we could show that the
> >information is not available, we could have provable "perfection,"
> >much like other cryptographic proofs.
>
> That's an interesting thought.
>
> But the 'answer' is that as soon as one has enough bits of information
> to do a successful brute-force search, we can distinguish, even if we
> don't know how to distinguish _efficiently_. And proving that we won't
> discover in future how to distinguish efficiently is, I believe,
> fundamentally impossible.
>
> In the specific case of Dynamic Transposition:
>
> We have N bit blocks.
>
> Our PRNG generates one of N! permutations for each block.
>
> Given known plaintext, all we know is that the permutation generated
> is one of a set of (N/2)!(N/2)! possible permutations.
>
> Then, if the internal state of our PRNG is x bits, the number of
> blocks of known plaintext required (on average) for uniquely
> establishing that state is z, where z is the least integer such that
>
> 2^x
>
> is less than or equal to
>
> (N!/((N/2)!(N/2)!))^z
Hmm. I'm not sure if this is right, so correct me if I'm wrong:
x is the size of the key (size of the internal PRNG state)
N is the size of the block
z is the number of blocks needed to uniquely establish the key
2^x <= (N!/((N/2)!(N/2)!))^z
x ln 2 <= z ln (N!/((N/2)!(N/2)!))
z >= (x ln 2) / (ln (N!/((N/2)!(N/2)!)))
If the attacker has z or more blocks of known plaintext, we can assume
he knows the key. If we simply make sure that we always send fewer than
z blocks under any one key, the cipher is probably [provably?] secure
against any attack save brute force.
> This even applies if there are two transposition layers, as long as x
> is the number of state bits in _both_ PRNGs.
Unless I'm mistaken, both transpositions are done using the same PRNG.
> The security of Dynamic Transposition, like other ciphers with a
> fixed-length key shorter than the plaintext, depends on the work
> factor, and is not information-theoretic in nature.
--
Most scientific innovations do not begin with "Eureka!" They begin with
"That's odd. I wonder why that happened?"
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: KASUMI Analysis? (Was: Re: 3G crypto algorithms)
Date: Sat, 27 Jan 2001 00:13:31 -0800
Paul Rubin <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> [EMAIL PROTECTED] (John Savard) writes:
> > >Has anyone had a look at KASUMI, the 'new' block cipher to be used with
> > >3GPP? Any comments or critical appraisal?
> >
> > As I recall, while someone posted an URL, the cipher is supposed to be
> > a trade secret or something like that. Thus, those who have read its
> > description are not supposed to talk about it.
>
> Not so. The description is published.
In fact, you can get it from http://www.etsi.org/dvbandca/3GPP/3gppspecs.htm
--
poncho
------------------------------
From: "Michael Brown" <[EMAIL PROTECTED]>
Subject: Re: no joke
Date: Sat, 27 Jan 2001 22:27:10 +1300
It's no fun taking the piss out of these any more. They're just too common.
------------------------------
From: "Markus Hahn" <[EMAIL PROTECTED]>
Subject: Re: Encryption Program
Date: Sat, 27 Jan 2001 09:31:10 GMT
The latest PGP _freeware_ version (6.58) is available and allows
also symmetric encryption of files, available at
http://web.mit.edu/network/pgp.html
(although for automation you might need to use public keys)
Markus
"Benjamin" <[EMAIL PROTECTED]> wrote in message
news:94sjm4$933$[EMAIL PROTECTED]...
> Hello,
>
> My name is Benjamin and currently our company is looking for a
> command line based encryption program that we can automate. I
> understand that certain tools exist under various *nix operating
> systems. Unfortuantly, under the circumstances that we are in we are
> only able use this program in a Windows based environment. Does such a
> tool exist in the windows environment? If so, where might i find this
> program? I have done various searches on the internet and on security
> sites and have had no such luck. Any information that may be passed
> along is greatly appreciated. Again, many thanks in advance!
>
>
> Benjamin Branch
>
>
> Sent via Deja.com
> http://www.deja.com/
>
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Dynamic Transposition Revisited (long)
Date: Sat, 27 Jan 2001 10:41:53 +0100
Paul Pires wrote:
>
> Terry Ritter <[EMAIL PROTECTED]> wrote:
[snip]
> > I have mentioned the possibility of a statistical or "almost" balance,
> > which could be very effective. But it seems like that analysis would
> > be much more complicated. We would have to talk about the
> > distribution of balance, and how strength changes accordingly, which
> > seems beyond what can now be done.
>
> I don't know about that. I think it can be done. But that opinion and
> $2.79 might by a cup of coffee.
I like to suggest that one at first limits all discussions of
strength of DT to using only (the subset of) balanced blocks
from the outset. (I used that to simplify argumentation
of a point of mine in another follow-up.) That would avoid
unnecessarily having the methodology of bit balancing
(a more technical issue) clouding up the fundamental issue.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Dynamic Transposition Revisited (long)
Date: Sat, 27 Jan 2001 10:41:46 +0100
Terry Ritter wrote:
>
> Mok-Kong Shen<[EMAIL PROTECTED]> wrote:
>
> >[...]
> >Then one has to wait your 'showing'. Before that, one
> >certainly can't legitimately support your previous claim
> >of superiority of DT over OTP, I believe.
>
> Then you believe incorrectly.
>
> We already know that OTP is weak if the sequence it uses is
> predictable. We also know that there is no test which can guarantee
> that a sequence we use is not predictable. The OTP thus has inherent
> potential weakness: the possibility of using a sequence with
> predictable structure.
>
> In contrast, Dynamic Transposition hides any structure in its'
> sequence behind permutations which do not reveal the sequence. This
> is an obvious superiority.
>
> Now we have a contest. OTP is not the obvious winner, I believe.
I suppose you have a different and problematical concept
of the (THEORETICAL) OTP. The bit sequence of OTP is by
definition/assumption unpredictable. If a 'claimed' OTP
uses a predictable bit sequence and consequently is weak
as you said, then it is by definition NOT an OTP, though
snake-oil peddlers used to call that OTP. Some people in
crypto groups even object to use the term pseudo-OTP to
designate that kind of stuff. (Once I got flames for having
employed the term pseudo-OTP.) We should take care not to
be contaminated in our terminology by the slangs of
snake-oil peddlers. (Of course they could complain, because
anything used 'one-time' is OT, but that's evidently outside
our present concern.)
BTW, my argumention in the previous follow-up could be
simplified a bit. One does not have to use the big sequence
S. It suffices to pick one arbitrary balanced block and
feed repetitions of it to the algorithm. Basically, the
argument boils down to the trivial fact that a PRNG has a
finite period, while the theoretical OTP has, by definition,
an infinite period. Hence there is no chance that the former
can compete with the latter.
M. K. Shen
=============================
http://home.t-onle.de/home/mok-kong.shen
------------------------------
From: "Michael Brown" <[EMAIL PROTECTED]>
Subject: Re: Encoded serial number:Help!
Date: Sat, 27 Jan 2001 22:56:41 +1300
> for s/n: 96000529 (dec) the number: 2D (hex) is calculated in
> 2nd eprom
>
> for s/n: 95000367 (dec) the number: 2E (hex) is calculated in
> 2nd eprom
Unfortunately, this is far too little information :(
One thing that might help in analysis is the date of manufacture of these
machines. Is the first built in '96 and the second in '95? If so then things
become a lot easier. Then we have the resulting binary numbers to work with
(s/n then checksum):
1000010001 101101 (1)
0101101111 101110 (2)
The number of "1" bits grows from 3 to 4 from the s/n to checksum in (1).
This indicates something as simple as taking certain bits is not possible.
If it is a simple machine then I would say that it would be a combination of
logical (OR, AND, XOR, NOT) operations on these 10 bits. The trouble is that
there are so many possibilities. Any number of zeros may be at the start of
the 10 bit number to zero the 2 upper bits of the checksum, or the 2 in the
checksum may just be a fluke and the important part could be the D or E.
What I would really like to know is why you need to know the algorithm to
generate checksums? If you need to do your own eprom then just copy in the
value. If you want to take the eprom from another (dead) machine then move
the serial nmber eprom across.
Or, if you want to get really sneaky, patch the eprom and disable the
checking for a valid serial number :)
Michael
------------------------------
From: "Michael Brown" <[EMAIL PROTECTED]>
Subject: Help with algorithm needed
Date: Sat, 27 Jan 2001 23:05:27 +1300
Hi there,
The point of this strange problem will be revealed in a couple of weeks
(after I get the program done - and it is VERY relevent to cryptography -
hint to wtshaw: remember reverse wassel tree adding scheme I think it's
called) but I'm stuck with one thing.
A table of pairs is generated like this:
Column 0 : no pairs
Column 1 : (1,2)
Column 2 : (1,3)
Column 3 : (1,4) (2,3)
Column 4 : (1,5) (2,4)
Column 5 : (1,6) (2,5) (3,4)
Column 6 : (2,6) (3,5)
Column 7 : (3,6) (4,5)
Column 8 : (4,6)
Column 9 : (5,6)
Column 10 : no pairs
Column 11 : no pairs
It is easy to get from Column number & pair number to the pair, but how do
you get from an arbitary pair to a column and pair number?
Thanks in advance,
Michael
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************