SecurePrint strength?

[J Tames]

I found this page http://bitcoin.stackexchange.com/questions/25694/how-secure-is-secure-print and attempted to read the paper about scrypt based key-derivation functions.  My takeaway from the paper was that the SecurePrint security becomes 2^(s+t) with "t" being the bits of entropy (which seems to be 64) and "2^s" being the number of cryptographic operations being computed. 

I couldn't find anything on how many operations armory performs to create the SecurePrint code.  If armory's cryptographic operations is less than 2^64 am I shooting myself in the foot because it becomes easier to crack the SecurePrint feature than the seed?

And if the SecurePrint code is letters and numbers and 11 characters long it can only represent about 64 bits.  So how can the scrypt function make it stronger ? Is it that for each SecurePrint phrase some attacker would have to search all possible seeds?

[btchris]

I wouldn't worry too much.... but here's some more detailed info. TL;DR: just read the bolded parts.

Armory's KDF & encryption for SecurePrint looks approximately like this:
(in short, it generates a random SecurePrint code, runs that through a KDF with good key stretching, and then encrypts your master private key.)

constant_pi = SHA-256(SHA-256('3.1415926...'))  # an arbitrary constant
constant_e  = SHA-256(SHA-256('2.7182818...'))  # an arbitrary constant

Step 1/3: create the SecurePrint code from the master privkey and chaincode
--------
ext_master_privkey = master_privkey + chaincode
# ext_master_privkey is now 64 bytes long and has
# 32 bytes of entropy (the chaincode contributes zero entropy)

code = PRF(key=ext_master_privkey, message=constant_e)
# where PRF is similar to HMAC_SHA-512; it requires 2 SHA-512 computations.

code = code[0..6]  # truncate to 7 bytes long
code = code + SHA-256(SHA-256(code))[0]  # append a single check byte
code = base58_encode(code)
# code now has 7 bytes of entropy (not 8 as the code comment says inside Armory)

Step 2/3: key stretching
--------
key = KDF(passphrase=code, salt=constant_e)
# where KDF is similar to ROMix_SHA-512 using ROMix
# (a memory-hard mixing function) as defined in the scrypt paper;
# it's hardcoded here to use 2²⁴ bytes (16 MiB) of RAM
# and require 2²⁴ / 64 * 1.5 = 393216 SHA-512 computations.

Step 3/3: encryption
--------
encrypted_privkey = CBC-Mode-Encrypt_AES-256(encryption_key=key, salt=constant_pi[0..15], plaintext=master_privkey)

So, brute-forcing a SecurePrint code would take, on average, about:
    2²⁴ / 64 * 1.5 * 2^7*8 / 2 = 1.5 * 2⁷³ ≈ 1.4 * 10²² Total SHA-512 operations

What you'd probably like to do next is use these results to approximate how long / how much $ it would take to brute-force a SecurePrint code. Unfortunately, that's really hard (for me, anyways) to approximate.

You can't compare Armory's KDF to SHA-512 (Bitcoin) ASICs because Armory requires 16MiB of memory to do its work. Comparing Armory's KDF to scrypt (e.g. Litecoin) ASICs might seem better, but... Litecoin uses 128x less memory than Armory's KDF. It also uses the much faster Salsa20/8 hashing algorithm, somewhere around 15x faster per block (but it uses more of them). Finally, Armory doesn't use the full scrypt... it uses a portion of scrypt (ROMix), and a modified portion at that.

To make things even more complicated, you can tweak the numbers above via a space/time tradeoff according to this formula:

table_size   = 2²⁴ / 64  # number of hashes stored in RAM when no space/time tradeoff is used
mem_required = 2^24-n  where n is in 0..18 (mem_required is in bytes)
SHA-512 operations per guess = table_size + 0.5 * table_size * (1 + (2ⁿ-1) / 2)

For the sake of a comparison to the Bitcoin network, let's pretend we can build an Armory KDF ASIC that holds just 16 hashes (has 1024 bytes of memory per parallel attempt, so not much more than 0), you set n=14, and get:

SHA-512 operations per guess = table_size + 0.5 * table_size * (1 + (2¹⁴-1) / 2) = 262144 + 131072 * (1 + 8,191.5) = 1074069504
SHA-512 operations to brute-force = 1074069504 * 2^7*8 / 2 ≈ 2⁸⁶ ≈ 7.7 * 10²⁵

If we apply the entire Bitcoin network's hash capability of 3.5 * 10¹⁷ H/s to this problem (and it's all been magically converted to Armory ASICs, and we assume that SHA-256d costs roughly the same to calculate as SHA-512), we get:
7.7 * 10²⁵ H  /  3.5 * 10¹⁷ H/s  ≈  2.2 * 10⁸ s  ≈  23 years (on average)

Of course, maybe we can build ASICs with more RAM than this and speed things up, but presumable there'd be a point of diminishing returns; I really have absolutely no estimates on that topic, and my guesses on time/spcace tradeoffs in ASICs are probably wildly off.

All of the above is missing several important assumptions:
 1. The encrypted printout was stolen (e.g. by a snooping printer), but the SecurePrint code was not.
 2. Either:
   a. The encrypted wallet file was also stolen (we need access to the chaincode, which is always stored unencrypted, to figure out if a guess is correct), or
   b. We can do EC scalar multiplications and address lookups in the blockchain at the same order of speed as the code guess rate (3.3 * 10⁸/s in this wild example), which is yet another very tall order; figure around 10,000 32-core servers, or additional specialized ASICs.

The reason for (2) above is that there's no way, just by looking at a decrypted private key, if the guess we tried for the code is correct unless we have something to check it against (either the chaincode or the blockchain, and the latter would require EC math which is also hard). Kudos to the Armory devs for not using any padding during private key encryption, which is different from every other wallet I've ever looked it.

I, for one, am not particularly concerned (but of course, keep your backups safe and offline! )

[J Tames]

Wow, thanks for such an in-depth answer.  Appreciate it!

[btchris]

Wow, thanks for such an in-depth answer.  Appreciate it!

I thought it was going to be a lot shorter when I started on it.... oh, well