[Bitcoin-development] Two factor wallet with one-time-passwords

[Bitcoin-development] Two factor wallet with one-time-passwords

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 5056 bytes --]

Gavin Andresen recently suggested a design for a wallet protected by
two-factor authentication via one-time-passwords with the aid of a
third-party service to counter-sign 2-of-2 protected wallets.(1) The
design is useful when the user can't sign transactions on a second
device, such as a phone, but can provide one-time-passwords. (possibly
generated on a smart phone or stored on paper) However involving a
third-party has privacy and availability risks. Here is an alternate
design, also using one-time-passwords, that removes the requirement for
a third-party, along with other advantages and disadvantages.


User experience
===============

The user has a wallet with a separate balances for savings and a smaller
day-to-day spending amount. Transactions spending the day-to-day balance
do not need two-factor authorization, while spending the savings balance
does. As the day-to-day balance becomes low the user is able to top it
up by authorizing the movement of discrete multiples of some amount from
savings to spending. That authorization requires one one-time-password
per multiple being moved.


Implementation
==============

Savings use P2SH outputs matching the following scriptPubKey form:

HASH160 <H(nonce_i)> EQUALVERIFY <pubkey> CHECKSIG

spent with:

<sig> <nonce_i>

The way the pubkey/seckey is generated is unimportant, although some
kind of deterministic scheme is preferable. Nonces on the other hand are
generated deterministically using a counter-based one-time-password
scheme that takes some secret seed and an integer i.  A large number of
H(nonce_n) are generated in advance and moved to the computer holding
the wallet. (generating them on that computer is also possible, but
obviously risks the secret seed being compromised)

A brute-force attack to spend a signed txout requires the attacker to
find a preimage, thus the security level is the number of bits for the
nonce; 64 bits is sufficient. (remember the birthday attack doesn't
apply here) Unfortunately the most popular one-time-password scheme, the
RFC6238 used in Google Authenticator, only outputs six digits numbers,
well below the security level required. (Google Auth is generally used
in a time-mode, but also has a counter mode)

The older RFC2289 however turns the passwords into six words from a 2048
entry wordlist, giving a 64-bit nonce with 2-bits of checksum. RFC2289
implementations are also well suited to paper print-outs and generally
make it easy to do so. RFC2289 as written uses SHA1, however the
suspected vulnerabilities in SHA1 are partial-preimage collisions, not
relevant in this application.

In a sense the user is now acting as an oracle answering the question of
whether or not funds should be allowed to move from savings to spending,
without being responsible for where those funds are allowed to go. As
described in (2) it is easy to create a whole range of conditions by
using multiple nonces if the use-case demanded. For instance a corporate
environment may want multiple parties to be required to authorize the
funds to move, possible with multiple nonces.

It's interesting to note how in some cases it may be preferable that the
authorization is simply authorization to spend without any other
involvement. Here the party acting as an oracle not only doesn't need to
know where funds are going but can even authorize the spend in advance
without two-way communication - possibly even prior to the funds being
received in the first place. This authorization can be easily given
manually, for instance over the phone, and the accounting to keep track
of the total amount authorized can be easily done with pen and paper -
something not possible with CHECKMULTISIG wallets.


Funding the wallet
==================

As with any multi-party wallet receiving funds must also be handled
carefully to ensure an attacker can't fool the user into giving the
sender the wrong address. This requires the involvement of all parties
required to authorize an outgoing payment. In addition here the
protection only works if funds sent to the wallet are split up into the
discrete authorization amounts the user wishes. (possibly with more than
one amount level)

There hasn't been as much thought put into these systems as there has
been on payment protocols between a customer and a merchant, but the
basic idea is to have more than one device participate in the generation
of payment request signed somehow. For fund splitting the request can be
that the funds are paid to multiple txouts in one go.  For recurring
payments the request could have some mechanism for multiple addresses to
be specified for future use. Fall-back to a standard multi-signature
wallet is possible as well.

More research is needed.


1) https://gist.github.com/gavinandresen/5616606
2) https://bitcointalk.org/index.php?topic=260898.msg2804469#msg2804469

-- 
'peter'[:-1]@petertodd.org
000000000000006447c7d824b1952ba36ad1f34351be6904c30247591156460c

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 490 bytes --]

Re: [Bitcoin-development] Two factor wallet with one-time-passwords

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 4270 bytes --]

On Sat, Jul 27, 2013 at 07:49:18PM -0400, Peter Todd wrote:
> Implementation
> ==============
> 
> Savings use P2SH outputs matching the following scriptPubKey form:
> 
> HASH160 <H(nonce_i)> EQUALVERIFY <pubkey> CHECKSIG
> 
> spent with:
> 
> <sig> <nonce_i>

FWIW with some minor scripting language additions such as access to txin
and txout contents, along with merklized abstract syntax tree (MAST)
support, we can even implement a version where scriptPubKey's can be
reused:

    <pubkey> CHECKSIGVERIFY

    // Verify we aren't spending more than the maximum spend amount
    0 GET-TXIN-VALUE      // relative indexing
    0 GET-TXOUT-VALUE
    SUB
    <max-spend-amount>
    LESSTHAN
    VERIFY

    // If the txout is greater than the maximum spend amount force it to
    // also follow these same rules.
    0 GET-TXOUT-VALUE
    <max-spend-amount>
    LESSTHAN
    IFNOT
        GET-THIS-SCRIPT
        MAST-HASH
        <serialized script "MAST-HASH MAST-EVAL">
        CAT
        GET-TXOUT-SCRIPT
        EQUALVERIFY
    ENDIF

    // Hash the provided oracle nonce, saving original for later.
    DUP
    HASH160

    // Use the txid:vout nonce as an index to a table, embedded with MAST
    // script compression.
    0 GET-TXIN-TXID
    0 GET-TXIN-VOUT
    CAT
    HASH160

    // The table, n=64 levels deep, not all levels shown for brevity.
    DUP
    1
    AND
    IF
        1
        RSHIFT
        DUP
        1
        AND
        IF
            1
            RSHIFT
            DUP
            1
            AND
            IF
                <MAST digest, not executed>
            ELSE
                1
                RSHIFT
                DUP
                1
                AND
                IF
                    // Lowest level contains the following pushdata,
                    // with 0 <= i < 2^64
                    <HASH160(HASH160(nonce-secret + i))>
                ELSE
                    <MAST digest, not executed>
                ENDIF
        ELSE
            <MAST digest, not executed>
        ENDIF
    ELSE
        <MAST digest, not executed>
    ENDIF

    // Drop the txid:vout nonce
    SWAP
    DROP

    // Verify that the hash of the nonce and the pre-committed value in
    // the H(nonce) table match.
    EQUALVERIFY

    // Stack now only contains the nonce preceeded by a merkle path linking
    // that nonce to the tip of a merkle tree over all nonces.
    //
    // Verify that path.
    SWAP // Move direction flag to the top
    IF
        SWAP
    ENDIF
    HASH160
    (repeat above five lines 63 more times)

    <nonce-merkle-tree-tip-digest>
    EQUAL

The scriptPubKey is spent by the following scriptSig:

    <nonce-merkle-path-0>...<nonce-merkle-path-63>
    <nonce>
    <signature>
    <serialized-script>

(note that I've left off a number of possible optimizations for clarity)

Now when the user wishes to spend a txout greather than their spending
limit their wallet software will first give them a short 6 word string
calculated from the last 64-bits of H(txid:vout). They simply enter this
string into their phone, ideally via convenient qr-code or voice/thought
recognition, and their phone provides a second short 6 word string to
enter into the wallet software on their computer, authorizing the
payment. If they opt for a paper-based one-time-password table they
simply use the 6 word string as an index to their pre-printed OTP
encyclopedia set.

Like the previously described version the security level is still a
healthy 2^64 - again the attacker needs to find a 64-bit pre-image,
considered to be a highly difficult task for any attacker unable to
count from 0 to 2^64 or store a table containing 2^64 values.

There is the disadvantage of the large storage requirements for both
wallets, however because of the double hashed construction,
H(H(nonce-secret+i)), neither table needs to be kept secret. Thus
without loss of security both tables can be easily stored in a
distributed hash table in the cloud and queried as needed.

-- 
'peter'[:-1]@petertodd.org
0000000000000012199fe3f1f54921e8e11c0b0d318ed6245dee22a4ad55bc65

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 490 bytes --]

Re: [Bitcoin-development] Two factor wallet with one-time-passwords

[John Dillon]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

On Sun, Jul 28, 2013 at 1:20 AM, Peter Todd <pete@petertodd.org> wrote:
> FWIW with some minor scripting language additions such as access to txin
> and txout contents, along with merklized abstract syntax tree (MAST)
> support, we can even implement a version where scriptPubKey's can be
> reused:

<snip>

>     // Stack now only contains the nonce preceeded by a merkle path linking
>     // that nonce to the tip of a merkle tree over all nonces.
>     //
>     // Verify that path.
>     SWAP // Move direction flag to the top
>     IF
>         SWAP
>     ENDIF

You missed a 'CAT' opcode here.

>     HASH160
>     (repeat above five lines 63 more times)

<snip>

> payment. If they opt for a paper-based one-time-password table they
> simply use the 6 word string as an index to their pre-printed OTP
> encyclopedia set.

I think you should disclose whether or not you have any ties to the pulp and
paper business... By my calculations the production of a single OTP table would
consume roughly half of all the forest biomass on this planet.

> Like the previously described version the security level is still a
> healthy 2^64 - again the attacker needs to find a 64-bit pre-image,
> considered to be a highly difficult task for any attacker unable to
> count from 0 to 2^64 or store a table containing 2^64 values.
>
> There is the disadvantage of the large storage requirements for both
> wallets, however because of the double hashed construction,
> H(H(nonce-secret+i)), neither table needs to be kept secret. Thus
> without loss of security both tables can be easily stored in a
> distributed hash table in the cloud and queried as needed.

ROTFL!

Your idea is better than you realize, you are just too paranoid for your own
good. The thing is the attacker isn't going to be someone paying you funds over
your minimum spending limit, which means the size of the table deriving which
H(nonce) is selected for a given txid:vout can be significantly smaller. For
instance if you want to have 256 total payments before a 50:50 chance of any
pair using the same nonce, you only need a table with ~2^16 elements or with 20
byte hashes just a megabyte of data. It is the 16 level merkle proofs that are
the problem, 16*21=336 bytes of data in the scriptSig. Then again, that's only
4.5x the size of a single signature, not unreasonable.

Also your nested IF statements, while a lovely and hilarious use of MAST, can
be replaced by simply creating the merkle tree over the tuples [i,H(nonce_i)]
and proving that the nonce_i you provided matched the precommitted tree. Now
you only need to provide one merkle proof, not two.

But don't let me discourage you, rarely do I see elaborate jokes that also meet
the criteria to be a least publishable unit. :)
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)

iQEcBAEBCAAGBQJR9WzMAAoJEEWCsU4mNhiP8wIIAJTESdZiIyrfmrJIQad19He0
nPUB1UGdrcRyYBKfk2bxmIgeTppEneISerAzFpfsZk/R1vLSp2zuFvFLMvaTqF0a
nof9dR4ztp753P6O9nLBIK1gcoOagg/FL61Cd1mQzoTjznGioEgk1mCo/Qjb8h9E
I43De70j575bvUkq8RQgijctIt463bM7vfdBC6qtgSziL/xrLUDQEJ6Mhqz3rnmX
+A2+MPHd/aGnRIcBuN6DFQTMXpjXG2y1CIM45e2gPL5x/vSIXqJoJs9tgGyzuFLG
rR34GCsifUKxJyvswG5ue9rNuo5mDkri2jIFx8SlqhfT/b8iWU8JIieoZYGuMiA=
=uhmy
-----END PGP SIGNATURE-----

Re: [Bitcoin-development] Two factor wallet with one-time-passwords

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 2915 bytes --]

On Sat, Jul 27, 2013 at 07:49:18PM -0400, Peter Todd wrote:
> Funding the wallet
> ==================
> 
> As with any multi-party wallet receiving funds must also be handled
> carefully to ensure an attacker can't fool the user into giving the
> sender the wrong address. This requires the involvement of all parties
> required to authorize an outgoing payment. In addition here the
> protection only works if funds sent to the wallet are split up into the
> discrete authorization amounts the user wishes. (possibly with more than
> one amount level)

Quick note for patent prior-art/my own memory - did a talk yesterday
about multifactor wallets, one time passwords and hash digest based
oracles. Someone getting involved in the business of selling bitcoins
pointed out that legally it can actually be desirable to give the
bitcoins to the customer by giving them a physical private key, perhaps
on a sheet of paper in a mailed envelope. Obviously the customer would
be wise to sweep the funds. Of course, the advantage of doing it with
paper is the legal system has a long history of dealing with the concept
of a secret on a piece of paper. (your customers won't have handy PKI to
use after all)

With multi-factor wallets you can have the customer provide one or more
keys, and you give them one final key on a sheet of paper, with
instructions to scan it on their phone via QR-code or something. Now the
transfer is absolute on your end - you can't get the funds back. If it's
a large amount you may want to split it up among multiple addresses, and
deliver the keys to the customer in a way that makes it obvious when
they are revealed. (scratch off for instance)

Finally, one-time-passwords do much the same thing, but they don't
require the second device, and the sheet of paper the customer is
dealing with can be much shorter. Similarly the final approval could
just be done over the phone by telling the customer the ~6-8 magic words
that unlock their funds - legally it could be useful to record that
phone call. Similarly for a large transfer, make it clear how much each
scratched off text field is unlocking to defend yourself in court.

Of course, in both there is still the risk of the funds ending up locked
due to a mistake, but at least there isn't financial incentive to make
that event happen. (usually)

I'll admit I hadn't thought of any of this stuff until I talked to an
actual business with real problems, worth doing.


Finally it's too bad we didn't get OP_EVAL; the customer could have
provided a P2SH script with, well, anything in it, and the unlock could
could have easily been a "bolt-on":

HASH160 <digest> EQUALVERIFY
DUP HASH160 <p2sh-code-digest> EQUALVERIFY EVAL

Oh well, MAST support can do the same thing one day.

-- 
'peter'[:-1]@petertodd.org
000000000000002f3613b5394e39a254ba4afa9f76af72cd6b4273736d7987fb

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]