-
-
Notifications
You must be signed in to change notification settings - Fork 47
Constant time arithmetics
Recent high-profile vulnerabilities in RSA (Cache-bleed), AES, ECDSA involved side-channel attacks. Most often those attacks were carried by timing the difference of execution time depending on user supplied input to restrict private keys to a subset of a large theoretical range.
Attacks can also allow decoding of a private encrypted message.
- Retrieving WPA3 passwords: https://wpa3.mathyvanhoef.com/
- The Trusted Platform Module in all laptop is vulnerable to timing attacks: http://tpm.fail/
- TLS 1.2 and 1.3: https://www.cryptologie.net/article/461/the-9-lives-of-bleichenbachers-cat-new-cache-attacks-on-tls-implementations/
- Minerva timing attack:
- ROTHNP Modular addition: https://www.nccgroup.trust/us/our-research/technical-advisory-return-of-the-hidden-number-problem/
- MSVC compiler using "optimized" multiplication defeating constant-time implementation and leaking server secrets:
- Retrieving 1024 RSA keys in libgcrypt and GPG by analysing modular exponentiation and other modular exponentiation woes:
- Attacking embedded ECC implementations through cmov side channels: https://eprint.iacr.org/2016/923
- Attacking Intel SGX Secure Enclave via the builtin thermometer https://arstechnica.com/information-technology/2020/11/intel-sgx-defeated-yet-again-this-time-thanks-to-on-chip-power-meter/
-
Side-Channel Attacks on Blinded Scalar Multiplications Revisited
Thomas Roche, Laurent Imbert, Victor Lomné
https://eprint.iacr.org/2019/1220 -
One Trace Is All It Takes: Machine Learning-Based Side-Channel Attack on EdDSA
Léo Weissbart, Stjepan Picek, Lejla Batina, 2019
https://eprint.iacr.org/2019/358 -
Survey for Performance & Security Problems of Passive Side-channel Attacks Countermeasures in ECC
Rodrigo Abarúa, Claudio Valencia, and Julio López, 2019
https://eprint.iacr.org/2019/010 -
One&Done: A Single-Decryption EM-Based Attack on OpenSSL’s Constant-Time Blinded RSA
Monjur Alam, Haider Adnan Khan, Moumita Dey, Nishith Sinha, Robert Callan, Alenka Zajic, and Milos Prvulovic
https://www.usenix.org/conference/usenixsecurity18/presentation/alam -
Remote Timing Attacks are Still Practical
Billy Bob Brumley and Nicola Tuveri
https://eprint.iacr.org/2011/232 -
State-of-the-art of secure ECC implementations:a survey on known side-channel attacks and countermeasures
Junfeng Fan,XuGuo, Elke De Mulder, Patrick Schaumont, Bart Preneel and Ingrid Verbauwhede, 2010 https://www.esat.kuleuven.be/cosic/publications/article-1461.pdf
You can read Twitter blogpost of Silhouette, an innovative side-channel attack that uses timing differences between private and public profile on Twitter to determine your Twitter identity bypassing all Twitter and browsers cookies and cross-site mitigations.
And another one exploiting the hardware Spectre vulnerability to read each bit at an arbitrary memory location in 5 lines of C.
It is key that execution time does not depend at all on user supplied input. As cryptography rely in big integers computation, a constant time big int implementation is needed.
Even Openssl does not have full constant time implementation..
We need boolean to implement logic, unfortunately there is no way to prevent compilers to use branches as soon as boolean are involved. So the library cannot use booleans at all and an alternative boolean type must be created.
Compilers may even used "optimized" routines like multiplication that have shortcuts for special operands (all ones or all zeros). This has been exploited to retrieve serve secrets (https://research.kudelskisecurity.com/2017/01/16/when-constant-time-source-may-not-save-you/)
Examples of fighting Clang/LLVM:
- https://www.cl.cam.ac.uk/~rja14/Papers/whatyouc-slides.pdf
- https://www.cl.cam.ac.uk/~rja14/Papers/whatyouc.pdf
- https://github.com/lmrs2/ct_choose
- https://github.com/lmrs2/zerostack
On some hardware, some primitive operations like multiplication are not constant-time. Given the resources we have, we should do constant-time as a best effort.
The following resources gives much more information on challenges, guidelines and implementations of constant time arithmetics:
- Constant-time crypto best practice
- https://bearssl.org/constanttime.html
- https://bearssl.org/ctmul.html
- https://bearssl.org/bigint.html
- Milagro Crypto White paper: http://docs.milagro.io/en/amcl/milagro-crypto-library-white-paper.html
- CryptoJedi on avoiding Carries: https://cryptojedi.org/peter/data/pairing-20131122.pdf
- Apache Milagro-Crypto paper: https://eprint.iacr.org/2017/437.pdf
- Rust timing shield: https://www.chosenplaintext.ca/open-source/rust-timing-shield/security
-
Dudect - Dude is my code constant-time
-
FaCT, a constant-time programming language: https://github.com/PLSysSec/FaCT
-
CANAL: A Cache Timing Analysis Framework via LLVM Transformation, Chungha Sung, Brandon Paulsen, Chao Wang, 33rd ACM/IEEE International Conference on Automated Software Engineering (ASE 2018) https://github.com/canalcache/canal
-
Verifying Constant-Time Implementations, Jose Bacelar Almeida, Manuel Barbosa, Gilles Barthe, Francois Dupressoir, Michael Emmi, 25th USENIX Security Symposium (2016) https://github.com/imdea-software/verifying-constant-time
-
Verifying Constant-Time Implementations by Abstract Interpretation Sandrine Blazy, David Pichardie, Alix Trieu, European Symposium on Research in Computer Security, Sep 2017, Oslo, Norway
-
: A Framework for Finding Side Channels in Binaries
https://arxiv.org/abs/1808.05575 https://github.com/UzL-ITS/Microwalk
Heap allocation is also very tricky and should be avoided
- Page-fault attack: http://people.eecs.berkeley.edu/~shwetas/publications/pfdefense_asiaccs16.pdf
- Memory allocators attack: https://arxiv.org/pdf/1903.00503.pdf
- Memory retention attacks: https://spacetime.dev/memory-retention-attacks
- Encrypting secret in memory
- Core dump protection
- OpenBSD MAP_CONCEAL: https://undeadly.org/cgi?action=article;sid=20190605110020
- On Linux madvise + MADV_DONTDUMP