Replace OpenSSL AES with ctaes-based version

sipa commented at 10:46 pm on March 14, 2016: member

This is a version of #5949 with a constant-time, slow and simple AES implementation.

Performance on modern systems should be around 2-10 Mbyte/s (for short to larger messages), which is plenty for the needs of our wallet.

sipa renamed this:
~~Replace OpenSSL AES with our own constant-time version (edit of #5949)~~
Replace OpenSSL AES with our own constant-time version
on Mar 14, 2016

laanwj added this to the milestone 0.13.0 on Mar 15, 2016

laanwj added the label Wallet on Mar 15, 2016

laanwj added the label Priority High on Mar 15, 2016

in src/Makefile.am: in e510fe7267 outdated

28@@ -29,13 +29,12 @@ $(LIBLEVELDB) $(LIBMEMENV):
29 endif
30 
31 BITCOIN_CONFIG_INCLUDES=-I$(builddir)/config
32-BITCOIN_INCLUDES=-I$(builddir) -I$(builddir)/obj $(BOOST_CPPFLAGS) $(LEVELDB_CPPFLAGS) $(CRYPTO_CFLAGS) $(SSL_CFLAGS)
33+BITCOIN_INCLUDES=-I$(builddir) -I$(builddir)/obj $(BDB_CPPFLAGS) $(BOOST_CPPFLAGS) $(LEVELDB_CPPFLAGS) $(CRYPTO_CFLAGS) $(SSL_CFLAGS)

jonasschnelli commented at 8:26 am on March 15, 2016:

I guess this does not break the --disable-wallet non BDB compile option? Its probably empty if BDB was not found.

theuni commented at 2:09 am on March 17, 2016:

@jonasschnelli yep, just empty

jonasschnelli commented at 8:27 am on March 15, 2016: contributor

Nice work! Short code review utACK. Will test soon.

sipa force-pushed on Mar 16, 2016

sipa commented at 5:29 pm on March 16, 2016: member

Made a small change: the RijndaelSetup function now uses no modulus or division operations anymore. All tests still pass.

sipa force-pushed on Mar 17, 2016

sipa commented at 0:44 am on March 17, 2016: member

Added more comments.

sipa force-pushed on Mar 17, 2016

theuni commented at 2:10 am on March 17, 2016: member

Thanks @sipa for the constant-time version!

in src/crypto/aes.cpp: in fc484f1390 outdated

421+    int round = 0;
422+    /* The number of the word being generated, modulo nkeywords */
423+    int pos = 0;
424+
425+    /* The first nkeywords round key words are just taken from the key directly */
426+    for (int i = 0; i < nkeywords; i++) {

gmaxwell commented at 5:05 pm on March 19, 2016:

A bounds assertion on nkeywords would be helpful prior to this line (e.g. at the start of the function). The loop requires that i<8 to prevent overflow on the stack, but this is only enforced in the caller. Similarly, the round count must be limited to not overflow the state.

sipa commented at 1:57 pm on March 20, 2016:

Fixed.

sipa force-pushed on Mar 20, 2016

jonasschnelli commented at 12:38 pm on March 21, 2016: contributor

Tested ACK (52e05be371551a4529ec9248afebcca67fae6181). Verified test vectors, run tests on different platforms and setups. Tested this PR with encrypted wallet.dat from master (and vice versa).

NOT tested/verified constant time behavior.

petertodd commented at 11:01 pm on March 23, 2016: contributor

Concept NACK

I don’t think we should be using low-level crypto primitives code developed by us that has ~zero chance of being reviewed or used by anyone other than us. I don’t care how good we think we are, thats just not a good practice.

Maybe stick this in libsecp256k1 instead?

gmaxwell commented at 5:20 am on March 24, 2016: contributor

@petertodd the “go put it in another library” response has a verifiable history of killing useful progress here (see also continued use of the problematic and fairly scary openssl RNG), you wouldn’t provide the same complaint for random “found on the internet” code that was demonstratively broken. Seems misplaced. We don’t have any performance concerns for AES but in a generic library there would be performance concerns and a different construction might be called for.

sipa commented at 7:00 am on March 24, 2016: member

We could also not go as far making it a separate library, but do abstract out the inner AES logic as a separate C file and publish that under a different repository, together with tests. @petertodd I agree in theory that it has little chance of being reviewed elsewhere this way, but what about reviewers here? We have several reimplementations of other crypto primitives, in which bugs could have been introduced. Did anyone check by comparing their code line by line with an alternate implementation? If not, whether it includes original design or not is not very relevant.

laanwj commented at 7:24 am on March 24, 2016: member

I agree with @petertodd that ideally the code should be published separately from bitcoin as well.

This doesn’t need to be a generic library. We’d like this code to be self-contained (and have a special requirement here) so using OpenSSL et al is not an option, and maintaining a new generic library is a lot of work and responsibility too.

But I can understand that some people would find a specific implementation of AES just for bitcoin core as risky. (And even though it’s not used in consensus, nor anything network-facing, a bug in the wallet encryption would be a big deal.)

Did anyone check by comparing their code line by line with an alternate implementation?

Yes, people have done so.

Maybe stick this in libsecp256k1 instead?

Please no, that’s scope creep for libsecp256k1. You’re not trying to turn secp256k1 into a generic crypto library are you?

luke-jr commented at 7:31 am on March 24, 2016: member

There seems to be a case to make for a “Bitcoin non-consensus crypto” library with AES, SHA512, etc…

laanwj commented at 7:53 am on March 24, 2016: member

I think we should ask the question separately from where the code is, though:

Can we get any (independent, skilled) cryptographers to review this code? At least reviewing crypto code is a mostly one-time deal, after which it will (hardly) ever change.

gmaxwell commented at 8:24 am on March 24, 2016: contributor

I’d already suggested sipa split out and convert to C before he posted it because this have have independent interest as is probably the smallest constant time implementation of AES I’ve seen, or at least the smallest that doesn’t have embarrassingly bad performance– so no objection there.

jonasschnelli commented at 8:27 am on March 24, 2016: contributor

I’m happy to extract this PR as C code into a C89 compatible library. I have interest to use this for my SPV library project (https://github.com/libbtc/libbtc) and for a open source hardware wallet MCU codebase: https://github.com/digitalbitbox/mcu.

gmaxwell commented at 4:53 am on March 30, 2016: contributor

I have had this code running on 104 cores for several days, running a test that feeds random input through encode and decode with random keys and compares it to AES-NI.

The current maximum long term rate for the wallet application of this code in the current network is roughly 7 decrypts per second of roughly 48 bytes. At the current speed of my test harness it means that I have tested the equivalent of the network’s maximum rate for thirty one thousand years without finding a fault.

Mutation testing showed very very high error correlation, meaning that any error manually introduced in the software made every execution (or nearly every execution) wrong. (So far I have not found any candidate error that didn’t have this effect though automated searching, though I wouldn’t be totally shocked if there were one– it’s still the case that this codebase has very high error correlation).

Pieter has a new version which is a straightforward port to plain C89 with some minor cleanup and some size reductions I contributed (the code size is still larger than the smallest AES implementations I can find (which aren’t constant time), but not enormously so). I’ll soon update my testing harness to that code and continue. I’ve also now reviewed the C89 version pretty extensively.

laanwj commented at 7:23 am on March 30, 2016: member

Thanks for the thorough testing and reviewing @gmaxwell!

btcdrak commented at 9:02 am on March 30, 2016: contributor

Concept ACK

paveljanik commented at 1:49 pm on March 30, 2016: contributor

Concept ACK

sipa force-pushed on Mar 30, 2016

sipa renamed this:
~~Replace OpenSSL AES with our own constant-time version~~
[WIP] Replace OpenSSL AES with ctaes-based version
on Mar 30, 2016

sipa commented at 1:58 pm on March 30, 2016: member

The constant time AES core code is now factored out to a new repository; for now, it’s available at http://github.com/sipa/ctaes/

The pull request here has been updated to use a subtree of that project, with C++ wrappers around it.

The build code is very simple: ctaes does not have any configuration or own build system, so Bitcoin Core just builds it as part of its own process. I have not included ctaes’s tests here for simplicity; the relevant AES C++ wrapper code does have its own tests though.

sipa commented at 2:12 pm on March 30, 2016: member

I’ve marked it as WIP for now, as I’d like to get some review on the ctaes code first before moving to the separate repository.

gmaxwell commented at 5:03 am on March 31, 2016: contributor

@sipa can you at least update to your latest code (even if not doing the subtree) just so people will not review the wrong thing?

sipa force-pushed on Mar 31, 2016

sipa commented at 10:01 am on March 31, 2016: member

@gmaxwell Done. Not going to touch this PR or the sipa/ctaes master branch until there has been some review.

Squashed 'src/crypto/ctaes/' content from commit cd3c3ac

git-subtree-dir: src/crypto/ctaes
git-subtree-split: cd3c3ac31fac41cc253bf5780b55ecd8d7368545

a545127fbc

Merge commit 'a545127fbccef4ee674d18d43732ce00ba97f782' as 'src/crypto/ctaes' cd2be4419e

sipa force-pushed on May 11, 2016

sipa commented at 6:18 pm on May 11, 2016: member

Updated to latest ctaes (which includes a link to the review work by Ayo Akinyele), and rebased.

I now get this error:

0/usr/bin/ld: crypto/libbitcoin_crypto.a(crypto_libbitcoin_crypto_a-ctaes.o): relocation R_X86_64_PC32 against undefined symbol `__stack_chk_fail@@GLIBC_2.4' can not be used when making a shared object; recompile with -fPIC

@theuni Did I screw up the rebase?

theuni commented at 11:22 pm on May 11, 2016: member

@sipa: ctaes.c doesn’t get cxxflags (it gets cflags since it builds with gcc). Introducing a c source throws a wrench in our assumptions that we’re building c++(11) sources. We could come up with a common set of flags shared between them, but by far the easiest fix here is just to ctaes.c –> ctaes.cpp.

If that drives you crazy, I can work on it.

sipa force-pushed on May 12, 2016

sipa commented at 0:09 am on May 12, 2016: member

@theuni Included the .c file from the .cpp wrapper for now; seems to work fine

sipa commented at 1:20 am on May 12, 2016: member

@theuni Ok, I’ll need your help anyway :)

Edit: nevermind, I did EXTRA_DIST += src/crypto/ctaes instead of EXTRA_DIST += crypto/ctaes

Add ctaes-based constant time AES implementation 6bec172eb9

crypto: add AES 128/256 CBC classes

The output should always match openssl's, even for failed operations. Even for
a decrypt with broken padding, the output is always deterministic (and attemtps
to be constant-time).

27a212dcb4

crypto: add aes cbc tests daa384120a

crypter: fix the stored initialization vector size

AES IV's are 16bytes, not 32. This was harmless but confusing.

Add WALLET_CRYPTO_IV_SIZE to make its usage explicit.

1c391a5866

crypter: constify encrypt/decrypt

This makes CCrypter easier to pass aroundf for tests

fb96831c1f

crypter: hook up the new aes cbc classes 9049cde4d9

crypter: add a BytesToKey clone to replace the use of openssl

BytesToKeySHA512AES should be functionally identical to EVP_BytesToKey, but
drops the dependency on openssl.

976f9ec264

crypter: shuffle Makefile so that crypto can be used by the wallet

Wallet must come before crypto, otherwise linking fails on some platforms.

Includes a tangentially-related general cleanup rather than making the Makefile
sloppier.

0a36b9af28

crypter: add tests for crypter

Verify that results correct (match known values), consistent (encrypt->decrypt
matches the original), and compatible with the previous openssl implementation.

Also check that failed encrypts/decrypts fail the exact same way as openssl.

34ed64a404

sipa force-pushed on May 13, 2016

sipa commented at 8:30 am on May 13, 2016: member

I think the CBC implementation should move to ctaes. It makes ctaes more useful (people shouldn’t be using the raw AES block cipher without a mode of operation), and reduced custom-written crypto inside Core.

theuni commented at 5:03 pm on May 13, 2016: member

@sipa makes sense, sgtm. No hard feelings if you’d prefer to drop this stuff. I could port it to c and give it an api in ctaes if you’d like, though obviously the “i tried to make it constant-time” implementation will need a stronger guarantee :)

sipa commented at 5:07 pm on May 13, 2016: member

@theuni No need for that to be a blocker, though. We could move things to C as a follow-up.

sipa commented at 6:24 pm on May 13, 2016: member

Ready for merging, I hope.

gmaxwell commented at 0:18 am on May 14, 2016: contributor

I didn’t see any tests that explicit test for failure with invalid padding, except perhaps in the test that makes sure it behaves the same as OpenSSL. Perhaps if the CBC mode is ported to C in a later PR that could be addressed.

utACK. Good work sipa and cfields.

sipa renamed this:
~~[WIP] Replace OpenSSL AES with ctaes-based version~~
Replace OpenSSL AES with ctaes-based version
on May 14, 2016

in src/crypto/aes.cpp: in 6bec172eb9 outdated

62+    AES256_init(&ctx, key);
63+}
64+
65+AES256Decrypt::~AES256Decrypt()
66+{
67+    memset(&ctx, 0, sizeof(ctx));

pstratem commented at 8:15 am on May 17, 2016:

Won’t this just be optimized out?

theuni commented at 9:01 pm on May 17, 2016:

@pstratem Probably, but it doesn’t hurt to leave it here. We can replace it with something stronger when we figure out what to do about OPENSSL_cleanse.

btcdrak commented at 7:39 pm on May 17, 2016: contributor

For the record, the formal peer review was made of CTAES implementation correctness. The report can be found at http://bitcoin.sipa.be/ctaes/review.zip written by Ayo Akinyele.

sipa commented at 2:17 pm on May 25, 2016: member

@theuni @jonasschnelli Feel like testing/reviewing again after the update to use ctaes?

theuni commented at 3:54 pm on May 26, 2016: member

@sipa Thanks for the reminder, I’ll test/ack again today. I’m not qualified to review ctaes itself, so I’ll have to defer to Ayo Akinyele’s review (which appears thorough).

build: Enumerate ctaes rather than globbing 723779c650

theuni commented at 6:38 pm on May 27, 2016: member

@sipa Please grab a quick build change: https://github.com/theuni/bitcoin/commit/723779c6504453cfb5ccdacf864e7e2f09bb6c32

After that: ACK

sipa commented at 6:54 pm on May 27, 2016: member

@theuni Merged in

sipa force-pushed on May 27, 2016

theuni commented at 4:12 pm on June 1, 2016: member

ACK https://github.com/bitcoin/bitcoin/pull/7689/commits/723779c6504453cfb5ccdacf864e7e2f09bb6c32

sipa merged this on Jun 1, 2016

sipa closed this on Jun 1, 2016

sipa referenced this in commit b89ef13114 on Jun 1, 2016

codablock referenced this in commit 856ae0b184 on Sep 16, 2017

codablock referenced this in commit 407c8c24b8 on Sep 19, 2017

codablock referenced this in commit 91752ab7ed on Dec 22, 2017

zkbot referenced this in commit 0d9fbb02d6 on Aug 4, 2018

zkbot referenced this in commit baae90489b on Aug 4, 2018

zkbot referenced this in commit 29de8c8456 on Aug 5, 2018

zkbot referenced this in commit 6eecedba2c on Aug 5, 2018

zkbot referenced this in commit 8df048b1de on Aug 5, 2018

andvgal referenced this in commit 6f128b68a1 on Jan 6, 2019

Fuzzbawls referenced this in commit e146131780 on May 16, 2020

zkbot referenced this in commit 4511c39361 on Jul 17, 2020

zkbot referenced this in commit 2589b2fcc5 on Jul 31, 2020

MarcoFalke locked this on Sep 8, 2021

Replace OpenSSL AES with ctaes-based version #7689