Cryptography-Digest Digest #289, Volume #13 Thu, 7 Dec 00 18:13:01 EST
Contents:
Re: Hamming Distance (John Myre)
Re: keysize for equivalent security for symmetric and asymmetric keys (John Myre)
Re: hardware RNG's ("Tony T. Warnock")
Re: Encrypting messages in images?? (Antonio Varni)
Re: Hamming Distance ([EMAIL PROTECTED])
Re: How to embed a key in executable code? (David Schwartz)
Re: How to embed a key in executable code? ([EMAIL PROTECTED])
Re: Fips Pub 140-1 and RNG ([EMAIL PROTECTED])
Modular arithmetic ("KENNETH H MARTIN")
RSA Coding Assistance ([EMAIL PROTECTED])
Byte-oriented Huffman coding (lit.) (Mok-Kong Shen)
Re: RSA Coding Assistance (Paul Rubin)
Re: Modular arithmetic (Mok-Kong Shen)
Re: Modular arithmetic ("Michael Scott")
Re: weten we die PIN? (John)
Re: Hamming Distance ("Matt Timmermans")
Re: Idea for ciphering? (correction w/ addition) (Mok-Kong Shen)
breaking rsa knowing the original text ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Hamming Distance
Date: Thu, 07 Dec 2000 10:35:49 -0700
Paul Crowley wrote:
<snip>
> How many strings do you tend to have? What does x tend to be?
Good questions.
> If x is
> really small (like 3 or something) then you could speed things up by
> throwing the strings into buckets based on the first byte, then only
> comparing those strings which are close enough in the first byte. In
> any case, you can abandon the software population count as soon as the
> Hamming threshold is crossed.
<snip>
Clever. And the buckets don't have to be based on exactly
8 bits; depending on circumstances a shorter or longer
piece might do. Indeed, I wonder if you could do this
recursively: once you've decided you need to compare strings
within a pair of buckets, what if you redistributed them
among buckets again based on more bits?
Wait, wait - I feel an idea coming on. What if we actually
compute the hamming distances between first bytes. That
is to say, between buckets. Then, to compare entries from
one bucket with those in another, you reduce x by the
distance between buckets. Recurse as appropriate. Will
this work? Would it be faster or slower to recurse one
bit at a time? What's the best time to bottom out the
recursion (and resort to the simple n^2 method)?
==========================================================
The following is based on ruminations from before I saw
your post. I don't think it will actually help solve
the OP's problem, but I include it anyway for general
interest, and in case it sparks a bright idea somewhere.
I thought a little bit about what you could do in terms
of algorithms, to try and reduce the n^2 behavior (for
the hamming computation itself). The only thing I could
come up with is to try to use the fact that "hamming
distance" actually is a distance:
hamming(a,b) + hamming(b,c) >= hamming(a,c)
hamming(a,b) - hamming(b,c) <= hamming(a,c)
So quick lower and upper bounds might be computed, once
we get started with some values.
For example, say the first string is A, and we remove it
from the list. Then say that we store the actual hamming
distance to A along with each of the rest of the strings
(whether or not the distance is < x). For the second step,
pick the string that was closest to A; say that is B. Now
for each string C, let B.dist and C.dist be the actual
computed distances to A. Then the hamming distance from
B to C is between |B.dist - C.dist| and B.dist + C.dist.
This range may include x, in which case we have to compute
the actual hamming distance anyway; but it may not, in
which case we already know what to do about C.
I haven't gone on, however, to see what the heck to do
for the third step. Maybe some dynamic programming idea
will help, but I can't see a way to be sure and do well.
Actually the method above doesn't look like it is going
anywhere. The big problem, however, is that depending on
x and n and the actual strings, it could be necessary to
compute all the actual hamming distances anyway! (Just
imagine a case where x is, say, 20, and every pair is
just about that distance apart, plus or minus 1 or 2.
I bet you could even construct such an example.)
So if there is some trick to do better, in the expected
case, I think it will have to be a trick that depends on
the answers to your first two questions above. Do you
see any more approaches?
JM
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: keysize for equivalent security for symmetric and asymmetric keys
Date: Thu, 07 Dec 2000 10:51:09 -0700
"Trevor L. Jackson, III" wrote:
<snip>
> The human body produces about one watt per pound. The Sun produces less than
> this. Since the Sun has a density below unity (it would float) it also produces
> less energy per unit volume.
Joke, right?
JM
------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: hardware RNG's
Date: Thu, 07 Dec 2000 11:49:35 -0700
Reply-To: [EMAIL PROTECTED]
John Feth wrote:
>It seems to me that the only cryptographically important attribute of a
random string is the lack of correlation at any >scale.
Somewhat more than this is necessary. The canonical example of
Champernowne's Number written in base 2 has lack of correlation at any
scale but it is not a random string. It is produced by concatenating the
integers: 1,10,11,100,101,110,111,1000... etc.
Actually one can concatenate the values of any integer-valued
polynomial, use any base, drop the leading digit, etc. The interesting
thing about these strings is that they satisfy the strong law of large
numbers in the sense that all k-tuples occure with the proper frequency.
------------------------------
From: Antonio Varni <[EMAIL PROTECTED]>
Crossposted-To: comp.security.misc,alt.2600.hacker,alt.security
Subject: Re: Encrypting messages in images??
Date: Thu, 07 Dec 2000 12:16:37 -0800
Cassj wrote:
>
[snip]
> For the latest in digital watermarking, check out http://www.digimarc.com.
About two years ago -- it was the case that the digimarc watermark was
rendered useless.
I remember (I think over at fravia.org) about how reversers found that
cracking the watermarking software was trivial -- and a hacked client
could be used to erase and re-create any watermark on any image. Thus
-- an image stamped with a Digimarc watermark __meant nothing__.
Digimarc was really not pleased by all this either.
I would bet the same issues remain today.
>
> Hope this helps. Steg is very cool, and you can finds lots more through your
> favorite Search engine.
>
> -Cass
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Hamming Distance
Date: Thu, 07 Dec 2000 19:12:17 GMT
Paul Crowley <[EMAIL PROTECTED]> wrote:
> How many strings do you tend to have? What does x tend to be? If x is
> really small (like 3 or something) then you could speed things up by
> throwing the strings into buckets based on the first byte, then only
> comparing those strings which are close enough in the first byte. In
> any case, you can abandon the software population count as soon as the
> Hamming threshold is crossed.
Thank you muchly, that's definately worth thinking about. As you
probably suspected, the number of strings tends to be large. Ideally
I'd like it to be scalable up to at least 100k. x is, of course,
tunable, but tends to be small, around 25.
I've wrestled with the idea of reorginising the list to speed up the
search before, but nothing seems to leap to mind. For example, it's
unlikely that a target string with a high population count will ever
be within such a small distance of one with a low population
count. Unfortunatly, I have yet to find any work relating the hamming
distance between two strings to their population counts. The boundry
conditions are clear, a string with a population of 256 will not be
within range of one at 0. Nor will the distance between say strings
with populations of 250 and 10. The problem is, as soon as I nail down
the break off point for any value of x by trial and error, you lose
the ability to change x. Is there any equation at all governing this
mess?
> There are a variety of techniques for fast population counting, though I
> can't remember them off the top of my head. GNU MP
> (http://www.swox.com/gmp/) includes a "population count" function which
> is probably implemented very efficiently, so you could steal their
> code. It includes the comment
Unfortunatly (well, I suppose there are worse things), the population
count has been surprisingly fast so far. I'd assumed it would be a
bottleneck, and I'd just end up recoding it into something
faster. However, the profile indicates that reducing the amount of the
list scanned each iteration would be a much bigger win.
--
Matt Gauthier <[EMAIL PROTECTED]>
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: How to embed a key in executable code?
Date: Thu, 07 Dec 2000 11:30:46 -0800
Tim Tyler wrote:
> David Schwartz <[EMAIL PROTECTED]> wrote:
> : Paul Rubin wrote:
> :> I wouldn't use the term "easy" but software vendors haven't yet come
> :> up with a software-only copy protection scheme that can't be cracked
> :> with enough effort. [...]
> : Creating a software-only copy protection scheme is actually _easier_
> : than hiding a private key in your programs. Software-only copy
> : protection can be achieved by placing a public key in your code. It
> : doesn't matter if someone can read that key because it's a public key,
> : that wouldn't help thbem at all to create their own forged credentials.
> : So software-only copy protection doesn't require hiding anything, it
> : just requires preventing a public key from being tampered with. Tamper
> : proofing is _much_ easier than hiding.
> Can you describe what this does in more detail?
> How does embedding a public key in software prevent that software from
> being copied?
The key would be used to validated some set of credentials that decided
when the software could run and when it couldn't. A common copy
protection technique is to use signed 'license files'. The simplest way
to break it is to create your own license file through some sort of key
generator.
If the encryption/signature technique used is symmetric, then the key
must be in the code, and if you can find it, you can create your own
license files. If the encryption/signature technique is not, then the
key isn't in the code, and so you can't find it no matter how hard you
look.
That means you can't generate your own keys and instead have to modify
the program. Thus the program only has to resist tampering, as opposed
to hiding information it's using.
DS
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: How to embed a key in executable code?
Date: Thu, 07 Dec 2000 20:24:20 GMT
I can describe what it does fairly well I believe. It fails. If there
is internal data (or code) that is used for verification, it is a
simple matter for someone with a debugger and a lot of time to locate
the data, and overwrite it with whatever they want.
I believe the idea was to embed the public key, keep the private key
with you, when someone purchases a license, generate their license
information and sign it with the private key. The program verifies that
the signature actually verifies, if it does then obviously it's a valid
license, then you verify the signed data actually matches the computer
the program is running on. I've already covered how to defeat it.
Joe
"Tim Tyler" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Can you describe what this does in more detail?
>
> How does embedding a public key in software prevent that software from
> being copied?
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Fips Pub 140-1 and RNG
Date: Thu, 07 Dec 2000 20:50:23 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> [EMAIL PROTECTED] wrote:
>
> : Also, what is the relevance of these tests being done on power up as
> : mentioned in the FIPS 140 document ?
>
> Random numbers are often required for "Power On Self-Test"s (POSTs).
> Could that have been what the document was talking about?
> --
> __________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
> |im |yler The Mandala Centre http://mandala.co.uk/ Free gift.
>
It was specified to do on power up, because all register/or flipflop in
the hardware are usually forced to a known state. Thus a randome
number generator can generate the same number or the same sequence at
power-up.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "KENNETH H MARTIN" <[EMAIL PROTECTED]>
Subject: Modular arithmetic
Date: Thu, 7 Dec 2000 16:01:27 -0500
Please forgive my ignorance, but to decrypt an IDEA cipher
I need to find the multiplicative inverse of a 16-bit number,
Mod 66537. What if there are no inverses less than the
modulus, say for a relatively prime number like 5? Is there
a trick to this?
------------------------------
From: [EMAIL PROTECTED]
Subject: RSA Coding Assistance
Date: Thu, 07 Dec 2000 20:56:27 GMT
I'm looking for a "simple" RSA implimentation to work with. By simple,
I mean that in the application, all I have to do is include 1 .h file
to accomplish everything. I'm confident that I can write it, but why
reinvent the proverbial wheel?
Restrictions:
1.) must be in C
2.) must be relatively efficient (Considering it's assymetric)
3.) must not be a library (I can't use them in the project, have to
static-ly include the files and compile them in)
4.) must be relatively compact (I really don't need 3des,
MD5/4/3/2/1/0/-1... Unless again, the RSA stuff is easily exctractable).
5.) preferibly well documented (Not high priority, but nice :)
6.) must be freely available. (I can't afford to pay royalties :( )
I looked into cryptlib 3.0, but I had all sorts of problems. Namely, I
couldn't easily extract *just* rsa from it. There were just so many
shot-gunned dependencies that were causing me some serious headaches.
Thanks in advance for the help
--Dave Weber
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Byte-oriented Huffman coding (lit.)
Date: Thu, 07 Dec 2000 22:28:58 +0100
Sometime ago there were quite an amount of discussions
related to Hoffman encoding. Those interested in compression
may like to read the following article in IEEE Computer,
Nov. 2000:
N. Ziviani et al., Compression: A key for next-generation
text retrieval systems.
Instead of the binary coding of characters of the original
Huffman scheme, the authors employ a byte-oriented coding
(i.e. the degree of each node is 256) of words and give
results (albeit on a very huge text base) showing that their
techniques lead to only a slight degradation of the
compression ratio but much less decompression time (with
almost the same compression time.) Other advantages accrue
to text retrieval.
M. K. Shen
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: RSA Coding Assistance
Date: 07 Dec 2000 13:43:20 -0800
[EMAIL PROTECTED] writes:
> I'm looking for a "simple" RSA implimentation to work with. By simple,
> I mean that in the application, all I have to do is include 1 .h file
> to accomplish everything. I'm confident that I can write it, but why
> reinvent the proverbial wheel?
>
> Restrictions:
> 1.) must be in C
> 2.) must be relatively efficient (Considering it's assymetric)
Can you say what hardware it will run on, and what the performance
requirements are? Your restrictions are in conflict with each other.
An efficient implementation is necessarily fairly complicated, and
uses some assembly code. You can do a simple implementation in C but
it will be at least 10x slower than an optimized implementation.
With today's hardware though, that's probably good enough for many purposes.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Modular arithmetic
Date: Thu, 07 Dec 2000 22:51:54 +0100
KENNETH H MARTIN wrote:
>
> Please forgive my ignorance, but to decrypt an IDEA cipher
> I need to find the multiplicative inverse of a 16-bit number,
> Mod 66537. What if there are no inverses less than the
> modulus, say for a relatively prime number like 5? Is there
> a trick to this?
What do you mean? 66537 is prime. Hence any number in
the range 1 - 66536 has an inverse mod 66537. (If you
find one larger than 66537, then reduce it mod 66537.)
M. K. Shen
------------------------------
From: "Michael Scott" <[EMAIL PROTECTED]>
Subject: Re: Modular arithmetic
Date: Thu, 7 Dec 2000 21:56:31 -0000
Because p=65537 is prime, every number from 1 to p-1 has a unique modular
inverse. For example 1/5 mod 65537 = 26215. Because 5*26215 = 1 mod 65537.
Mike Scott
"KENNETH H MARTIN" <[EMAIL PROTECTED]> wrote in message
news:90otoo$1js8$[EMAIL PROTECTED]...
> Please forgive my ignorance, but to decrypt an IDEA cipher
> I need to find the multiplicative inverse of a 16-bit number,
> Mod 66537. What if there are no inverses less than the
> modulus, say for a relatively prime number like 5? Is there
> a trick to this?
>
>
>
------------------------------
From: John <[EMAIL PROTECTED]>
Crossposted-To:
alt.cracks.nl,alt.nl.telebankieren,nl.comp.crypt,nl.financieel.bankieren,nl.juridisch
Subject: Re: weten we die PIN?
Date: 7 Dec 2000 22:09:58 GMT
David Dylan wrote:
>
> On Wed, 06 Dec 2000 10:32:38 GMT, [EMAIL PROTECTED] (David Dylan) wrote:
>
> PS: Iemand enig idee waar dit wordt bijgehouden? Bij de bank of op de
> automaat?
Geen van beiden, het wordt namelijk op de kaart zelf bijgehouden.
Gr, John
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: Hamming Distance
Date: Thu, 7 Dec 2000 16:26:59 -0500
Reply-To: "Matt Timmermans" <[EMAIL PROTECTED]>
<[EMAIL PROTECTED]> wrote in message
news:liRX5.80386$[EMAIL PROTECTED]...
> I've wrestled with the idea of reorginising the list to speed up the
> search before, but nothing seems to leap to mind. For example, it's
> unlikely that a target string with a high population count will ever
> be within such a small distance of one with a low population
> count. Unfortunatly, I have yet to find any work relating the hamming
> distance between two strings to their population counts. The boundry
> conditions are clear, a string with a population of 256 will not be
> within range of one at 0. Nor will the distance between say strings
> with populations of 250 and 10. The problem is, as soon as I nail down
> the break off point for any value of x by trial and error, you lose
> the ability to change x. Is there any equation at all governing this
> mess?
HDist(A,B) >= |Pop(A)-Pop(B)|
This is so simple that it will probably be worth something to sort the list
by population count. Bear in mind, though, that there are a whole lot more
256-bit strings with a population count of around 128 than there are with
counts near 0 or 256, so you might not get the terriffic improvement you
expect.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Idea for ciphering? (correction w/ addition)
Date: Thu, 07 Dec 2000 23:33:49 +0100
John Myre wrote:
>
[snip]
> Any stream cipher can be modelled as a "black box": a
> plaintext character comes in, a ciphertext character goes
> out, and something has happened to the state of the box
> (invisibly). The state change could be dependant on the
> plaintext character, or on the ciphertext character, or on
> both, or neither.
>
> RC4 is an example of where the state change is independant
> of any input (plaintext) or output (ciphertext). The way
> it works is to produce a bunch of pseudo-random bytes, as
> it sequences through its state space; then the bytes are
> simply XOR'd with the message data to encrypt or decrypt.
> A lot of stream ciphers work this way.
>
> Consider, on the other hand, something like 8-bit CFB mode
> for a block cipher. This is now a stream cipher, as it
> encrypts one byte at a time. After each step, the latest
> output (ciphertext byte) is combined with the state. Of
> course, this means that decryption is slightly different;
> you still need to feed back the ciphertext, but that is
> now the input instead of the output.
>
> Other examples abound. My original point was just that,
> for essentially any stream cipher, you could find a way
> to explain it in terms of the state machine model. You
> just need to figure out what part is the "state", what
> part is the "output function" (i.e., input + state =>
> output), and what is the "state transition" function.
>
> Although the state transition is defined abstractly in
> terms of a table (the STT), that doesn't mean it has to
> actually be implemented by a stored table. It could also
> be implemented in terms of computation: mathematical
> formulas, decision points in the code, some tables, and
> so forth. Similarly, the "output function" could be
> implemented however we like. Therefore, we have a lot of
> flexibility in trying to describe things (like stream
> ciphers) in these terms.
I like to remark that it is also possible to arrange to
have some parameters of a block cipher be varied
dynamically dependent on the processing so far done.
Thus variability is achievable generally.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED]
Subject: breaking rsa knowing the original text
Date: Thu, 07 Dec 2000 22:32:35 GMT
Hi, I'm trying to figure out if it is much simpler to
break RSA knowing the original text and the encrypted text.
I mean, if some knows the original and the encrypted data
how easy will be to get the key ??
thanks in advance
Jorge
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
** 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
******************************
