What purpose for using randomly generated KeyPair to do sha256WithRSA signing?

Question

I'm reversing an android apk, it uses http as protocol, each http request contains a timestamp and a signature, for example:

http://x/req?....&timestamp=1501234567890&signature=....(256-byte rsa signature of timestamp '1501234567890')

The param signature is sha256WithRSA signature of timestamp(1501234567890). I guess the reason is that it guarantees the packet works only in a period of time, and user cannot modify the timestamp because it won't pass the signature verifying.

But the strange thing is that the apk uses a randomly generated RSA KeyPair for signing the timestamp. The apk generates the KeyPair when it is launched the first time, I understand the RSA verification requires public_key, but apk doesn't send the public_key to server(the server won't know the public_key). How does server verify it?

The apk generates the KeyPair like:

Calendar cal = Calendar.getInstance();
Date now = cal.getTime();
cal.add(Calendar.YEAR, 1);
Date end = cal.getTime();

KeyPairGenerator kpg = KeyPairGenerator.getInstance("RSA", "AndroidKeyStore");
kpg.initialize(new KeyPairGeneratorSpec.Builder(getApplicationContext())
        .setAlias(alias)
        .setStartDate(now)
        .setEndDate(end)
        .setSerialNumber(BigInteger.valueOf(1))
        .setSubject(new X500Principal("CN=test1"))
        .build());

KeyPair kp = kpg.generateKeyPair();

How does server verify the timestamp when it doesn't know the public_key?

Or do I miss something?

Answer 1

If the public key is never communicated to the server then it in all likelihood doesn't verify the time stamp. What it does is that it uses the signature as unique number. The input for the unique number is the build and the specific device, as the device is linked to the key pair.

This trick relies on the fact that PKCS#1 padded signatures are deterministic; if you sign the same message twice it will generate the same signature. This is not a required property of signature schemes in general; for instance RSA-PSS produces a randomized signature.