Replace OpenSSL AES with ctaes-based version #7689

sipa · 2016-03-14T22:46:55Z

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.

jonasschnelli · 2016-03-15T08:26:05Z

src/Makefile.am

@@ -29,13 +29,12 @@ $(LIBLEVELDB) $(LIBMEMENV):
 endif

 BITCOIN_CONFIG_INCLUDES=-I$(builddir)/config
-BITCOIN_INCLUDES=-I$(builddir) -I$(builddir)/obj $(BOOST_CPPFLAGS) $(LEVELDB_CPPFLAGS) $(CRYPTO_CFLAGS) $(SSL_CFLAGS)
+BITCOIN_INCLUDES=-I$(builddir) -I$(builddir)/obj $(BDB_CPPFLAGS) $(BOOST_CPPFLAGS) $(LEVELDB_CPPFLAGS) $(CRYPTO_CFLAGS) $(SSL_CFLAGS)


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

@jonasschnelli yep, just empty

jonasschnelli · 2016-03-15T08:27:02Z

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

sipa · 2016-03-16T17:29:11Z

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

sipa · 2016-03-17T00:44:36Z

Added more comments.

theuni · 2016-03-17T02:10:54Z

Thanks @sipa for the constant-time version!

gmaxwell · 2016-03-19T17:05:15Z

src/crypto/aes.cpp

+    int pos = 0;
+
+    /* The first nkeywords round key words are just taken from the key directly */
+    for (int i = 0; i < nkeywords; i++) {


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.

jonasschnelli · 2016-03-21T12:38:53Z

Tested ACK (52e05be).
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 · 2016-03-23T23:01:44Z

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 · 2016-03-24T05:20:33Z

@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 · 2016-03-24T07:00:06Z

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 · 2016-03-24T07:24:27Z

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 · 2016-03-24T07:31:22Z

There seems to be a case to make for a "Bitcoin non-consensus crypto" library with AES, SHA512, etc...

laanwj · 2016-03-24T07:53:35Z

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 · 2016-03-24T08:24:45Z

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 · 2016-03-24T08:27:18Z

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 · 2016-03-30T04:53:59Z

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 · 2016-03-30T07:23:51Z

Thanks for the thorough testing and reviewing @gmaxwell!

btcdrak · 2016-03-30T09:02:30Z

Concept ACK

paveljanik · 2016-03-30T13:49:36Z

Concept ACK

pstratem · 2016-05-17T08:15:22Z

src/crypto/aes.cpp

+
+AES256Decrypt::~AES256Decrypt()
+{
+    memset(&ctx, 0, sizeof(ctx));


Won't this just be optimized out?

@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 · 2016-05-17T19:39:35Z

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 · 2016-05-25T14:17:23Z

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

theuni · 2016-05-26T15:54:15Z

@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).

theuni · 2016-05-27T18:38:35Z

@sipa Please grab a quick build change: theuni@723779c

After that: ACK

sipa · 2016-05-27T18:54:01Z

@theuni Merged in

theuni · 2016-06-01T16:12:58Z

ACK 723779c

723779c build: Enumerate ctaes rather than globbing (Cory Fields) 34ed64a crypter: add tests for crypter (Cory Fields) 0a36b9a crypter: shuffle Makefile so that crypto can be used by the wallet (Cory Fields) 976f9ec crypter: add a BytesToKey clone to replace the use of openssl (Cory Fields) 9049cde crypter: hook up the new aes cbc classes (Cory Fields) fb96831 crypter: constify encrypt/decrypt (Cory Fields) 1c391a5 crypter: fix the stored initialization vector size (Cory Fields) daa3841 crypto: add aes cbc tests (Cory Fields) 27a212d crypto: add AES 128/256 CBC classes (Cory Fields) 6bec172 Add ctaes-based constant time AES implementation (Pieter Wuille) a545127 Squashed 'src/crypto/ctaes/' content from commit cd3c3ac (Pieter Wuille)

ZIP 32 preparations Includes Makefile changes cherry-picked from the following upstream PRs: - bitcoin/bitcoin#7689 - bitcoin/bitcoin#10849 Part of #3380.

723779c build: Enumerate ctaes rather than globbing (Cory Fields) 34ed64a crypter: add tests for crypter (Cory Fields) 0a36b9a crypter: shuffle Makefile so that crypto can be used by the wallet (Cory Fields) 976f9ec crypter: add a BytesToKey clone to replace the use of openssl (Cory Fields) 9049cde crypter: hook up the new aes cbc classes (Cory Fields) fb96831 crypter: constify encrypt/decrypt (Cory Fields) 1c391a5 crypter: fix the stored initialization vector size (Cory Fields) daa3841 crypto: add aes cbc tests (Cory Fields) 27a212d crypto: add AES 128/256 CBC classes (Cory Fields) 6bec172 Add ctaes-based constant time AES implementation (Pieter Wuille) a545127 Squashed 'src/crypto/ctaes/' content from commit cd3c3ac (Pieter Wuille)

a49d5d4 Remove unused OpenSSL includes to make it more clear where OpenSSL is used (furszy) 8adbaab Build: Add ctaes to CMakeLists (Fuzzbawls) 5975fc2 build: Enumerate ctaes rather than globbing (furszy) 096d1b7 crypter: constify encrypt/decrypt (furszy) ad984e4 crypter: add tests for crypter (Cory Fields) be94566 crypter: add a BytesToKey clone to replace the use of openssl (furszy) 2aeb09e crypter: hook up the new aes cbc classes (furszy) b2175f3 crypter: fix the stored initialization vector size (furszy) 86053f5 crypto: add aes cbc tests (Cory Fields) 1708a62 crypto: add AES 128/256 CBC classes (Cory Fields) 2395fa7 Add ctaes-based constant time AES implementation (Pieter Wuille) bfb12ba Squashed 'src/crypto/ctaes/' content from commit cd3c3ac (Pieter Wuille) Pull request description: Coming from upstream [7689](bitcoin#7689) ``` 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. ``` ACKs for top commit: Fuzzbawls: ACK a49d5d4 random-zebra: utACK cleanup commit a49d5d4 Tree-SHA512: f825aaf200d214adb804f1f1a1849d8f6a052ebe766f015215e958d135acefb7ce2580205bdea309a8be3c3aaf8007cd9aa2399e071c416eb90f1c55e0342ae2

Replace OpenSSL AES with ctaes-based version Backported from upstream PR bitcoin/bitcoin#7689. This is backported primarily to remove merge conflicts for a subsequent backport, and also helps us towards removing OpenSSL. Its actual usage in wallet encryption would be replaced by a more modern construction before we make wallet encryption a supported feature, but for now this does not affect anyone using the experimental feature.

sipa changed the title ~~Replace OpenSSL AES with our own constant-time version (edit of #5949)~~ Replace OpenSSL AES with our own constant-time version Mar 14, 2016

laanwj mentioned this pull request Mar 15, 2016

Replace openssl aes encryption/decryption/key creation implementations with our own #5949

Closed

laanwj added this to the 0.13.0 milestone Mar 15, 2016

laanwj added Wallet Priority High labels Mar 15, 2016

jonasschnelli reviewed Mar 15, 2016
View reviewed changes

sipa force-pushed the const_aes branch from e510fe7 to ef3c998 Compare March 16, 2016 17:26

sipa force-pushed the const_aes branch from ef3c998 to e4a08a3 Compare March 17, 2016 00:44

sipa force-pushed the const_aes branch from e4a08a3 to 6d754e1 Compare March 17, 2016 01:09

gmaxwell reviewed Mar 19, 2016
View reviewed changes

sipa force-pushed the const_aes branch 3 times, most recently from 73b369c to e208d95 Compare March 20, 2016 18:31

pstratem reviewed May 17, 2016
View reviewed changes

build: Enumerate ctaes rather than globbing

723779c

sipa force-pushed the const_aes branch from 18c6a51 to 723779c Compare May 27, 2016 18:54

sipa merged commit 723779c into bitcoin:master Jun 1, 2016

sickpig mentioned this pull request Feb 22, 2017

Bundle together deadalnix's PR 213 to 218 BitcoinUnlimited/BitcoinUnlimited#313

Merged

kyuupichan mentioned this pull request May 1, 2017

[port][easy crypto: spelling fixes BitcoinUnlimited/BitcoinUnlimited#497

Merged

Warrows mentioned this pull request Jun 10, 2018

[Crypto] Switch to libsecp256k1 signature verification and update the lib PIVX-Project/PIVX#549

Merged

str4d mentioned this pull request Aug 4, 2018

ZIP 32 preparations zcash/zcash#3447

Merged

zkbot added a commit to zcash/zcash that referenced this pull request Aug 5, 2018

Auto merge of #3447 - str4d:zip32-prep, r=str4d

8df048b

ZIP 32 preparations Includes Makefile changes cherry-picked from the following upstream PRs: - bitcoin/bitcoin#7689 - bitcoin/bitcoin#10849 Part of #3380.

furszy mentioned this pull request Apr 2, 2020

Replace OpenSSL AES with ctaes-based version PIVX-Project/PIVX#1486

Merged

str4d mentioned this pull request Jul 17, 2020

Replace OpenSSL AES with ctaes-based version zcash/zcash#4614

Merged

bitcoin locked as resolved and limited conversation to collaborators Sep 8, 2021

Replace OpenSSL AES with ctaes-based version #7689

Replace OpenSSL AES with ctaes-based version #7689

Uh oh!

Conversation

sipa commented Mar 14, 2016

Uh oh!

jonasschnelli Mar 15, 2016

Choose a reason for hiding this comment

Uh oh!

theuni Mar 17, 2016

Choose a reason for hiding this comment

Uh oh!

jonasschnelli commented Mar 15, 2016

Uh oh!

sipa commented Mar 16, 2016

Uh oh!

sipa commented Mar 17, 2016

Uh oh!

theuni commented Mar 17, 2016

Uh oh!

gmaxwell Mar 19, 2016

Choose a reason for hiding this comment

Uh oh!

sipa Mar 20, 2016

Choose a reason for hiding this comment

Uh oh!

jonasschnelli commented Mar 21, 2016

Uh oh!

petertodd commented Mar 23, 2016

Uh oh!

gmaxwell commented Mar 24, 2016

Uh oh!

sipa commented Mar 24, 2016 via email

Uh oh!

laanwj commented Mar 24, 2016

Uh oh!

luke-jr commented Mar 24, 2016

Uh oh!

laanwj commented Mar 24, 2016

Uh oh!

gmaxwell commented Mar 24, 2016

Uh oh!

jonasschnelli commented Mar 24, 2016

Uh oh!

gmaxwell commented Mar 30, 2016

Uh oh!

laanwj commented Mar 30, 2016

Uh oh!

btcdrak commented Mar 30, 2016

Uh oh!

paveljanik commented Mar 30, 2016

Uh oh!

pstratem May 17, 2016

Choose a reason for hiding this comment

Uh oh!

theuni May 17, 2016

Choose a reason for hiding this comment

Uh oh!

btcdrak commented May 17, 2016

Uh oh!

sipa commented May 25, 2016

Uh oh!

theuni commented May 26, 2016

Uh oh!

theuni commented May 27, 2016

Uh oh!

sipa commented May 27, 2016

Uh oh!

theuni commented Jun 1, 2016

Uh oh!

Uh oh!