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.
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.
The only inevitable data dependence in Base 64 encoding or decoding is on the length of the value being encoded or decoded.
- Extraction of 6-bit value by bit shift and masking: constant time.
- Conversion from 6-bit to a character: indexing into a 64-character table, constant time.
- Conversion from a character into a 6-bit value: indexing into a 256-byte table, constant time.
- Insertion into decoded data by bit shift and ORing: constant time.