Month: July 2016

ASN.1 buffer overflow puts networks at risk

An ASN.1 vulnerability has been found in a security advisory of 7/18 here. It has to do with length bounds checking in the LTV triplet.  A fix is provided but updating it on a large number of GSM devices is not practical. “It could be triggered remotely without any authentication in scenarios where the vulnerable code receives and processes ASN.1 encoded data from untrusted sources, these may include communications between mobile devices and telecommunication network infrastructure nodes, communications between nodes in a carrier’s network or across carrier boundaries, or communication between mutually untrusted endpoints in a data network.”

A discussion at Arstechnica here, brings up a real exploit against GSM base station software, that operates below the application layer and so can be exploited against a  large number of devices.

A quote from the paper – “When GSM radio stacks were implemented, attacks against end devices were not much of a concern. Hence checks on messages arriving over the air interface were lax as long as the stack passed interoperability tests and certifications. Open-source solutions such as OpenBTS (Base Transceiver Station)allow anyone to run their own GSM network at a fraction of the cost of carrier-grade equipment, using a sim- ple and cheap software-defined radio. This development has made GSM security explorations possible for a significantly larger set of security researchers. Indeed, as the reader will see in the following, insufficient verification of input parameters transmitted over the air interface can lead to remotely exploitable memory corruptions in the baseband stack.”

The cellular baseband stack of most smartphones runs on a separate processor and is significantly less hardened, if at all. GSM does not provide mutual authentication, there is no protection against fake BTSs.

Self-Signed Certificate with OpenSSL genrsa and primality testing 

Steps to generate a private key, a cert-signing request and a self-signed cert

# openssl genrsa -out privatekey.pem 2048
Generating RSA private key, 2048 bit long modulus
e is 65537 (0x10001)

# openssl req -new -key privatekey.pem -out certrequest.csr

# openssl x509 -req -in certrequest.csr -signkey privatekey.pem -out certificate.pem

If you want to create a p12 file which includes both private key and pub key

# openssl pkcs12 -export -out keyStore.p12 -inkey  privatekey.pem -in certificate.pem

In case the cert is issued by an external CA server, there may be a conversion involved.

How are the large primes generated in genrsa ? 2048 bits is a ~617 decimal digit integer. The probability of it being a prime is ~1/ln(N) or ~1/1420, by PNT. Actually since we are looking for 2 primes of 1024 bit length, the prob is ~1/710 for each.

>>> math.log(pow(2,2049)) # natural log

From genrsa doc, a “.” represents each number which has passed an initial sieve test, “+” means a number has passed a single round of the Miller-Rabin primality test. The primality testing idea for big numbers is to repeatedly check for a condition satisfied by primes, such as a^p mod p = a mod p, for different a, until a probabality bound is met. The key is that a^p mod p can be calculated relatively easily even if p is very large – and it is much easier to prove a number is prime with high probability, than to factorize it (so far).

The AKS test uses a different property of primes, that binomial coefficients of an pth power are multiples of p iff p is prime.

Putting some traces, in BN_GENCB_call, shows it generates a number of random numbers and checks them for primality using a sieve method. Surprising that the number of iterations is as small as 13 below.  bn_prime.h has a table of the first 2048 primes and it tests the random number against them to find the remainders. If unsuccessful, it adds 2 to the random number to arrive at an adjacent number to test, recalculates the remainders by adding 2 to the original remainders and modding by corresponding prime. If any of the mods against the first 2048 primes is zero or one (why one ? T=p(x.2^k)+1), it moves to the next number. Basically the “.” above is printed only after this set of numbers along with the deltas have been tested, so it has tested many more numbers than 13. Once it finds a target which passes this sieve test it proceeds with a fast test and the MR test. The dot, plus and star are printed in genrsa_cb calback in apps/genrsa.c .

bn_prime.c 123 /* The quick sieve algorithm approach to weeding out primes is Philip Zimmermann’s, as implemented in PGP.  I have had a read of his comments and implemented my own version.*/

rt: starting BN_generate_prime_ex loop: 1024 safe=0 checks=3

checking probable prime

checked probable prime

. rt2: calling cb 0 12  type2 1

checking fast

rt: starting BN_generate_prime_ex loop: 1024 safe=0 checks=3

checking probable prime

checked probable prime

. rt2: calling cb 0 13  type2 1

checking fast

+ rt2: calling cb 1 0  type2 1

+ rt2: calling cb 1 1  type2 1

+ rt2: calling cb 1 2  type2 1

rt2: calling cb 3 1  type2 1

e is 65537 (0x10001)

crypto/bn/bn_x931p.c   BN_GENCB_call(cb, 3, 0)  is in BN_X931_derive_prime_ex().

X931 is short for ANSI X9.31-1998, discussed here and here and here. A discussion on strong primes here. Some factor methods are in

From doc/man3/BN_generate_prime.pod, (src)

If safe is true, it will be a safe prime (i.e. a prime p so that (p-1)/2 is also prime).

The PRNG must be seeded prior to calling BN_generate_prime_ex().

The prime number generation has a negligible error probability.

BN_is_prime_ex() and BN_is_prime_fasttest_ex() test if the number is prime.

The following tests are performed until one of them shows that is composite; if passes all these tests, it is considered prime.

BN_is_prime_fasttest_ex(), when called with do_trial_division == 1, first attempts trial division by a number of small primes; if no divisors are found by this test and cb is not NULLBN_GENCB_call(cb, 1, -1) is called.

If do_trial_division == 0, this test is skipped.

Both BN_is_prime_ex() and BN_is_prime_fasttest_ex() perform a Miller-Rabin probabilistic primality test with nchecks iterations. If nchecks == BN_prime_checks, a number of iterations is used that yields a false positive rate of at most 2^-80 for random input.

When the source of the prime is not random or not trusted, the number of checks needs to be much higher to reach the same level of assurance: It should equal half of the targeted security level in bits (rounded up to the next integer if necessary). For instance, to reach the 128 bit security level, B should be set to 64.

bn/bn.h has a comment referring to a Table 4.4 in Handbook of applied cryptography, original paper “Average case error estimates for the strong probable prime test”, by Damgard, Landrock, Pomerance, . The table shows that the number of required tests goes down from 18 for a 150bit number to 3 for an 850bit number, down to 2 for a number greater than 1300 bits. For a 2048 bit pubkey, it factors two 1024 bit primes, which means 3 + tests per prime (seen above). By accounting for Carmichael numbers and some really complex math, the paper brings down the number of Miller-Rabin tests required to a low number.

These numbers were updated in July 2018 commit with a link to and a comment –

“Make number of Miller-Rabin tests for a prime tests depend on the security level of the prime. The old numbers where all generated for an 80 bit security level. But the number should depend on security level you want to reach. For bigger primes we want a higher security level and so need to do more tests.”