Why Doesn’t Code Have a Pen Test When Compiling?

Why Doesn’t Code Have a Pen Test When Compiling? Here’s Project Paranoid Outlining RSA Weaknesses (RAMBUS)

I have never understood why many developers never use Pen Testing tools to reveal security problems in their code. Most just depend on the compiler to spot problems. In fact, a major problem in using Rust, is that developers often care little about how their data is used in memory and in-process. For many, the Pen Test is a step after coding, and not with it. Basically, it is close the door after the horse has bolted.

Hopefully, with the rise of ChatGPT, there might be an improvement in testing in this area. One great tool from Google is Project Paranoid [1] and which allows developers to check for a range of cryptographic weaknesses [here]:

The library is created by two leading cryptographers: Pedro Barbosa and Daniel Bleichenbacher. So, let’s look at one of the examples.

Fermat’s factorization

Pierre de Fermat defined a factorization method which could factor prime number factors if these prime numbers were close to each other. In RSA, we use a modulus (N) and which is the multiplication of two prime numbers (p and q). If these prime numbers are close to each other, then N can be factorized, and the RSA methods can be easily broken.

In March 2022, it was discovered that a Rambus cryptographic module was selecting a prime number and then selecting another which was relatively close. These led to vulnerabilities in a number of printers which used Rambus module [here]:

It affected Fuji Xerox and Canon printers for the keys that generated a CSR (Certificate Signing Request).

Fermat’s method

In this case, we will use Fermat’s method to factorize a modulus and where the prime numbers are within ²¹⁰⁰ of each other. We will also try two random prime numbers and see if we can factorize. With Fermat’s factorization algorithm, we assume that two large prime numbers can be written as:

N=(a−b)(a+b)

We then have the first prime as a−b and the second one as a+b. If the prime numbers are close, the value of a will be close to the square root of N. We could thus guess the value of a from the square root of N and then increment the value of a and for each guess, we take:

b²=a²−N

If the result is then a square value, we have the right values for a and b, and compute:

p=a+b

and:

q=a−b

The basic algorithm is then [taken from [here]:

def FermatFactor(n: int, max_steps: int):
    if n % 2 == 0:
        return 2, n // 2    a = gmpy2.isqrt(n)    if a * a == n:
        return a, a    a += 1  # ceil(sqrt(n))
    b2 = a * a - n    for _ in range(max_steps):
        if gmpy2.is_square(b2):
            return a + gmpy2.isqrt(b2), a - gmpy2.isqrt(b2)        b2 += a
        a += 1
        b2 += a
    return None

In this case, we use gmpy2 to compute the integer square roots, and return None if we cannot factorize the modulus.

Code

The following is an outline of the code [here]:

# Some code derived from https://github.com/google/paranoid_crypto/
import gmpy2
from gmpy2 import mpz, xmpz
import random
import sysclass RSAKey:
    def __init__(self): # constructor method
      e=bytearray(0)
      n=bytearray(0)  def Int2Bytes(int_val: int):
    return int.to_bytes(int(int_val), (int_val.bit_length() + 7) // 8, 'big')def Bytes2Int(bytes_val: bytes) -> int:
    return int.from_bytes(bytes_val, 'big')def FermatFactor(n: int, max_steps: int):
    if n % 2 == 0:
        return 2, n // 2    a = gmpy2.isqrt(n)    if a * a == n:
        return a, a    a += 1  # ceil(sqrt(n))
    b2 = a * a - n    for _ in range(max_steps):
        if gmpy2.is_square(b2):
            return a + gmpy2.isqrt(b2), a - gmpy2.isqrt(b2)    b2 += a
    a += 1
    b2 += a
    return Nonensize=512
rsa_key1=RSAKey()
max_steps = 2if (len(sys.argv)>1):
	nsize=int(sys.argv[1])print(f"Prime number size: {nsize} bits\n")
p = gmpy2.next_prime(random.getrandbits(nsize))
q = gmpy2.next_prime(p + 2**100)rsa_key1.n=p * q 
print(f"== Try with p and q close to each other (within 2^100)==\n")
print(f"N={rsa_key1.n}")result = FermatFactor(rsa_key1.n, max_steps)try:
    if ((result[0] * result[1])==rsa_key1.n):
        print("Able to factor")
except:
    print("Success: Not able to factor")
p = gmpy2.next_prime(random.getrandbits(nsize))
q = gmpy2.next_prime(random.getrandbits(nsize))rsa_key1.n=p * q 
print(f"\n== Try with p and q as random primes==\n")
print(f"N={rsa_key1.n}")
result = FermatFactor(rsa_key1.n, max_steps)
try:
    if ((result[0] * result[1])==rsa_key1.n):
        print("Able to factor")
except:
    print("Success: Not able to factor")

A sample run is [here]:

Prime number size: 1024 bits== Try with p and q close to each other (within 2^100)==N=8704309713329794391787624088108390166615849526057044757655516652810445455914313355842186472690420915893317060751453277778542906673834732917538129080446534899759462232344761961777709717348529328041820323137303783139690224592767828846152165399673670470727994987601110757086145476515673676804574894909120950870030110882550773368703788956669391140946224924453861287632727300274444819159716032656503839867275866813467907906743755263158792652129833239456645743597048914452179624531058777426167679242043718835427173969255560282059183112627328833413034912545460129076385894403425462913104262356751319381061567320897200070529
Able to factor== Try with p and q as random primes==N=2806536120217532769357004324632105544640202339383143017293712949521245614722233021581036516596071505250034801057287477157268160558698601789455741407795165358191639339558213929886161439925139061910830407043601191511045492966225905624106334993942778987072311536110374325366438290949898913469379076821547872825580262409268517753058270215937300766583709371380070288391119223969477986239799834024409957102030291794504709067491856986569899643167245375608838598471909576619845735607779704575879673411005592241759833515604191144488269194649614610246103730921220483235606158755534260032861437892169311214665093388070677322881
Success: Not able to factor

Conclusion

You must worry when such a novice mistake is created by an experienced team and used within commonly used products. I

References

[1] Barbosa, Pedro and Bleichenbacher, Daniel, Paranoid Crypto, Aug 2022, https://github.com/google/paranoid_crypto