Bug of EMSA-PSS

I have just fixed the bug in EMSA-PSS verify. It has been there since version 0.2.x.

The problem was test case for EMSA-PSS verify failed *sometimes*, like once in 100 times or once in a month. It was really annoying and made this procedure unreliable.

Because of this random frequency, I suspected it was random number generator. In the test case, it uses secure random number generator so that it generate different number each time. (well, thank god I used secure random, otherwise I would never notice this bug.)

So first step to fix this bug was create a proper (improper?) state of PRNG. To create it, I made this code;

(import (crypto) (math) (getopt))

(define key-pair (generate-key-pair RSA :size 512 :prng (pseudo-random RC4)))
(define valid-rsa-message (string->utf8 "test message"))

(define prng (pseudo-random RC4))
(with-args (command-line)
    ((c (#\c "count") #t "1"))
  (let ((count (string->number c)))
    (do ((i 0 (+ i 1))
  (r (read-random-bytes prng 100) (read-random-bytes prng 100)))
 ((= i count) r))))

(let* ((rsa-sign-cipher (cipher RSA (keypair-private key-pair)))
       (rsa-verify-cipher (cipher RSA (keypair-public key-pair)))
       (em (sign rsa-sign-cipher valid-rsa-message :prng prng)))
  (verify rsa-verify-cipher valid-rsa-message em))

And this shell script;

#!/bin/sh

for i in `seq 1 $1`
do
    count=`expr $i + 100`
    echo $count
    `sash -Lext/crypto crypto.scm -c $count`
done

Then ran the script and check which number was the key number! After the inspection, the number was 181.

Now, it's time for debug. once I could find the PRNG state, it was really simple to fix. The problem was the signed message's first 2 bytes. RSA operation deletes left most 0's so verify procedure needs to add removed 0's in front of the message. However previous implementation did not add more than 2 zeros. That was the problem.
So I modified to add propert 0's in front of the message, and now it works!

I hope Sagittarius is now a bit more reliable. Even though I have no idea if it was the only problem that causes test case failed.