Fooling primality tests on smartcards [ESORICS 2020]

Authors: Vladimir Sedlacek, Jan Jancar and Petr Svenda

Primary contact: Jan Jancar <j08ny@mail.muni.cz>

Conference: ESORICS 2020

@InProceedings{2020-esorics-foolingprimes,
  Title         = {Fooling primality tests on smartcards},
  Author        = {Vladimir Sedlacek and Jan Jancar and Petr Svenda},
  BookTitle     = {25th European Symposium on Research in Computer Security (ESORICS) 2020},
  Year          = {2020},
  Publisher     = {Springer},
  crocsweb      = {https://crocs.fi.muni.cz/papers/primality_esorics20},
  Keywords      = {ECC, primality, pseudoprimes, smartcards},
}

Abstract

We analyse whether the smartcards of the JavaCard platform correctly validate primality of domain parameters. The work is inspired by Albrecht et al.[1], where the authors analysed many open-source libraries and constructed pseudoprimes fooling the primality testing functions. However, in the case of smart-cards, often there is no way to invoke the primality test directly, so we trigger it by replacing (EC)DSA and (EC)DH prime domain parameters by adversarial composites. Such a replacement results in vulnerability to Pohlig-Hellman style attacks, leading to private key recovery.Out of nine smartcards (produced by five major manufacturers) we tested, all butone have no primality test in parameter validation. As the JavaCard platform provides no public primality testing API, the problem cannot be fixed by an extra parameter check, making it difficult to mitigate in already deployed smartcards.

Further research

Data, generation scripts and attack demonstrations: GitHub

Summarizing video

Selected conclusions

We analysed nine different smartcards from ﬁve major manufacturers and found that all but one failed to properly verify the primality of the provided ECDSA and ECDH domain parameters. Furthermore, general composites (not even pseudoprimes) were enough to fool the cards.
Due to the unavailability of primality testing functionality in the public JavaCardAPI and the blackbox nature of the smartcards, it is hard to systematically test domain parameters for primality. We propose a methodology to do so.
We demonstrated Pohlig-Hellman style attacks in two scenarios for ECDSA/ECDH (one of which is new) and two scenarios for DSA/DH. The attacks lead to full private key recovery, assuming the attacker has control over the domain parameters.
Issues found were responsibly disclosed to the aﬀected vendors, but the vulnerability is not easily mitigated for the already deployed smartcards. The code responsible for the domain parameter validation is often stored in a read only memory without the possibility for an update. In addition, the missing primality testing function in the API prevents the developer the check the parameters on-card.
Besides allowing API primality testing, full domain parameter validation and supporting only named curves (though this limits future flexibility) should mitigate the vulnerability. On a lower level, using either Miller-Rabin with random bases or the Baillie-PSW primality test should detect all composites.

Acknowledgements

J. Jancar was supported by the grant MUNI/C/1701/2018, V.Sedlacek by the Czech Science Foundation project GA2003426S and the Brno Ph.D. Talent Scholarship (funded by the Brno City Municipality). Some of the tools used and P.Svenda were supported by the CyberSec4Europe Competence Network. Computational resources were supplied by the project e-INFRA LM2018140.