Cryptography-Digest Digest #63, Volume #12 Mon, 19 Jun 00 15:13:01 EDT
Contents:
Re: test prog !! (Mark Wooding)
Re: Comments/analysis requested: stream cipher derived from hash function (SHA-1)
(Lon Willett)
Re: Mathematical formula (Darren New)
Re: GF Math problems (mulinv) (Mike Rosing)
Re: Mathematical formula (Simon Johnson)
Re: small subgroups in Blum Blum Shub (Terry Ritter)
Re: XOR versur MOD (Mok-Kong Shen)
Re: Flattening of frequency distributions (Mok-Kong Shen)
Re: Online Text Encryption (Terry Ritter)
Re: Newbie: germans please: field == Koerper ? (math) (Christof Paar)
Re: GF Math problems (mulinv) (tomstd)
Re: software protection schemes ("John E. Kuslich")
Re: Weight of Digital Signatures (Paul Koning)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: test prog !!
Date: 19 Jun 2000 16:46:06 GMT
[EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
> i seek also maurers test prog in c if possible or executable msdos !!!
Catacomb 2.0.0pre1 has code for doing Maurer's test (maurer.c). I
implemented from the description in Menezes, van Oorshott and Vanstone's
Handbook of Applied Cryptography.
I'm not *entirely* convinced it's working right. I occasionally get
*very* badly skewed results -- I've seen some as far off as seven
standard deviations! -- for 2- and especially 1-bit blocks, even with
generators I'd expect to be good, such as the BBS.
Hmm. Does anyone have some good test vectors for Maurer's test using
single bits, giving the final ought-to-be-distributed-according-to-
N(0, 1) variable Z_u?
-- [mdw]
------------------------------
From: Lon Willett <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: Comments/analysis requested: stream cipher derived from hash function
(SHA-1)
Date: Mon, 19 Jun 2000 16:58:26 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> In sci.crypt.random-numbers Lon Willett <[EMAIL PROTECTED]> wrote:
>
> :> I removed the XOR of the output with H[i+1], because it allows
state
> :> following attacks (what you called iterative guessing attacks
above)
> :> if each H value is of low entropy, and all E values are of zero
entropy.
> :> If you're concerned with this type of attack, it's better to mix in
> :> entropy only in fairly large chunks.
>
> : Good point. But a very tricky situation, and I'm not sure that I
got it
> : wrong. In order to know how many "H" values one should collect
before
> : mixing them in, one has to have a reasonable estimate of the entropy
> : that they contain. If the hardware RNG is working correctly, then
my
> : approach is fine. If it is defective or sabotaged, how can one
estimate
> : the entropy they contain? The safest assumption is that they
contain
> : zero entropy. And in that case, nothing is lost by mixing them in
> : immediately.
>
> This sounds dubious to me - though I'm not sure I'm following it all
> correctly ;-)
>
> I don't think you should not assume H contains zero entropy. If it
> contains zero entropy, once the state is learned, it's known for all
time
> (determinism).
>
> OTOH, if H contains a small quantity of entropy, you can /potentially/
> defeat an attacker who has learned the state by accumulating the
entropy -
> and then performing the infamous "catastrophic reseeding".
>
> If you dripple the entropy into the system as you go along then the
> attacker can perform the "state following" attack to maintain his
> knowledge of the internal state by repeated guesswork.
>
> The problem of estimating the entropy of the inputs is a significant
one
> - but the idea that the solution is to assume they have zero entropy -
> and not bother with entropy accumulation methods - on the grounds that
> you never know for certain when you have enough entropy - seems very
> questionable.
> --
> __________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
> |im |yler The Mandala Centre http://mandala.co.uk/ I'm pink :.
I'm spam
>
I probably shouldn't have put the "H" values in at all; they are
irrelevant to the questions I'm interested in. :-(
But to continue on this tangent...
This discussion has made me think about it more, and I'm still
convinced that the hardware RNG output should have special handling
(along the lines of what I am doing).
What you seem to be misunderstanding, is that the "H" values are not
the sole source of entropy; they are entropy from some special
hardware RNG. I have "E" values which are the more typical (portable)
miscellaneous sources of entropy. Everything you said is valid for
the "E" values. I specifically avoid introducing them until they are
believed to have accumulated sufficient (160+ bits) entropy. And
indeed, getting these values and estimating their entropy is the
hardest part of writing a decent RNG.
As for my separate handling of "H" and "E", consider the nature of a
hardware RNG. When one has a hardware RNG, and it is working, it
makes the rest of my code irrelevant. In this situation, the software
is used only to provide an "insurance policy" against the failure of
the hardware RNG. And in what ways might the hardware RNG fail?
The primary concern is sabotage. And note that this is exceptionally
easy. Consider, for example, the Intel RNG that is being put on a lot
of motherboards these days. An attacker need only substitute his own
chip for the RNG chip. And his chip would look and act just like the
Intel, except that instead of providing random output, it provides its
output from 3DES in OFB mode, using a preset key. So the attacker
needs only to guess (and he probably can make a very close estimate)
the location in the stream from where it is returning the output, and
he knows exactly what you are getting. The "H" values really do have
very close to zero entropy in this case. And you can't increase it by
reading more values (the only entropy from the attacker's point of
view is the location within the stream).
Furthermore, unless you can crack 3DES, there is no test that you can
perform to detect that this chip is not functioning correctly (other
than ripping it apart and analyzing its internals). The NSA may be
producing such chips now (or, if you are really paranoid, maybe you
think that the Intel is already doing this for them).
So in this case, you will be relying entirely on the "E" values and
the software RNG (your "insurance policy"). The "E" values are
collected from the usual places: mouse and keyboard, miscellaneous
performance and timing statistics, etc. It is actually much harder to
so completely sabotage the entropy in these components, without also
modifying some software as well (and hopefully you have an effective
means of verifying your software's integrity).
I have some other justifications, but they are distinctly secondary to
the one above. And, on the other side, the only scenario (ignoring
performance constraints) where it makes sense to treat the "H" values
just like another entropy source (i.e. just mixing them into the "E"
values) is when you don't like the design of the hardware RNG, and
believe that it is producing _significantly_ less than full entropy,
and the hardware RNG driver doesn't compensate for this. And you can
handle this within my model (just do it, as suggested, and set the "H"
values to zero), or you can fix the driver to compensate for this
shortcoming. But there's not much you can do against the above attack
on the hardware RNG, other than collect adequately strong "E" values
that are _independent_ of the "H" values (which requires treating the
"H" values as a source with _no_ entropy).
In summary, a reasonably good hardware RNG output (my "H") and
miscellaneous sources of entropy (my "E") really do have different
characteristics and vulnerabilities, and therefore should be handled
differently by a RNG implementation.
I hope that this has clarified my thinking.
/Lon Willett
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Mathematical formula
Date: Mon, 19 Jun 2000 17:47:51 GMT
Simon Johnson wrote:
> e.g. For RC4 40-bit, it 2^40 possible keys (roughly 1 trillion).
> Where as RC4 128-bit has 2^128 keys. Therefore RC4 128-bit is 88
> times as 'strong' RC4 40-bit.
That doesn't sound right. I think you mean RC4 128-bit would be 2^88 times
as strong. Otherwise, one could crack RC4 with 88 trillion operations, or
with 88 machines of the same class as can crack RC4-40.
--
Darren New / Senior MTS & Free Radical / Invisible Worlds Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
"You know Lewis and Clark?" "You mean Superman?"
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: GF Math problems (mulinv)
Date: Mon, 19 Jun 2000 12:53:04 -0500
tomstd wrote:
>
> Using Mike Rosings book (Implementing ECC) I am trying to devise
> my own set of GF routines. So far I have done addtion,
> multiplication, modular multiplication and division by myself
> (without the book), but I got stuck on multiplicative inverses.
> At http://tomstdenis.com/files/gfmath.c
>
> Is my work-in-progress. For some reasons some elements don't
> find inverses. I am using the polynomial from twofish (since
> it's easy to memorize :)) 0x169. I try to find inverses for
> decimal '5' and I get values out of range...
>
> I probably overlooked something...Please help!!
Code looks ok (for a 30 second glance). Is that poly prime?
You've got a lot of stuff on each line. Too many tricks makes
even simple things too complicated to check easily. This chunk
for example:
/* check to see if this multiple of 'b' divides 'a' */
i = deg_a >> 5ul; j = 1ul << (deg_a & 31);
if ((t1[i] & t2[i]) & j) {
gf_add(t1, t2); i = deg_a - deg_b; q[i>>5ul] |= (1ul<<(i&31)); }
may or may not have a bug in it. Even with a debugger, you'd have
a hard time single stepping this and figuring out what your variables
actally are.
Spread it out and print out intermediate values. Do something you
know works by hand so you can follow each step. When the error in
your hand work is fixed by the computer, you know you're on the right
track :-)
Patience, persistence, truth,
Dr. mike
------------------------------
Subject: Re: Mathematical formula
From: Simon Johnson <[EMAIL PROTECTED]>
Date: Mon, 19 Jun 2000 11:04:47 -0700
You thought correct, sorry for the mistake :)
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: small subgroups in Blum Blum Shub
Date: Mon, 19 Jun 2000 18:15:49 GMT
On 19 Jun 2000 10:22:19 GMT, in <[EMAIL PROTECTED]>,
in sci.crypt [EMAIL PROTECTED] (Mark Wooding) wrote:
>Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>> I am not commenting on the chance of using a 'weak key' but like
>> to mention that for a sequence from a non-linear generator there
>> is normally an initial segment (which could be long) followed by
>> a loop, so that the chance of getting problems due to the loop is
>> likely to be higher if one uses longer sequences from the generator.
>
>This doesn't happen in the BBS. To see this, it suffices to note that,
>within the subgroup of quadratic residues mod n where n is a Blum
>integer, the map x |-> x^2 is bijective.
It can be extremely educational to build some fairly small examples of
the generator, and then follow them through, state by state, until all
states have been covered. I did this by computer program, but some of
the smaller versions might be as easy and more meaningful when done by
hand, or calculator. The complex internal structure of these systems
is simply not apparent from their simple description.
In my published experimental results:
http://www.io.com/~ritter/ARTS/CRNG2ART.HTM#Sect7.2.2
I call the number of states which lead to a cycle an "arc," and all of
the experimental BB&S versions -- both proper and improper -- had an
arc length of exactly one.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: XOR versur MOD
Date: Mon, 19 Jun 2000 20:24:29 +0200
"Tony T. Warnock" wrote:
> If the same size blocks are used, for example 8 bits, both the XOR and
> MOD 256 after addition, or even MOD 256 after subtraction, give the same
> outputs permuted. The operation tables for each of these is a latin
> square. The XOR is more flexible in that a block size is not implied
> (other than 1 bit.)
I am afraid I haven't properly understood you. In addition/subtraction
there are carry-overs. Thus in general the resulting bits cannot be
a permutation of the result of xor. Consider a two bits field. Addition
of 11 and 01 gives 00, while xor gives 10.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Flattening of frequency distributions
Date: Mon, 19 Jun 2000 20:24:36 +0200
Stefan Schlott wrote:
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >A normal compression algorithm doesn't have a secret key, thus
> >the opponent can decompress just as well as the legitimate
> >receiver.
> That's what the following encryption process is for.
But if a secret key is involved in the flattening process, you have
in effect a multiple encryption. Note that if you are very sure that
your chosen system is secure, then you certainly don't need
anything more, whether frequency flattening or else. Recently
in another thread it was discussed that frequency flattening could
be of some value against the risk of accidental reuse of OTP.
> >Thus it adds practically nothing to the difficulty of his
> >task.What we want is flattening that he can't (or with difficulty)
> >figure out how to undo in order to recover the original plaintext.
> You asked for a way to flatten distributions in natural language,
> because exploiting uneven distributions are a classic tool of crypt-
> analysis.
> Compressing your text before encrypting it will do that. You might
> run into trouble with data which cannot be compressed with the codec
> in use. Further (as I already mentioned), special care should be given
> when storing the data necessary for decompression; when not done
> properly, this will lead to known-plaintext attacks.
Are you assuming that the compression algorithm is secret? If not,
and there is no secret key involved, then the opponent can decompress,
so that he is in the same situation as if no compression has been done.
For use of an adaptive Huffman compression (plus secret information)
to achieve encryption purposes, see the recent thread 'On using
compression as proper means of encryption' initiated by me.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Online Text Encryption
Date: Mon, 19 Jun 2000 18:17:27 GMT
On Mon, 19 Jun 2000 11:55:12 -0400, in <[EMAIL PROTECTED]>,
in sci.crypt "Trevor L. Jackson, III" <[EMAIL PROTECTED]> wrote:
>[...]
>I'm certain Terry Ritter and most readers are familiar with this usage.
Alas, yes.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: Christof Paar <[EMAIL PROTECTED]>
Subject: Re: Newbie: germans please: field == Koerper ? (math)
Date: Mon, 19 Jun 2000 13:57:52 -0400
Ja, "Field" translates into "Koerper". The translations for "Galois field"
(und nicht Galouis :) is "endlicher Koerper". Note that "Galois
fields" and "finite fields" are the same thing.
Gruss,
Christof
! WORKSHOP ON CRYPTOGRAPHIC HARDWARE AND EMBEDDED SYSTEMS (CHES 2000) !
! WPI, August 17 & 18, 2000 !
! http://www.ece.wpi.edu/Research/crypt/ches !
***********************************************************************
Christof Paar, Assistant Professor
Cryptography and Information Security (CRIS) Group
ECE Dept., WPI, 100 Institute Rd., Worcester, MA 01609, USA
fon:(508) 831 5061 email: [EMAIL PROTECTED]
fax:(508) 831 5491 www: http://www.ece.wpi.edu/People/faculty/cxp.html
***********************************************************************
On Mon, 19 Jun 2000, Runu Knips wrote:
> "Tony T. Warnock" wrote:
> > XOR works in the field GF(2**k) where ADD works in the ring (MOD 2**k).
> > ADD is non-linear in the field whereas XOR is non-linear in the ring.
> > The ring and the field are different algebraic structures.
>
> Hmm. Is the english "Field" the same mathematical term as the
> german "Koerper" ? How do the germans call that "Galouis
> Field" then ?
>
------------------------------
Subject: Re: GF Math problems (mulinv)
From: tomstd <[EMAIL PROTECTED]>
Date: Mon, 19 Jun 2000 11:28:15 -0700
Mike Rosing <[EMAIL PROTECTED]> wrote:
>tomstd wrote:
>>
>> Using Mike Rosings book (Implementing ECC) I am trying to
devise
>> my own set of GF routines. So far I have done addtion,
>> multiplication, modular multiplication and division by myself
>> (without the book), but I got stuck on multiplicative
inverses.
>> At http://tomstdenis.com/files/gfmath.c
>>
>> Is my work-in-progress. For some reasons some elements don't
>> find inverses. I am using the polynomial from twofish (since
>> it's easy to memorize :)) 0x169. I try to find inverses for
>> decimal '5' and I get values out of range...
>>
>> I probably overlooked something...Please help!!
>
>Code looks ok (for a 30 second glance). Is that poly prime?
>You've got a lot of stuff on each line. Too many tricks makes
>even simple things too complicated to check easily. This chunk
>for example:
> /* check to see if this multiple of 'b' divides 'a'
*/
> i = deg_a >> 5ul; j = 1ul << (deg_a & 31);
> if ((t1[i] & t2[i]) & j) {
> gf_add(t1, t2); i = deg_a - deg_b; q[i>>5ul] |=
(1ul<<(i&31)); }
>
>may or may not have a bug in it. Even with a debugger, you'd
have
>a hard time single stepping this and figuring out what your
variables
>actally are.
Yeah that is a bit obfuscated..
>
>Spread it out and print out intermediate values. Do something
you
>know works by hand so you can follow each step. When the error
in
>your hand work is fixed by the computer, you know you're on the
right
>track :-)
I will try this out. Normally I do use printfs but it was too
late for me to reasonably work it out...
I am cetain that 0x169 is a primitive poly since it's used in
Twofish as part of the MDS code...
Thanks,
Tom
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: "John E. Kuslich" <[EMAIL PROTECTED]>
Subject: Re: software protection schemes
Date: Mon, 19 Jun 2000 11:59:40 -0700
A classic example of software protection that depends on a complex software
verification system is popular database software (not the program itself but
the security measures implemented ob the databases it creates).
I validating a user, certain versions of Access have a complex set of SID's
(security identifiers) and implements a marginally secure version of RC4
with a hard coded key. Anyone tracing this code would probably find this
tedious in the extreme and give up upon breaking the Access user level
security.
Until, that is, you realize that the security is based on ultimately one bit
in the software being set or being reset. This bit answers the simple
question "is this a valid user??? Yes? or No?" All the attacker has to do
is to find this bit and change it to instantly become a valid user. This
bit is easy to find in memory and thus Access can be considered to have very
little real security.
Almost any software protection scheme running on the PC suffers from this
same vulnerability. If the attacker finds the magic bit that finally
authenticates the user, the software protection will not work. Usually it
is very easy to find this bit. If there are multiple levels of checks with
many bits scattered throughout the executable, the job is a little more
difficult. Any scheme that is deliberately and perversely complex is likely
to be buggy and slow and still subject to attack by automated tools. Dongle
protection scheme fall into this category. Most dongle protection scheme
have been broken.
Good, reliable software protection in the PC environment is a myth.
JK Password Recovery Software http://www.crak.com
Been the victim of a disgruntled employee?
Have you lost access to important data you own?
Contact CRAK Software, We Can Help
lament <[EMAIL PROTECTED]> wrote in message
news:pyf35.5748$[EMAIL PROTECTED]...
> In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
> > RecilS wrote:
> > > They don't all currently suck. All mass-market schemes suck simply
because
> > > they do not have the time to tailor computer-specific protection. An
actual
> > > recompilation of source (not a key-code algorithm) which relies upon
the
> > > processor's ID to decrypt necissary code seems to work for me.
> >
> > Why ? You simply replace the assembly code which gets that "unique" id
> > with a routine which returns that unique id - then your "perfect"
> > protection is also broken.
>
> Good point. But what if the "code which gets the unique ID" returns a
hashed version
> of the found ID? This hashed value is saved in "global" memory, and is
operated on at
> various times by various pieces of code in the application, especially
during
> startup. Each operation further hashes/changes the global value until --
sometime
> later -- it is used. The "sometime later" may only be a second or two --
but that's a
> lot of code to step through with a debugger. The "is used" means that the
current
> value is used in a calculation or other operation such that if the value
is
> incorrect, the program will fail.
>
> A simple example is that a current value is the limit in a FOR loop, or is
bitwise
> ANDed to a local integer. Subsequent changes are made to the value, and
usages occur
> during the normal execution of the program. All subsequent values, or most
all, have
> to be correct. A value could be accessed many times (in a loop) in a
harmless way,
> but would cause a debugger to repeatedly detect a "hit." Further, a single
hashed
> value can be replicated into many other hashed global values at various
times and
> places in the application. Some are used in an essential way, some not. I
think it
> would be very difficult to hunt down all accesses to this data, and
determine what
> the initial "returned ID' ought to be.
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: Weight of Digital Signatures
Date: Mon, 19 Jun 2000 14:56:20 -0400
Lyalc wrote:
>
> In general, a lay-persons analysis of electronic signature legislation based
> on the UNCITRAL Model Law shows they have 5 main components; the electronic
> signature
> ...
> iv) be under the sole control of the individual identified.
Ok, so that immediately excludes any digital signatures generated
by Microsoft products from consideration, right? :-)
I'd wish, but I suspect not. Any bets on how long it will take for
the first MS Visual Basic (Outlook, Word, pick one) virus to appear
that generates digital signatures for the benefit of the criminal?
Surely that won't be hard.
paul
------------------------------
** 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
******************************
