12
$\begingroup$

Do I need to worry about timing attacks in Base64 encoding/decoding of private keys? This is a common operation (ex. PEM keys) and is variable time in typical implementations.

$\endgroup$
2
  • $\begingroup$ It may be worth to notice that the private key material to be base64 encoded/decoded is commonly ASN.1 DER encoded. DER encoding may also reveal some information via timing differences, as well. $\endgroup$
    – user4982
    Commented May 23, 2016 at 18:40
  • $\begingroup$ @user4982 True, but DER is TLV encoding. The length of the value may be disclosed, but the value itself is not as likely to be exposed. Knowing the length of e.g. the CRT parameters may make it slightly easier to get to the key, but it would be very tough to get the key value that way. $\endgroup$
    – Maarten Bodewes
    Commented May 23, 2016 at 20:37

4 Answers 4

8
$\begingroup$

Yes, kind of. The encoding does depend on the individual bits so there could very well be timing differences. Note that the differences would be pretty small; encoding a byte is likely much faster than e.g. modular exponentiation. But as even block ciphers are vulnerable it may very well be possible, especially since table lookup may be implemented.

The solution however is also very standard: before storing the keys you first wrap the keys with a symmetric cipher. The key can be derived from a strong passphrase. Most of the time when private keys are stored in PEM format (which is just the ASCII armor) they are encoded in PKCS#12. As the encoding after the wrapping and the decoding before, you should be secure against timing attacks against base 64. Obviously the block cipher is much more likely to be protected against timing attacks (but don't forget to verify that).

In principle PKCS#8 could also describe an encrypted private key, but that doesn't seem to be used much. PKCS#12 can be used to encrypt the private key and store the certificate (chain) for the public / private key pair.

If you directly store them in PKCS#1 or PKCS#8 format (without encryption) you should make sure the system itself is secure - especially with regards to file access.

$\endgroup$
4
  • $\begingroup$ PKCS12 is certainly common in DER, but not in PEM that I've seen. PKCS8 PEM is (fairly) common in things using or compatible with OpenSSL, but PKCS8 has optional pw-based encryption -- and the privatekey encryption in PKCS12 is PKCS8. $\endgroup$ Commented May 23, 2016 at 22:59
  • $\begingroup$ @dave_thompson_085 Usually the PKCS#8 structure is only the inner PKCS#8 structure. That doesn't contain encryption. PKCS#12 on the other hand is a software token format where password encryption is usually performed. But I'll edit the answer a bit to show this. Do you often encounter PKCS#8 encrypted keys? $\endgroup$
    – Maarten Bodewes
    Commented May 23, 2016 at 23:12
  • $\begingroup$ @MaartenBodewes PKCS #8 for the most private key formats stores public key (as a part of the private key). RFC 5958 is an update to PKCS #8, which allows to store also public key explicitly (but this extension does not seem very common currently). PKCS #8 encrypted keys are seems from time to time, especially in applications where you would want to password protect the private key, but storing certificate is necessary or possible due to how the key is used. $\endgroup$
    – user4982
    Commented May 24, 2016 at 4:44
  • $\begingroup$ (@user4982) In OpenSSL req -newkey pkcs8 -topk8 pkcs12 (import) (since 2010) all generate PKCS8 encrypted (and PEM) by default; only genpkey defaults to unencrypted and I've not yet seen anyone else (other than OpenSSL site) even mention that. So yes I do see PKCS8 mostly encrypted, though certainly not always. But on the whole I do see PKCS12 more, which always encrypts the privatekey; it usually encrypts the cert(s) also, though weakly and unnecessarily. $\endgroup$ Commented May 24, 2016 at 19:24
1
$\begingroup$

Yes, you do need to worry about timing attacks in Base64 encoding and decoding. A naive implementation either does a table lookup (which is vulnerable to data cache timing attacks) or a range-based calculation (which is vulnerable to branch prediction and code cache timing attacks).

The leak is small, and does not reveal complete information (e.g. table entries that fall within the same cache line might be completely indistinguishable). But this can leak enough of the key material to reconstruct the key, especially with RSA keys where the private key has a lot of redundant information (private exponent and CRT parameters). Util::Lookup: Exploiting key decoding in cryptographic libraries by Sieck et al. observed some common implementations in ideal conditions for a timing attack (attacking a secure enclave from the non-secure operating system running on the same processor) and managed to recover RSA private keys with a single trace of Base64 decoding.

As of mid-2021, this paper lead several cryptographic libraries to switch to a constant-time implementation of Base64 encoding and decoding. However, some still use a table-based implementation as I write, notably OpenSSL.

There are several ways avoid timing side channel leakage from Base64 decoding of private keys and other cryptographic objects:

  • Use binary DER encoding instead of PEM encoding.
  • Use a constant-time Base64 implementation.
  • Encrypt the PEM-encoded data with PKCS#8 or PKCS#12 encryption. This doesn't improve security at rest if the encryption key is stored with the encrypted data, but it does prevent leakage from Base64 decoding, since any leakage would only reveal unexploitable information about the encrypted key (assuming that the decryption process itself doesn't leak).
$\endgroup$
1
$\begingroup$

For secret material stored unencrypted in Base64 format, yes Base64 encoding or decoding is a potential side channel. So is compressing the data (something that OSes may do to conserve RAM or disk).

The amount of information that could be extracted by timing attack (rather than by some other form of side channel, like power analysis) depends a lot on how much foothold the adversaries have in the system, and on the Base64 code. If adversaries can run code on the same CPU (thus same caches) as the one repeatedly running the encoding or decoding, and can time that attacked process to exquisite precision, then it's reasonable to fear a lot of secret data leaks. For a pure timing attack (loosely defined as one where adversaries can't act on the computer attacked, and only get timing measurements) against standard encoder/decoder, that's much more difficult. For said timing measurements thru a packet-based communication network similar to Gigabit Ethernet or slower, and key size 128-bit or more, I'm dubious.

Doing almost anything on unencrypted data in a standard computer opens to many risks, including side-channel attacks. The best solution is to keep sensitive and unencrypted data out of standard computers (e.g. generate and keep that data in a Smart Card), or in standard computers out of reach of attackers. That's a reason why key ceremonies best practices when using a standard computer include using one with no network connection (including no wireless interface), and zeroizing everything before (bringing any OS or code from read-only media) and after use.

$\endgroup$
-2
$\begingroup$

The only inevitable data dependence in Base 64 encoding or decoding is on the length of the value being encoded or decoded.

Encoding

  1. Extraction of 6-bit value by bit shift and masking: constant time.
  2. Conversion from 6-bit to a character: indexing into a 64-character table, constant time.

Decoding

  1. Conversion from a character into a 6-bit value: indexing into a 256-byte table, constant time.
  2. Insertion into decoded data by bit shift and ORing: constant time.
$\endgroup$
3
  • 2
    $\begingroup$ Indexing into a 256-byte (or even 64-byte) table is not necessarily constant time. CPU cache lines can be e.g. 32 or 64 bytes. A timing attack could tell the difference between using only parts of the table and using it all. $\endgroup$
    – otus
    Commented May 29, 2016 at 13:24
  • 1
    $\begingroup$ You're right that length is the only inevitable timing side channel (at least as an upper-bound). But most implementations, including yours, are not constant time since they rely on array lookup with a secret index, which isn't guaranteed to be constant time on many CPUs. $\endgroup$ Commented May 29, 2016 at 15:15
  • $\begingroup$ This is not a constant-time implementation. Indexing into a 256-byte table is vulnerable to cache-based timing attacks. See Cache-timing attacks on AES by D. Bernstein. $\endgroup$
    – Demi
    Commented May 29, 2016 at 18:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.