Hello readers,

Lately i came across a piece of software that had an interesting piece of build in cryptography. My intention is to understand how it works and to know if it relies on a 'standard' crypto algorithm or that it is something more fancy.

First an introduction (coded in Java, i left most pieces out):

-----

Secure Hash Algorithm (SHA-1) hashes the data of three files thus creating the following constant values:
* serenv1 (1024 bit) - prime number
* serenv2 (128 bit) - prime number
* serenv3 (1024 bit)
* serkey (1024 bit)
* array - with 2^14 128-bit positive numbers

After some playing around the input message is encrypted (in a reversible way) to a 144 bit number. The last 14 bit form the index into the array (bi2). Furthermore the most significant bit is removed resulting in bi4 (129 bits number).

Note: modInverse: (x xor -1) % y
modPow: (x ^ z) % y (where ^ stands for power, not XOR)

BigInteger bi2 = index;
BigInteger bi4 = 129bit_number;
BigInteger bi5 = array[index_array];

BigInteger bi6 = bi4.modInverse(serenv2);
BigInteger bi7 = bi2.multiply(bi6).mod(serenv2);
BigInteger bi8 = bi5.multiply(bi6).mod(serenv2);
BigInteger bi9 = serenv3.modPow(bi7, serenv1).multiply(serkey.modPow(bi8, serenv1)).mod(serenv1).mod(serenv2);

if(bi5.equals(bi9))
//Bingo! Free beers if the index is between 0 and 16000

-----

my first thoughts were a combination between SHA-1 and RSA. the extensive use of modPow and the use of modInverse gave me that idea, but since the modInverse operation in RSA is only used when calculating the private exponent i'm slightly confused. i think the multiply operations have something to do with the input message being bigger then 128 bits so it had to be 'hacked to pieces'.

if there anyone that can explain to me what is happening here (in crypto language, i can see what happens to the values ). every scrap of information would be helpfull!

regards & thanks in advance!
rhythm

OK, first thing I notice is that modInverse is horribly misnamed if it really is (x xor -1) % y. Looks like some clueless newbie took the notation for exponentiation to mean xor.

Second:

SHA doesn't just spit out prime numbers; were the first two run through a primality test or something?

Third: the notation is kind of obtuse. Does

bi4.modInverse(serenv2)

mean

(bi4 XOR -1) % serenv2

or

(serenv2 XOR -1) % bi4

Also,

serenv3.modPow(bi7, serenv1).multiply(serkey.modPow(bi8, serenv1)).mod(serenv1).mod(serenv2);

looks like it's a bunch of operations in a row. Can you rewrite the code so there's only one operation on a line. If you could use more common notation (like x % y), that would help, too.

Fourth: as I recall, BigIntegers don't have a specific bit length. This isn't usually an issue, but here you're XORing with -1, which is a kluge. -1 is implicitly cast to an unsigned something, usually one less than a power of two. Which power of two? It matters because you're doing things modulo some other number.

1. thanks for your reply, i'm the clueless newbie. modInverse (as you already mentions) does x.pow(-1) % y and has nothing to do with XOR. forgive me my mistake. i hope that clears things up.

2. to simplify things i left out all the code that deals with reading in the files, handing them over to the messagedigest algoritm and creating the message digests. point is that the output is the constants i mentioned. of which the first two are primes with a probability of (1 - 1/1.000.000).
a previous version of this program used the same algorithm with different source files and serenv2 was a prime number too. so i don't think it's coincedence. serenv1 on the other hand, wasn't a prime in the previous version.

i can post the implementation of the algorithm if that would be of any help, just let me know.

3. example:
bi4.modInverse(serenv2) does (bi4.pow(-1)) % serenv2
(just like it's used creating the private exponent in RSA)

rewritten code:
BigInteger bi2 = index;
BigInteger bi4 = 129bit_number;
BigInteger bi5 = array[index_array];

BigInteger bi6 = bi4.modInverse(serenv2);
BigInteger bi7 = bi2.multiply(bi6).mod(serenv2);
BigInteger bi8 = bi5.multiply(bi6).mod(serenv2);

BigInteger bi9 = serenv3.modPow(bi7, serenv1);
BigInteger bi10 = serkey.modPow(bi8, serenv1);
BigInteger bi11 = b9.multiply.b10;
BigInteger bi12 = bi11.mod(serenv1).mod(serenv2);

4. again sorry for the confusion ;-)

OK. It makes a lot more sense now.

The only hard stuff I see going on is perhaps discrete log. The whole system isn't anything I've seen before. The modular inverse is used in such a way that it has no real bearing on the problem (unless serenv2 divides serenv1 - 1; then there might be something to it).

Discrete log is the following problem: It's easy to compute y where y=a ^ x mod n given a,x,n. It's hard to compute x given a,y,n.

What information are you allowed to alter in this system? You mentioned an "input message". What is that? Also, what are the three files being hashed?

Details about the SHA-1 procedure, "serial.dat" is 262,144 bytes, "serial.env" 545 bytes, "serial.key" 329 bytes. The author changes his codemechanism every version by replacing the files with other files of the same size.



the array is created this way:


bi2 & bi4 can be choosen freely (they are derived from the serial you entered). it's easy when given bi2 and bi4 to reconstruct the serial entered by you.

furthermore there's a line of text in the readme that says something like 'contains code licensed by rsa laboratories' and i think he aint talking about SHA-1.

hope things are more clear now!

I don't understand what the ObjectInputStream and DigestInputStream functions are doing.

I'm assuming that DigestInputStream generates a string of random numbers based on the hash of a file, and that ObjectInputStream allows you to read in data from the random stream and cast it to whatever type you want.

I'm curious, because I don't see any primality testing. If the numbers just happen to be prime as they come out of the random number generator, then we're in luck.

That means the creator of the files must have chosen the files carefully so that the random numbers came out to be primes. That's not particularly hard to do, so it wouldn't be a lot of work on his part. If so, it means that if we change the files, the numbers won't be prime anymore and we can break the crypto.

But, like I said, I don't understand what they do, so I could be completely wrong.

MessageDigest (http://java.sun.com/j2se/1.4/docs/api/java/security/MessageDigest.html) for some more information about SHA-1, from there you can click to the DigestInputStream method.

i'm confident that the author chose his files in such a way that the 128 bit number is a prime, i'm not sure about the 1024 bit number though ... could be by accident, but since he seems like a clever guy i doubt it.

replacing the files is a possibility, just don't use the files of any previous versions of the software because checks are made if you do. patching this scheme shouldn't be too hard, but that's not my point of interest. i want to understand every single bit of this piece of crypto :-)

/me still wonders about the link with RSA ...

maybe it's usefull to note that i do have valid keys in combination with other files. didn't help though; and believe me, i had some sleepless nights over this one

I was wrong about what DigestInputStream does, but things still might work out OK. DigestInputStream computes the hash of data passing through the stream and passes the data out the other side. So it's not the hash that's a prime number; the prime number is stored in the file.

The hash is probably used in a checksum somewhere; it's not referenced in the code you posted (to retreive the hash you call getMessageDigest() ). If that's true, that will be a virtually impossible problem to keygen. If the hashes of the files aren't checked anywhere, then calculating the hashes was a waste.

Ignoring that problem, if we can change the moduli to any number we want (by editing the files), then we can pick numbers for which calculating discrete log is much easier.

Do you know if getMessageDigest is referenced anywhere?

*does some codedigging* (i HATE obfuscators)



badbytes is a predefined array ... so are you saying that the only reason for SHA-1 here is to calculate a hash to check for the right files?

Maybe it has something to do with: RSAES-OAEP (RSA Encryption Scheme - Optimal Asymmetric Encryption Padding) or RSASSA-PSS (RSA Signature Scheme with Appendix - Probabilistic Signature Scheme). I don't have a clue what they are, diving into it while you're reading this.

Thanks for the help so far, although i'm still puzzled i have the feeling that i'll get a good understanding of this one.

Well, perhaps not the only reason, but at least one of them.

Looks like you're out of luck as far as keygenning this one. If you could change the primes, there'd be some hope in solving the discrete log problem, but with the hash check in there, you're pretty much stuck.

Patching it or using a valid serial number are your only options as far as I can tell.

Whatever they're using right there, it's not RSA. RSA does stuff modulo composite numbers, not primes.