Primality testing in Apple core…crypto

Today Apple publish their security update (https://support.apple.com/en-gb/HT201222) for macOS Mojave 10.14.1 and iOS 12.1, which includes changes to the way they test numbers for primality. In this post I will describe how easily we could produce composite numbers that fool Apple into classifying as prime what exactly has changed to the primality testing in this update.

I want this post to be as accessible as possible, so it is mainly targeted for people who want a flavour without having to read the full paper. If you are already familiar with the nature of primality testing, feel free to skip to the juicy parts in the section named: Library Structure or read the full version of the paper at https://eprint.iacr.org/2018/749.

Primality Testing

First we need to understand a little about how we decide if a number is composite or prime, and for this we perform what is known as primality testing. One quick way to get an intuition for what a primality test is, is to simply try and perform one yourself. If I ask you if 77 is prime, you’d probably think “no, it’s divisible by 7 and 11”, if I asked if 79 is prime, you might think, “well it’s not divisible by 3, 5 or even 7, so it probably is”- and you would be correct. What we’ve done here is trial division, a naïve, but effective approach for testing small numbers.

So what if I ask you if this number is prime?

122623673100774902819890811512093121818009864395929257382206929494220541500353599732762551419245399058398366502168963509640168639794202705645034115138272912046190084444976198156980059092407987735996562308131806635633617847615677949071026045920492821200676854540540234658043716124914438158326334228684623784307

This is quite a bit bigger than the first two examples, in fact this is a 1024 bit number and is more like the size we tend to think about in cryptography. So how would we test if this is prime? Well trial division here is pretty ineffective, as we would need to “trial-divide” around 2^512 primes in order to determine an answer. My next port of call would probably be to Google it, or to shove it in Wolfram Alpha. Sure enough this would give an answer, but what sort of test would they perform?

Although many deterministic tests do exist, but in practice (due to their efficiently and simplicity) we mainly use probabilistic testing methods, the most popular of which is the Miller-Rabin test. If we were testing this number in a cryptographic application, we can’t simply “Google-it” each time, and therefore we would most likely be using a cryptographic library to perform this testing. This is where Apple comes in.

Apple like many others, perform testing using Miller-Rabin. However, the implementation suffers from various pitfalls, which we can exploit in order to guarantee that composite numbers are falsely declared prime. Before we discuss these pitfalls in more detail, we’ll just recap how a Miller-Rabin test works.

Miller-Rabin

The Miller-Rabin primality test works by taking a statement we know holds for all primes and testing if this statement holds for a number n that we are testing. If n is composite, then this statement should cause a contradiction, and we have proof that n cannot be prime. If n is prime then the statement will always hold.

However, since this test is probabilistic, it has some degree of inaccuracy. It is well known that the test can incorrectly declare a composite number as prime, this happens with a probability of ¼ for a single test. It is therefore common to repeatedly test this number, each time with differing parameters, until we are satisfied with a small enough error rate. For example, 16 rounds of Miller-Rabin will have an error probability less than 1/4294967296.

One little bit of detail we’ll now dive into is how the parameters of each round of testing are chosen, as this will be important when we look at what Apple is doing. For those familiar with the test, we know that the statement Miller-Rabin is based on is the following:

With each round of testing we must choose a base a. If for this a, both conditions do not hold, then we know that n is composite, if either condition holds then we say than n is probably prime. If this just got too mathy for a blog post then just I'll give a nice intuitive example, so stick with me here...

For example, here is a diagram of the distribution of bases for n = 700. Think of it as a kind of lottery, where we draw t balls- each draw is equivalent to one round of Miller-Rabin testing. Each ball represents a base a, where drawing a red ball indicates that n is prime, and blue proves n to be composite.

Much like the real lottery, It is very important that the choice of balls is random. Otherwise, if we are able to predict before the draw which balls are chosen we can always “win” the lottery, i.e declare a composite number prime – Derren Brown style.

So we’re now ready to take a look at Apple’s primality test.

Library Structure

Apple provide a cryptographic library known as CommonCrypto to provide implementations of low-level cryptographic primitives. Many of the functions found in CommonCrypto actually rely on code found in Apple’s corecrypto – both are open source and available at https://developer.apple.com/security/.

A developer creating an application used in macOS or iOS may call upon these primality testing functions to verify the primality of numbers in cryptographic scenarios, so the accuracy of the test could have a significant impact on security of the application.

We’ll take a look at the primality test in both CommonCrypto and corecrypto since they are slightly different. Keep in mind that CommonCrypto is the flagship library offered by Apple, and corecrypto is the sort of backend code not directly called by the user. We note that these private Apple APIs 

are not recommended for use by 3rd party applications.

corecrypto

Apple's primality test can be found in corecrypto file ccz_is_prime.c, which contains the function ccz_is_prime. This function takes as input a number n to be tested and the number of rounds of testing chosen by the user, t. This function then calls the function ccprime_rabin_miller found in ccprime_rabin_miller.c. This in turn optionally checks that the number being tested is odd, is not one of the first 256 primes, and not divisible by one of the first 119 primes (via a GCD computation). It then performs min(t,256) rounds of Miller-Rabin testing, selecting the bases incrementally from a hard-coded list of the first 256 primes. The code documentation states that when performing t = 32 rounds of testing, the probability of a false prime classification is estimated as 2^-64.

So what does this mean? Well we know the bases chosen for Miller-Rabin will simply be the first t primes. Moreover, since these bases are chosen deterministically based on the value of t, we can achieve a failure rate of 100% with respect to that value t. To follow on from the lottery example, we simply need to produce a composite n that has the first t primes as red balls, as we know these will be chosen.

Using the method described in Arnault, F., 1995. Constructing Carmichael numbers which are strong pseudoprimes to several bases. Journal of Symbolic Computation, 20(2), pp.151-161. We can generate the 1024 bit composite n such that it is declared prime by corecrypto for t ≤ 40.

Such an n is of the form n = pqr where:

n = 105216055594390884840438324972769319399722594046651360392070071794973423530188471087867855419188813164954561140227145977855514336985746250989366318940490798583710597151720075427387437940535767395296272532149397065590267303873620351321073058502920032770522836726669005262088263964215455869031740912313201227043

with

p = 123282949929736752510916282638002560328626287433241467864741378859343760091491850110380631340085554443

q = 28724927333628663335043493854654596556569924971945262012484741274227096101317601075718687102239934184987

r = 29711190933066557355130824115758617039198935271411193755402672305101846182049535876601732152960618620523

In fact we can go one step further and create a 7023 bit n of the form n = pqr such that n is declared prime by corecrypto for any valid user choice of t. See the link to the paper at the end of this post for this example - too big for the blog!

CommonCrypto

CommonCrypto provides the primailty test CCBigNumIsPrime which calls ccz_is_prime provided by corecrypto. However, the user has no choice over the number of rounds of testing t in this case, as it is hard-coded to 16.

It is even easier to generate composites that fool this test, since Apple are forcing us to use the first 16 primes as bases, we know exactly which balls to make red. Again by using the method described in Arnault, F., 1995 we can easily produce such composites, here we give examples for 512, 1024 and 2048 bit numbers.

512 bit n of the form n = pqr where:

n = 7901877332421117604277233556001994548174031728058485631926375876865078028180049751981627864304181541061183590498201673009039329539171539230651776950727307

p = 73938149834061418521192073314311208786743496108043

q = 8355010931248940292894704284517166592902015060208747

r = 12791299921292625404166228683375839120106624826691267

1024 bit n of the form n = pqr where:

n =

122623673100774902819890811512093121818009864395929257382206929494220541500353599732762551419245399058398366502168963509640168639794202705645034115138272912046190084444976198156980059092407987735996562308131806635633617847615677949071026045920492821200676854540540234658043716124914438158326334228684623784307

(This is the number I used earlier in the introduction!)

p =

184423640821245254099510263989726185275555264354779963459730437466872086414580403681648321609499543203

q =

20839871412800713713244659830839058936137744872090135870949539433756545764847585616026260341873448381827

r =

31905289862075428959215275670222630052671060733376933678533365681768870949722409836925159638443420973947

2048 bit n of the form n = pqr where:

n =

19045993130340238960516619526438196400111100205282343586730655491361145656716279531133626430434529862564012117981039124164877101697940176896586158417605958263877200848913504507021277579950088169124892268426377618637450987170274052735330198112915008469887168631791088882138462895976241696424319684682694737684482873770270608671767351537287446887784007605238000642746275451764369774864238904543361007743399722804711123700499775470397792907613698576886427753795632702382124771629436498075085327724596322478489152628386513622447595060065193541715781044580768866541780025974180911498465786060216591028528938508564952141307

p =

991348511670412607102838857034154655102006823401170761398057998099526898363349562736790546231443508447843603144522299600087111824066254038832394576032613300251122333363340447396711513510926363603975967003

q =

112022381818756624602620790844859476026526771044332296037980553785246539515058500589257331724153116454606327155331019854809843636119486706388060587091685302928376823670057470555828401026734679087249284271227

r =

171503292518981381028791122266908755332647180448402541721864033671218153416859474353464764498039726961476943344002357830815070345563461948718004261653642100943444163671857897399631091837390260903487842291347

Test script

I'll now include the framework to show how to call Apple's primality test on these numbers so that you verify for yourselves, that they really are declared prime. (Provided you use a version prior to the update!)

Output:

Disclosure and Mitigations

Working with Apple we have resolved this issue by now performing random selection of bases during Miller-Rabin. We were issued CVE-2018-4398: Martin Albrecht, Jake Massimo and Kenny Paterson of Royal Holloway, University of London, and Juraj Somorovsky of Ruhr University, Bochum.

Thanks for reading! Check out the full details in our paper Prime and Prejudice: Primality Testing Under Adversarial Conditions at https://eprint.iacr.org/2018/749 as well as full analysis of 14 other cryptographic libraries and mathematical software such as OpenSSL, GNU GMP, Java, Botan, GoLang and many more!

Full details of security updates of available at:

iOS 12.1 https://support.apple.com/en-gb/HT209192

macOS Mojave 10.14.1 https://support.apple.com/en-gb/HT209193