Originally Posted by gatomon
From the El Gamal paper "A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms"If any k is used twice in the signing, then the system of equations is uniquely determined and x [, the secret key,] can be recovered. So for the system to be secure, any value of k should never be used twice.
This means that each time they updated the time, they had to use a different "k" value (the signature has two parts, "r" and "s"; if "k" is the same then "r" is the same). This would be hard for them to do day in and day out for every time update request. I saw somewhere that someone had recorded Replaytv transactions over several years. If we collect that data, and perhaps find some other similar data, I would be surprised if every "r" value is distinct (you only need to find one instance of a repeated use of the "k" ("r") value.
Furthermore, the algorithm has three steps, The first:1) Choose a random number k, uniformly between 0 and p - 1, such that gcd(k, p - 1) = 1.
If they do this (i.e., randomly select k), then we have the "birthday paradox" on our side (http://en.wikipedia.org/wiki/Birthday_problem);
if they do something like a simple counter, I expect that this can be exploited.
PS: I won't give up until the fat lady sings...
One of the problems would be to actually determine when the common key was used, as well as a practical algorithm for actually using the weakness you mention in the paper, but that seems possible.
The vtime.pl (time getting) call looks like:
time: The time of the request in epoch format.
r: Random alpha-numeric string of length 25 to 35 characters.
According to the 2004 documentation from Josh Stubbs:
Response: The response contains normal http headers for a 200 OK response, along with data. This data appears to be an El Gamal hash. It is believed that the hash is of a concatenation of the time and random strings or a hash of a md5hash of the concatenation of the time and the random string.
By the way, somebody, or somebodies, should probably record some logs of the back-and-forth conversations between the Replay and the Mother Ship while it is still occurring normally, especially including the activation itself. I am worried about re-activiating if I ever have to install a new disk in my unit.
I once did that kind of logging in case this day arrived, but the disk I had the data on had a head crash.