Cryptography-Digest Digest #541, Volume #13 Wed, 24 Jan 01 15:13:00 EST
Contents:
Re: Some Enigma Questions ("David C. Barber")
How much of this group's discussion violates the DMCA ("David C. Barber")
Re: 3G crypto algorithms (Arturo)
Re: How many bits of security can a password give? (Tom St Denis)
Re: TSEPRNG, a secure RNG ? (Dan Parisien)
Re: Transposition code (Richard Heathfield)
Re: How much of this group's discussion violates the DMCA
DES check values (58)
Re: How much of this group's discussion violates the DMCA (Richard Heathfield)
finding inverses and factoring (David A Molnar)
Re: TSEPRNG, a secure RNG ? (Splaat23)
Re: 3G crypto algorithms[Off-Topic: Asian Echelon] (Abe Lin)
Re: Fitting Dynamic Transposition into a Binary World (John Savard)
Re: DES check values (Splaat23)
Re: How many bits of security can a password give? (Erik Runeson)
Re: Cryptographic Camouflage (Darren New)
Echelon in Asia. (Abe Lin)
----------------------------------------------------------------------------
From: "David C. Barber" <[EMAIL PROTECTED]>
Subject: Re: Some Enigma Questions
Date: Wed, 24 Jan 2001 10:55:31 -0700
"John Savard" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> It still wouldn't be as secure as, say, DES.
One difference is that one could do a reasonable pencil+paper
encrypt/decrypt of an enigma message if the machine wasn't available. Hard
to say the same about DES.(Yes, I know possible, but *much* harder.)
*David Barber*
------------------------------
From: "David C. Barber" <[EMAIL PROTECTED]>
Subject: How much of this group's discussion violates the DMCA
Date: Wed, 24 Jan 2001 11:00:29 -0700
I wonder how much of this group's current discussions about systems and how
they're broken is in violation of the Digital Millennium Copyright Act,
which prohibits any attempt to reveal or break even lame systems.
Any informed opinion(s) on this?
*David Barber*
------------------------------
From: Arturo <[EMAIL PROTECTED]=NOSPAM>
Subject: Re: 3G crypto algorithms
Date: Wed, 24 Jan 2001 18:23:34 +0100
On Tue, 23 Jan 2001 14:06:25 +0100, Mok-Kong Shen <[EMAIL PROTECTED]>
wrote:
>
>
>Arturo wrote:
>.....
>
>In a town not too far from mine there is an
>Echelon station.
Hmmm, you mean Bad Aibling? Or maybe some other I didnīt hear about?
Details, please. Iīm interested in the matter (you can post here or drop me
some bytes at [EMAIL PROTECTED]; PGP keys available at keyservers).
>It is possible in Germany for a government
>agency to lawfully but secretly install a microphone in
>one's home. Right now there is a little revision of the law
>underway to make the recording of telephone conversations
>an even more convenient task.
And thereīs an European-wide effort at Carvirorizing the old continent.
Just browse to http://www.ugr.es/~aquiran/cripto/enfopole.htm for more details.
(Hint: Convention on Mutual Assistance In Criminal Matters, Title III:
"Interception of Communications").
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: How many bits of security can a password give?
Date: Wed, 24 Jan 2001 17:57:34 GMT
In article <94mn7a$27r$[EMAIL PROTECTED]>,
Erik Runeson <[EMAIL PROTECTED]> wrote:
> I'm doing some analysis on how many bits of security a password can
> provide.
>
> For instance, if we take a password with 8 random characters (all lower
> case to simplify a bit), it is easy to assume that it would mean:
> 8*8=64 bits of security (since each character is 8 bits).
> However, since there are only 26 lower case letters, the actual figure
> is:
> log2( 26^8 ) = 37.6 bits
>
> Of course, the whole issue gets a lot more complicated when you add
> upper case letters, numbers and other characters, as well as dealing
> with the fact that users rarely choose random passwords.
>
> Does anyone know any articles or other studies in this area?
You're generally right, but use the def'n of entropy to calc the bits of info
in a string instead of using an assumption.
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Dan Parisien <[EMAIL PROTECTED]>
Subject: Re: TSEPRNG, a secure RNG ?
Reply-To: [EMAIL PROTECTED]
Date: Wed, 24 Jan 2001 18:17:58 GMT
> An attacker might be able to force system load to be abnormally high.
> For some systems, this might result in deterministic round robin
> scheduling, such that the number of instructions given to each thread
> becomes known easily guessable to the attacker.
Maybe I'll explain the algorithm in more detail because this kind of attack
has no effect on it.
Race conditions caused by multi-threaded programming causes a large amount
of headaches to programmers. Why? Because there is no way (theoretically)
of knowing in which order they will be executed (so you must place locks
around shared data). That is entropy.
To test the theory that threads get scheduled differently each time (under
the exact same conditions), I created controlled race conditions. I started
many threads and made them wait on an event. Each thread has an identity
(in the test I gave each thread a different number). When the event is
triggered, all threads try and append to a shared structure in memory.
Theoretically the order in which they get appended to the structure is
aleatoric (because if it wasn't, locks and semaphores would be a useless
waste of resources). The test I ran proved the theory; the simple test
produced many different results.
After the test proved my hunch I produced two functions that accentuate the
entropy of thread scheduling. Instead of using a sequence of numbers, I
used a predictably seeded prng (the seed was, as previously mentioned, 1
each run). The first algorithm simply appended data to a shared structure
(which already was already proven to provide entropy). The second algorithm
used blocks from the previous shared structure as identities for the
threads. Each threads polls a shared prng (out of sequence) to bitwise-xor
the value of the identity.
Using those algorithms, I also created threads that manage those threads,
and create race conditions with the master threads as well. The lists are
shuffled (by random appending) and mangled (by random xor). The result is
very dynamic data.
I guess the best answer would be to post the source code :)
Dan
------------------------------
Date: Wed, 24 Jan 2001 19:36:50 +0000
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: Transposition code
Benjamin Goldberg wrote:
>
> John Savard wrote:
> >
> > On Mon, 22 Jan 2001 05:04:45 +0000, Richard Heathfield
> > <[EMAIL PROTECTED]> wrote, in part:
> >
> > >Why?
> >
> > Well, he is using C. So, if he is using malloc, it is more convenient
> > to have a one-dimensional array, although one could always use an
> > array of pointers to get a two-dimensional notation.
>
> Right. Actually, the real problem is figuring out the indices I need
> for the transposition. It's easy enough to do the transposition on
> paper, but figuring out the numbers needed isn't quite so easy.
>
> What I want to do is this:
>
> If I have a plaintext of abcdef, and a key of acb, the table looks like:
>
> a c b
> -----
> a b c
> d e f
> g h
>
> and the resulting text that I want is:
> adgcfbeh
>
> This is obtained by reading down the columns.
>
> Assuming I've got the "permutation" array like in my earlier post (or
> it's inverse),
[my rather mediocre news server has forgotten your earlier post, so I'll
have to "wing it"]
> my text in "txt" and my output going to "out", how do I
> calculate the transposition?
>
> for( i = 0, j = strlen(key); txt[i]; ++i )
> out[ permutation[i%j]+(i/j)*j ] = txt[i];
>
> Is wrong, I know... but what is right?
We have J columns, one for each byte of the key.
We have I items of text altogether, stored in txt[I], a one-dimensional
array.
I'm going to ignore your permutation array, and hope that you can plug
it back in. Sorry about that.
Also, I'm going to cheat and pretend your key consists of non-negative
integers.
Also also, I'm going to teach you to suck eggs. Sorry about that, but
(as you have discovered), this is deceptively difficult for bears of
very little brain such as myself, so I am going to take it step by
painful step.
Consider this table:
Key: 0 2 1
----------------
Text: 0 1 2
3 4 5
6 7 8
9 10 11
12 13 14
15 16 17
18 DD DD
This table has 7 (numrows) rows and 3 (klen) columns. DD means Dummy
Data, which you don't output. (You might wish to maintain a separate bit
array for this instead of reserving a character for it.)
We can see fairly easily now that text[i] is in row i / klen and column
i % klen. Given column C and row R, we can calculate that the
appropriate index into the text array is C * klen + R.
We want to transpose the table to
0 3 6 9 12 15 18
2 5 8 11 14 17 DD
1 4 7 10 13 16 DD
Now let k[] be the key ({0, 2, 1} in our example), and let n be the
number of the column we're about to transpose. tkb is "this key byte".
size_t tkb, c, j;
size_t klen = sizeof k / sizeof k[0]; /* you'll want strlen here, I
expect, and you'll have to make an appropriate change to the line n =
k[tkb]. */
for(tkb = 0, c = 0; tkb < klen; tkb++) /* iterating through the key */
{
n = k[tkb]; /* select the appropriate column of the first table */
for(j = 0; j < numrows; j++) /* select the appropriate row of the
first table */
{
out[c++] = text[n * klen + j];
}
}
And that's it... I think! Like I said, you'll need to make a small
adjustment if there are gaps in the first table, but I'm reasonably sure
this will work. On the other hand, I didn't exactly test it or
anything... ;-)
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html
------------------------------
From: <[EMAIL PROTECTED]>
Subject: Re: How much of this group's discussion violates the DMCA
Date: Wed, 24 Jan 2001 18:41:55 GMT
David C. Barber <[EMAIL PROTECTED]> wrote:
> I wonder how much of this group's current discussions about systems and how
> they're broken is in violation of the Digital Millennium Copyright Act,
> which prohibits any attempt to reveal or break even lame systems.
It prohibits the reverse engineering of copy protection, not "lame
systems." A real minority of the content is applicable.
--
Matt Gauthier <[EMAIL PROTECTED]>
------------------------------
From: 58 <[EMAIL PROTECTED]>
Subject: DES check values
Date: Wed, 24 Jan 2001 18:39:41 GMT
My company uses DES to encrypt fixed length (16-character) values.
Much as I'd like to see them make the leap from DES, it's what our
system, indeed all the businesses with which we work, uses.
I am a custodian for one part of the clear text, and I am a hobbyist
BASIC programmer (no laughing, please). One business to whom we must
occasionally send this text requires that we apply some simple XOR math
to mask the true text. This isn't hard, and I've written a program
that does this for us and fills out a form.
The business also asks that we provide a check value for the clear
text, so that they can confirm it when they undo the XOR functions.
And this is where I'm not proceeding well. For my tests, I used our
Atalla SIU to generate some random clear text and the check values for
each. When I try to generate my own check values, they're wrong.
I understand that the algorithm to generate a check value simply
encrypts with a key of all zeroes. I confirmed this on our SIU. I
followed the ANSI standard to the best of my knowledge, making sure
each step of the algorithm had its own routine, and the routines and
tables all look right. The minor adjustments I've made don't change
the check value, and I'm not sure where the real problem is (should be
beyond the last sections, but I've adjusted those, too).
So, I guess the easiest step, vice trying to re-invent this wheel, is
to determine if such a program already exists. It doesn't have to be
BASIC, but it does need to run on an NT. If the program accepted input
on the command line, so much the better so I could integrate it with
the bits I've already written.
If anyone knows of such a beastie I would appreciate hearing about it.
I would prefer a followup here, but email is also acceptable.
Thanks,
Larry
Sent via Deja.com
http://www.deja.com/
------------------------------
Date: Wed, 24 Jan 2001 19:56:34 +0000
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: How much of this group's discussion violates the DMCA
"David C. Barber" wrote:
>
> I wonder how much of this group's current discussions about systems and how
> they're broken is in violation of the Digital Millennium Copyright Act,
> which prohibits any attempt to reveal or break even lame systems.
>
> Any informed opinion(s) on this?
No, just a question.
In which country is that law applicable?
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: finding inverses and factoring
Date: 24 Jan 2001 18:36:08 GMT
Hi,
I recall that in RSA, knowledge of d alone, combined with e and n, is
enough to derive phi(n) and factor. I don't recall the proof,
unfortunately - so I apologize if this post turns out to be trivial.
Two related questions.
Suppose I publish n, g1 a generator of some subgroup in n, and g2 a
generator of some subgroup of "the exponents mod n", which have order
phi(n). Further I publish g1^(g2^x) and g2^x. The value n is made public,
but phi(n) is not revealed. Can phi(n) be feasibly determined?
Suppose I publish g1^(g2^x). Can (g2^-x) mod phi(n) be feasibly determined
without knowledge of phi(n)? It seems to me that (g1^(g2^x))^-1 gives us
g^(g^x + g^-x), which does not seem helpful.
Thanks,
-David Molnar
------------------------------
From: Splaat23 <[EMAIL PROTECTED]>
Subject: Re: TSEPRNG, a secure RNG ?
Date: Wed, 24 Jan 2001 19:03:48 GMT
No, actually the best answer would _not_ be to produce source code. In
fact, we know enough about your algorithm already from the description
(or at least I do).
However, do _you_ know how the OS task scheduler is written? I don't,
but I imagine it uses some sort of deterministic algorithm, since
computers are deterministic devices. Are you prepared to show that
scheduler's are unpredictable? Or can you even accurately estimate the
entropy of the scheduler under any given conditions?
The point is that internally generated entropy is an unknown. Attacks
may surface that undermine the scheduler, especially if a PRNG uses it
for random number generation. Your testing, although commendable, is
not a proof of security. It is a good assurance that the data "appears"
random, but lots of things appear random that aren't, or aren't to the
expected degree. TrueRand is the same thing with much of the same
problems.
However, you can secure your algorithm if you can guarantee >= a
certain amount of entropy per bit output from race conditions. If you
can do this, then once sufficient entropy has been collected, hash and
key a PRNG with that hash. Input such as your algorithm can output can
be fed to a PRNG like Yarrow, which can use it for seeding and
reseeding purposes.
- Andrew
In article <q%Eb6.117049$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> > An attacker might be able to force system load to be abnormally
high.
> > For some systems, this might result in deterministic round robin
> > scheduling, such that the number of instructions given to each
thread
> > becomes known easily guessable to the attacker.
>
> Maybe I'll explain the algorithm in more detail because this kind of
attack
> has no effect on it.
>
> Race conditions caused by multi-threaded programming causes a large
amount
> of headaches to programmers. Why? Because there is no way
(theoretically)
> of knowing in which order they will be executed (so you must place
locks
> around shared data). That is entropy.
>
> To test the theory that threads get scheduled differently each time
(under
> the exact same conditions), I created controlled race conditions. I
started
> many threads and made them wait on an event. Each thread has an
identity
> (in the test I gave each thread a different number). When the event
is
> triggered, all threads try and append to a shared structure in
memory.
> Theoretically the order in which they get appended to the structure
is
> aleatoric (because if it wasn't, locks and semaphores would be a
useless
> waste of resources). The test I ran proved the theory; the simple
test
> produced many different results.
>
> After the test proved my hunch I produced two functions that
accentuate the
> entropy of thread scheduling. Instead of using a sequence of numbers,
I
> used a predictably seeded prng (the seed was, as previously
mentioned, 1
> each run). The first algorithm simply appended data to a shared
structure
> (which already was already proven to provide entropy). The second
algorithm
> used blocks from the previous shared structure as identities for the
> threads. Each threads polls a shared prng (out of sequence) to
bitwise-xor
> the value of the identity.
>
> Using those algorithms, I also created threads that manage those
threads,
> and create race conditions with the master threads as well. The lists
are
> shuffled (by random appending) and mangled (by random xor). The
result is
> very dynamic data.
>
> I guess the best answer would be to post the source code :)
>
> Dan
>
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (Abe Lin)
Subject: Re: 3G crypto algorithms[Off-Topic: Asian Echelon]
Date: Wed, 24 Jan 2001 19:13:19 GMT
Hi,
Aside from Echlon, nothing much about Asia is being reported to
my knowledge. Anyone has input?
Thanks/abe
On Wed, 24 Jan 2001 18:23:34 +0100, Arturo <[EMAIL PROTECTED]=NOSPAM>
wrote:
>On Tue, 23 Jan 2001 14:06:25 +0100, Mok-Kong Shen <[EMAIL PROTECTED]>
>wrote:
>
>>
>>
>>Arturo wrote:
>>.....
>>
>>In a town not too far from mine there is an
>>Echelon station.
>
> Hmmm, you mean Bad Aibling? Or maybe some other I didnīt hear about?
>Details, please. Iīm interested in the matter (you can post here or drop me
>some bytes at [EMAIL PROTECTED]; PGP keys available at keyservers).
>
>>It is possible in Germany for a government
>>agency to lawfully but secretly install a microphone in
>>one's home. Right now there is a little revision of the law
>>underway to make the recording of telephone conversations
>>an even more convenient task.
>
> And thereīs an European-wide effort at Carvirorizing the old continent.
>Just browse to http://www.ugr.es/~aquiran/cripto/enfopole.htm for more details.
>(Hint: Convention on Mutual Assistance In Criminal Matters, Title III:
>"Interception of Communications").
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Fitting Dynamic Transposition into a Binary World
Date: Wed, 24 Jan 2001 19:15:38 GMT
On Wed, 24 Jan 2001 17:26:10 GMT, Splaat23 <[EMAIL PROTECTED]>
wrote, in part:
>If the
>block isn't a "valid" balanced block, then simply repeat the
>transposition (assuming it is not it's own inverse) until you get a
>valid 162-bit balanced string. This (as far as I can tell, IANA good
>cryptographer) should not compromise security.
Yes, I'm aware of this trick, and I remember thinking of it when I was
10 years old as a method of using the 27-letter alphabet to perform
trigraphic encipherment of texts strictly confined to the 26-letter
alphabet.
Since it does require extra time, and especially a _variable_ amount
of time, however, it is the sort of thing I prefer to avoid if
possible.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Splaat23 <[EMAIL PROTECTED]>
Subject: Re: DES check values
Date: Wed, 24 Jan 2001 19:20:12 GMT
You basically want a checksum to verify the message once it's been
decrypted, right? There are any number of checksum algorithms that are
fast and easy to program. CRC32 is the standard I think. If you
need/want collision-free and one way, look to MD5 or SHA-1. But I can't
imagine I got your circumstances correct. Could you please clarify
exactly what you need?
- Andrew
In article <94n7hb$ij0$[EMAIL PROTECTED]>,
58 <[EMAIL PROTECTED]> wrote:
> My company uses DES to encrypt fixed length (16-character) values.
> Much as I'd like to see them make the leap from DES, it's what our
> system, indeed all the businesses with which we work, uses.
>
> I am a custodian for one part of the clear text, and I am a hobbyist
> BASIC programmer (no laughing, please). One business to whom we must
> occasionally send this text requires that we apply some simple XOR
math
> to mask the true text. This isn't hard, and I've written a program
> that does this for us and fills out a form.
>
> The business also asks that we provide a check value for the clear
> text, so that they can confirm it when they undo the XOR functions.
> And this is where I'm not proceeding well. For my tests, I used our
> Atalla SIU to generate some random clear text and the check values for
> each. When I try to generate my own check values, they're wrong.
>
> I understand that the algorithm to generate a check value simply
> encrypts with a key of all zeroes. I confirmed this on our SIU. I
> followed the ANSI standard to the best of my knowledge, making sure
> each step of the algorithm had its own routine, and the routines and
> tables all look right. The minor adjustments I've made don't change
> the check value, and I'm not sure where the real problem is (should be
> beyond the last sections, but I've adjusted those, too).
>
> So, I guess the easiest step, vice trying to re-invent this wheel, is
> to determine if such a program already exists. It doesn't have to be
> BASIC, but it does need to run on an NT. If the program accepted
input
> on the command line, so much the better so I could integrate it with
> the bits I've already written.
>
> If anyone knows of such a beastie I would appreciate hearing about it.
> I would prefer a followup here, but email is also acceptable.
>
> Thanks,
> Larry
>
> Sent via Deja.com
> http://www.deja.com/
>
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Erik Runeson <[EMAIL PROTECTED]>
Subject: Re: How many bits of security can a password give?
Date: Wed, 24 Jan 2001 19:30:01 GMT
In article <94n528$g0c$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
> You're generally right, but use the def'n of entropy to calc the bits
of info
> in a string instead of using an assumption.
It's been a while since my cryptography class, but as I remember it,
entrophy is used when you are dealing with a written text. I assume
random passwords, so there is no redundancy based on e.g. the structure
of the language. I'm trying to find an upper limit to how strong a
regular password can be.
-Erik Runeson
---
Disclaimer: This post represent my personal views,
not those of my employer.
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Subject: Re: Cryptographic Camouflage
Date: Wed, 24 Jan 2001 19:50:21 GMT
Mok-Kong Shen wrote:
> I haven't looked at the detailed document. But the formulation
> of the short description appears indeed to be puzzling. It
> seems to claim that, since entering something (whether right
> or wrong) into the device and there always comes out something,
> an outsider can't know from this fact (alone) whether what was
> entered is correct or not. But that's a trivial, isn't it?
>From my reading, the idea was to protect a private key that's encrypted with
a passphrase. There would be a checksum on the decrypted key that says you
decrypted it properly. A minor typo would lead to a broken checksum, so you
know it's a typo, and you don't try to use it. But there might be zillions
of invalid passphrases, thousands of "pseudo-valid" passphrases, and only
one valid passphrase. If you did an offline brute-force search for a
passphrase, you'd be much more likely to find a pseudo-valid passphrase than
the single valid one. Then you try to use it online. *That* gets you
immediately locked out.
I.e., it looks like it's protecting against offline searches of passwords
you can only truely verify online.
Of course, that's just my interpretation. Read the actual patent for what
they're actually covering.
--
Darren New / Senior MTS & Free Radical / Invisible Worlds Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
"It says this wine has syphilis."
"I think that's pronounced `sulphates'."
------------------------------
From: [EMAIL PROTECTED] (Abe Lin)
Subject: Echelon in Asia.
Date: Wed, 24 Jan 2001 19:52:39 GMT
Hi, forum,
We've been seeing a bit about echlon, but I haven't heard anything
in Asia yet. Given Chinese Government's nature, they'd really surprise
me if they don't have one.
Anyone?
rgds/abe
------------------------------
** 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
******************************
