Received: from sog-mx-4.v43.ch3.sourceforge.com ([172.29.43.194] helo=mx.sourceforge.net) by sfs-ml-4.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1XWXNj-0004Yr-IM for bitcoin-development@lists.sourceforge.net; Tue, 23 Sep 2014 21:12:19 +0000 Received-SPF: pass (sog-mx-4.v43.ch3.sourceforge.com: domain of gmail.com designates 209.85.223.194 as permitted sender) client-ip=209.85.223.194; envelope-from=memwallet.info@gmail.com; helo=mail-ie0-f194.google.com; Received: from mail-ie0-f194.google.com ([209.85.223.194]) by sog-mx-4.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1XWXNa-0003zN-Df for bitcoin-development@lists.sourceforge.net; Tue, 23 Sep 2014 21:12:19 +0000 Received: by mail-ie0-f194.google.com with SMTP id tr6so1923361ieb.1 for ; Tue, 23 Sep 2014 14:12:04 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.50.79.232 with SMTP id m8mr10783112igx.0.1411506724664; Tue, 23 Sep 2014 14:12:04 -0700 (PDT) Received: by 10.107.157.130 with HTTP; Tue, 23 Sep 2014 14:12:04 -0700 (PDT) Date: Tue, 23 Sep 2014 17:12:04 -0400 Message-ID: From: Mem Wallet To: bitcoin-development@lists.sourceforge.net Content-Type: multipart/alternative; boundary=089e013a0606ebfde00503c2049d X-Spam-Score: -0.6 (/) X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. See http://spamassassin.org/tag/ for more details. -1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for sender-domain 0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider (memwallet.info[at]gmail.com) -0.0 SPF_PASS SPF: sender matches SPF record 1.0 HTML_MESSAGE BODY: HTML included in message -0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from author's domain 0.1 DKIM_SIGNED Message has a DKIM or DK signature, not necessarily valid -0.1 DKIM_VALID Message has at least one valid DKIM or DK signature X-Headers-End: 1XWXNa-0003zN-Df Subject: [Bitcoin-development] cryptographic review requested X-BeenThere: bitcoin-development@lists.sourceforge.net X-Mailman-Version: 2.1.9 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 23 Sep 2014 21:12:19 -0000 --089e013a0606ebfde00503c2049d Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Hello, I've made a proposal for a standardized ecies scheme for bitcoin communication. To address gmaxwell's criticism, I'd like to also follow up with a proposed change to BIP44, such that a structured wallet would also include a series of identity keys, both addresses which will be used for signing, and public keys which would be used as destinations for encrypted messages. If anyone is familiar with ECIES and would be interested, there is a working implementation at http://memwallet.info/btcmssgs.html, which also includes this whitepaper: Abstract This document describes a scheme for sending signed encrypted messages using bitcoin public and private keys. Motivation PGP and Bitmessage and other secure communications channels exist. This standard allows for secure messaging using a bitcoin wallet alone, without the need for other software. This standard allows the owner of an address to conveniently prove ownership to the holder of another address privately without the need for separate secure communications channels. Specification= : Message Format In the rest of this text we will assume the public key cryptography used in Bitcoin. The || operator is concatenation. All operations are defined over binary, and not text conversion of the data. When serializing public keys the compressed encoding is always used, even if the input parameters are passed as uncompressed. Bitcoin addresses are always serialized from compressed public keys, and for mainnet. (directives to use testnet or uncompressed keys ignored) String literals are represented as if for the C programming language in native UTF-8. No assumptions are made about the payload message format, it may even be binary. Caveat Decryptor. Plain unformatted text message payloads are recommended to use utf-8. - CompactSize format is a variable size little endian length field serialization format, know as a bitcoin "Variable length integer" - CompactSizePrefix(X) =3D CompactSize(X) || X - QTHASH(x) =3D SHA256((SHA256( CompactSizePrefix("Bitcoin Signed Message:\n") || CompactSizePrefix(x) ) This standard assumes the reader is familiar with the bitcoin compact signature format, which is a 65 byte signature which allows the verifier to recover the public key associated with the signature, eliminating the need to send it with the message. Once consequence of this format is that signatures of tampered messages will nearly always result in some public key, but it will not be the same as the orignial signing key. The address of the sender will be provided to enable validation of the signature. The format is a 1 byte recid, followed by ECDSA R then S values. - CompactSign( PrivateKey, 32 byte QT Hash ) =3D=3D 65 byte message - CompactVerify( 65 byte message, 32 bytes Hash ) public key counterpart of (PrivateKey) - ECIES with HMAC_SHA256 for mac, PBKDF2 for KDF - PBKDF2 is used with 2048 iterations, salt=3D( "Bitcoin Secure Message" || ecies_nonce_publickey ) - AES is used with 256 bit keys, and CFB mode, with a 128 bit feedback buffer. No padding or envelope, simply a pure byte cipher - compact_signed_message =3D 0x01 || CompactSizePrefix(M) || Sender_Address || Signature - compact_unsigned_message =3D 0x00 || CompactSizePrefix(M) - Secure message format: ECIES( compact_signed_message or compact_unsigned_message ) Summary of the functions defined: - eM =3D SendMessage( M, Signing_Key, Dest_Pub ) - M,Sender_Address =3D ReceiveMessage( eM, Decrypting_Key ) It is acceptable for deterministic nonces to be used for signatures, however nonces generated for ECIES must be high quality random bytes. (excepting unit test vectors) Message Sending Inputs: - The message to send "M" (treat as precise binary bytes, no space stripping or normalization) - The bitcoin private key "Signing_Key" to be used to sign the message - The bitcoin public key "Dest_Pub" to be used as the destination of the message Algorithm Calculations: - Calculate the QTHASH(M) to obtain "M_hash", 32 bytes of data - if signing Sign with CompactSign(Signing_Key,M_hash) to obtain "Signature", 65 bytes of data ** Calculate the compressed address of Signing_Key to obtain "Sender_Address" 21 bytes of data ** Serialize 0x0= 1 || CompactSizePrefix(M) || Sender_Address || Signature to obtain "Signed_Message" - if not signing, instead Serialize 0x00 || CompactSizePrefix(M) to obtain "Unsigned_Message" - Generate 32 random bytes "ecies_nonce_bytes" - Generate a bitcoin private key from ecies_nonce_bytes, "Nonce_Key" 32 bytes of data (retry if invalid) - Derive the compressed public key of Nonce_Key, "Nonce_Pub", 33 bytes of data - ECMultiply Dest_Pub by Nonce_Key to obtain the point "Shared_Secret_Point" - Serialize Shared_Secret_Point as a compressed point "Shared_Secret" - Derive "KeyingBytes" =3D PBKDF2( Shared_Secret ) to get 80 bytes of da= ta - Directly Derive "AES256_Key" from the first 32 bytes of KeyingBytes (index 0 to 32) - Directly Derive "HMAC_Key" from the second 32 bytes of KeyingBytes (index 32 to 64) - Directly Derive "AES_IV" from the last 16 bytes of KeyingBytes (index 64 to 80) - Encrypt Signed_Message or Unsigned_Message using AES256_cfb_128 using AES_IV and AES256_Key to obtain "Encrypted_Payload". Same length as M - Compute the HMAC_SHA256 of Encrypted_Payload using HMAC_Key, truncate to the first 8 bytes to obtain "Message_HMAC" Serialization output - Serialize Nonce_Pub || Encrypted_Payload || Message_HMAC to obtain "eM" For text transmission eM may be sent encoded with base 64, otherwis= e binary is preferred. Message Receiving Inputs: - The message received "eM" (decode from base64 if needed) - The bitcoin private key "Decrypting_Key" to be used to decode the message Algorithm Calculations: - Deserliaize eM to recover "Nonce_Pub", "Encrypted_Payload", and "Message_HMAC" - ECMultiply Nonce_Pub by Decrypting_Key to recover "Shared_Secret_Point" - Serialize Shared_Secret_Point as a compressed point to yield "Shared_Secret", 33 bytes of data - Derive "KeyingBytes" =3D PBKDF2( Shared_Secret ) to get 80 bytes of da= ta - Directly Derive "AES256_Key" from the first 32 bytes of KeyingBytes (index 0 to 32) - Directly Derive "HMAC_Key" from the second 32 bytes of KeyingBytes (index 32 to 64) - Directly Derive "AES_IV" from the last 16 bytes of KeyingBytes (index 64 to 80) - Compute the HMAC_SHA256 of Encrypted_Payload using HMAC_Key, truncate to the first 8 bytes to compare with Message_HMAC - If the Message_HMAC did not match, the message is corrpted so abort - Decrypt Encrypted_Payload using AES256_cfb, AES_IV and AES256_Key to recover "Payload_Message" - Verify that the first byte is a 0x01 or 0x00, else abort. 0x01 indicates signed - if signed Deserialize "Payload_Message" to obtain "M", "Sender_Address", and "Signature" - if not signed Deserialize "Payload_Message" to obtain "M", and return M - Calculate the QTHASH(M) to obtain "M_hash", 32 bytes of data - Call CompactVerify(Signature, M_hash) to obtain "Signing_Pubkey" - Calculate the compressed address of Signing_Pubkey to obtian "Sender_Address_check" 21 bytes of data - Compare Sender_Address_check and Sender_Address, if they are not identical, fail/stop Output: - Output Sender_Address to indicate who the mesage is from, and that the signature is valid and untampered with - Output M, considering it is valid and the content untampered with Test Vectors By convention keys will be in WIF format, public keys in base58_check format, messages in c style UTF-8 string literals. Encrypted messages are in Base64 format. Compliant implementations will use random nonces from a cryptographically strong DRBG. For the units tests, they will be provided in hex format. The nonce bytes provided are to be used both for the ECIES ecies_nonce_bytes, as well as for the Signature algorithm. Test vector 1 - M =3D "Hello, World!\n" - nonce bytes =3D 7357000000000000000000000000000000000000000000000000000000000000 - Dest_Pub =3D 6ebngTeKJNTjhVj67YhSw5EBNf6sqdGrz7KAT8kiFRwwL8QjHr - Signing_Key =3D L48ftytpCTGe8GCkfmX1BQoR9yq6DZCoeTsNkxGR4UEiHjQV3uDF - eM =3D A34UI90GVmD1wJ0sMEwSsAaTG6bL+vHE0Ebk078EI7qAHZSWxYBy3rQTKw4XyQUgCnH90pXw= wJRRfPIzlSINTiHm+rs f8hL972pDsnjK5H4mBwu6koi0JCJeisH2j899Z97D9Dy7z9y8V7mW5q3HJDNPiRx99CW2hOD= HOzNlqHSKIItDyqwqMVoHJH7y1rA=3D Decrypting WIF =3D Kwc89APmzQx9bT3u3iUYoCKmhKK4tgcnJih27r9QsxhrHyYY6U8F - Signing_Addr =3D 1LCA11Udyw784zBhN3VQYsRadSUbUpeJrw Test vector 2 - M =3D "Test Message\n=E4=B8=AD=E6=96=87\n" - nonce bytes =3D 00CDEF3636363636363635c5c5c5c5c5c5c5c5c3e3ee3e5c5c5c5c5c53636363 - Dest_Pub =3D 5RARVjiFrm4gBSEc3NQkhqSrmxtixY1Q4NNoQr5fhwK8gMQDLr - Signing_Key =3D L3uN7ev8T5HV8ckp75YgMLzG6ijZ1AYAL8vKBubvvSmLw72yey4x - eM =3D AjUnA/xZbNa1uXu/fh2ZrEDFWNtpwBe5lQi4qRoTzUo6RF5EByEZ4n/eZmWk7MaHViGeO4yP= XhQYyTK4O5XbRknXon4ApQcxsh EaTj0QfoDLYYZ2/CL9p9G8aN2RCoXdcDrYwZ7KyRLdFnCZvUuvv4VZNZW8/h4fT7sf0MKl7H= 9eCv9OVaKwPJe2pyaNDshfzY12FMQ=3D - Decrypting WIF =3D L5UxEELoqFr8eri8nsrBUX2YFmLKZYG6oYBjEUpRSnXwvofdfbg= M - Signing_Addr =3D 1HxcmSvFiviw1RDyzoPgktJfzgKcJ4pHeh Implementations http://memwallet.info/btcmssgs.html Acknowledgements Implementation by: 76NPRHE2g5pSvbLgP8fEEtBvfPB4zte56veXdxXfaXcsQwRjZB aka 1Lk96ASyr3k6ZoTFGLrUgxGuctNKF24V5q Credit Must be given to bitaddress.org brainwallet.org, and many others who have made crypto and bitcoin easy to code for in javascript. --089e013a0606ebfde00503c2049d Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
Hello,
I've made a p= roposal for a standardized ecies scheme for bitcoin
communication. To ad= dress gmaxwell's criticism, I'd like to also
follow up wit= h a proposed change to BIP44, such that a structured
wallet would also i= nclude a series of identity keys, both addresses
which will be used for = signing, and public keys which would be used
as destinations for e= ncrypted messages.

If anyone is familiar with ECIES and would = be interested, there is a
working implementation at http://memwallet.info/btcmssgs.html,
which also includes this whitepaper:

Abstract

This document describes a scheme for sending signed encrypted messages usin= g bitcoin public and private keys.

Motivation

PGP and Bitmessage and other secure communications channels exist. This standard allows for secure messaging using a bitcoin wallet alone, without = the need for other software. This standard allows the owner of an address to conveniently prove ownership to the holder of another address privately wit= hout the need for separate secure communications channels.

Specification: Message Format

In the rest of this text we will assume the public key cryptography used in Bitcoin. The || operator is concatenation. All operations are defined over binary, and not text conversion of the data. When serializing public keys the compressed encoding is always used, even if the input parameters are passed as uncompressed. Bitcoin addresses are always serialized from compressed public keys, and for mainnet. (directives to use testnet or uncompressed keys ignored) String literals are represented as if for the C programming language in native UTF-8. No assumptions are made about the payload message format, it may even be binary. Caveat Decryptor. Plain unformatted text message payloads are recommended to use utf-8.
  • CompactSize format is a variable size little endian length field se= rialization format, know as a bitcoin "Variable length integer"
  • CompactSizePrefix(X) =3D CompactSize(X) || X
  • QTHASH(x) =3D SHA256((SHA256( CompactSizePrefix("Bitcoin Sign= ed Message:\n") || CompactSizePrefix(x) )

This standard assumes the reader is familiar with the bitcoin compact si= gnature format, which is a 65 byte signature which allows the verifier to recover the publi= c key associated with the signature, eliminating the need to send it with the message. Once consequence of this format is that signatures of tampered messages wil= l nearly always result in some public key, but it will not be the same as the orignial sign= ing key. The address of the sender will be provided to enable validation of the sign= ature. The format is a 1 byte recid, followed by ECDSA R then S values.

  • CompactSign( PrivateKey, 32 byte QT Hash ) =3D=3D 65 byte messa= ge
  • CompactVerify( 65 byte message, 32 bytes Hash ) public key counter= part of (PrivateKey)
  • ECIES with HMAC_SHA256 for mac, PBKDF2 for KDF
  • PBKDF2 is used with 2048 iterations, salt=3D( "Bitcoin Secure= Message" || ecies_nonce_publickey )
  • AES is used with 256 bit keys, and CFB mode, with a 128 bit feedba= ck buffer. No padding or envelope, simply a pure byte cipher
  • compact_signed_message =3D 0x01 || CompactSizePrefix(M) || Sender_= Address || Signature
  • compact_unsigned_message =3D 0x00 || CompactSizePrefix(M)
  • Secure message format: ECIES( compact_signed_message or compact_un= signed_message )

Summary of the functions defined:

  • eM =3D SendMessage( M, Signing_Key, Dest_Pub )
  • M,Sender_Address =3D ReceiveMessage( eM, Decrypting_Key ) It is acceptable for deterministic nonces to be used for signatures, howeve= r nonces generated for ECIES must be high quality random bytes. (excepting unit test vectors)

Message Sending

Inputs:
  • The message to send "M" (treat as precise binary bytes, n= o space stripping or normalization)
  • The bitcoin private key "Signing_Key" to be used to sign= the message
  • The bitcoin public key "Dest_Pub" to be used as the dest= ination of the message Algorithm Calculations:
  • Calculate the QTHASH(M) to obtain "M_hash", 32 bytes of = data
  • if signing Sign with CompactSign(Signing_Key,M_hash) to obtain &qu= ot;Signature", 65 bytes of data ** Calculate the compressed address of Signing_Key to obtain "Sender_A= ddress" 21 bytes of data ** Serialize 0x01 || CompactSizePrefix(M) || Sender_Address || Signature to= obtain "Signed_Message"
  • if not signing, instead Serialize 0x00 || CompactSizePrefix(M) to = obtain "Unsigned_Message"
  • Generate 32 random bytes "ecies_nonce_bytes"
  • Generate a bitcoin private key from ecies_nonce_bytes, "Nonce= _Key" 32 bytes of data (retry if invalid)
  • Derive the compressed public key of Nonce_Key, "Nonce_Pub&quo= t;, 33 bytes of data
  • ECMultiply Dest_Pub by Nonce_Key to obtain the point "Shared_= Secret_Point"
  • Serialize Shared_Secret_Point as a compressed point "Shared_S= ecret"
  • Derive "KeyingBytes" =3D PBKDF2( Shared_Secret ) to get = 80 bytes of data
  • Directly Derive "AES256_Key" from the first 32 bytes of = KeyingBytes (index 0 to 32)
  • Directly Derive "HMAC_Key" from the second 32 bytes of K= eyingBytes (index 32 to 64)
  • Directly Derive "AES_IV" from the last 16 bytes of Keyin= gBytes (index 64 to 80)
  • Encrypt Signed_Message or Unsigned_Message using AES256_cfb_128 us= ing AES_IV and AES256_Key to obtain "Encrypted_Payload". Same length as M
  • Compute the HMAC_SHA256 of Encrypted_Payload using HMAC_Key, trunc= ate to the first 8 bytes to obtain "Message_HMAC"

Serialization output

  • Serialize Nonce_Pub || Encrypted_Payload || Message_HMAC to obt= ain "eM" For text transmission eM may be sent encoded with base 64, otherwise binary= is preferred.

Message Receiving

Inputs:
  • The message received "eM" (decode from base64 if needed)
  • The bitcoin private key "Decrypting_Key" to be used to d= ecode the message Algorithm Calculations:
  • Deserliaize eM to recover "Nonce_Pub", "Encrypted_P= ayload", and "Message_HMAC"
  • ECMultiply Nonce_Pub by Decrypting_Key to recover "Shared_Sec= ret_Point"
  • Serialize Shared_Secret_Point as a compressed point to yield "= ;Shared_Secret", 33 bytes of data
  • Derive "KeyingBytes" =3D PBKDF2( Shared_Secret ) to get = 80 bytes of data
  • Directly Derive "AES256_Key" from the first 32 bytes of = KeyingBytes (index 0 to 32)
  • Directly Derive "HMAC_Key" from the second 32 bytes of K= eyingBytes (index 32 to 64)
  • Directly Derive "AES_IV" from the last 16 bytes of Keyin= gBytes (index 64 to 80)
  • Compute the HMAC_SHA256 of Encrypted_Payload using HMAC_Key, trunc= ate to the first 8 bytes to compare with Message_HMAC
  • If the Message_HMAC did not match, the message is corrpted so abor= t
  • Decrypt Encrypted_Payload using AES256_cfb, AES_IV and AES256_Key = to recover "Payload_Message"
  • Verify that the first byte is a 0x01 or 0x00, else abort. 0x01 in= dicates signed
  • if signed Deserialize "Payload_Message" to obtain "= M", "Sender_Address", and "Signature"
  • if not signed Deserialize "Payload_Message" to obtain &q= uot;M", and return M
  • Calculate the QTHASH(M) to obtain "M_hash", 32 bytes of = data
  • Call CompactVerify(Signature, M_hash) to obtain "Signing_Pubk= ey"
  • Calculate the compressed address of Signing_Pubkey to obtian "= ;Sender_Address_check" 21 bytes of data
  • Compare Sender_Address_check and Sender_Address, if they are not i= dentical, fail/stop

Output:

  • Output Sender_Address to indicate who the mesage is from, and t= hat the signature is valid and untampered with
  • Output M, considering it is valid and the content untampered with

Test Vectors

By convention keys will be in WIF format, public keys in base58_check forma= t, messages in c style UTF-8 string literals. Encrypted messages are in Base64 format. Compliant implementations will use random nonces from a cryptographically strong DRBG. For the units tests, they will be provided i= n hex format. The nonce bytes provided are to be used both for the ECIES ecies_nonce_bytes, as well as for the Signature algorithm.

Test vector 1

  • M =3D "Hello, World!\n"
  • nonce bytes =3D 73570000000000000000000000000000000000000000000000= 00000000000000
  • Dest_Pub =3D 6ebngTeKJNTjhVj67YhSw5EBNf6sqdGrz7KAT8kiFRwwL8QjHr
  • Signing_Key =3D L48ftytpCTGe8GCkfmX1BQoR9yq6DZCoeTsNkxGR4UEiHjQV3u= DF
  • eM =3D A34UI90GVmD1wJ0sMEwSsAaTG6bL+vHE0Ebk078EI7qAHZSWxYBy3rQTKw4= XyQUgCnH90pXwwJRRfPIzlSINTiHm+rs f8hL972pDsnjK5H4mBwu6koi0JCJeisH2j899Z97D9Dy7z9y8V7mW5q3HJDNPiRx99CW2hODHOz= NlqHSKIItDyqwqMVoHJH7y1rA=3D Decrypting WIF =3D Kwc89APmzQx9bT3u3iUYoCKmhKK4tgcnJih27r9QsxhrHyYY6U8F
  • Signing_Addr =3D 1LCA11Udyw784zBhN3VQYsRadSUbUpeJrw

Test vector 2

  • M =3D "Test Message\n=E4=B8=AD=E6=96=87\n"
  • nonce bytes =3D 00CDEF3636363636363635c5c5c5c5c5c5c5c5c3e3ee3e5c5c= 5c5c5c53636363
  • Dest_Pub =3D 5RARVjiFrm4gBSEc3NQkhqSrmxtixY1Q4NNoQr5fhwK8gMQDLr
  • Signing_Key =3D L3uN7ev8T5HV8ckp75YgMLzG6ijZ1AYAL8vKBubvvSmLw72yey= 4x
  • eM =3D AjUnA/xZbNa1uXu/fh2ZrEDFWNtpwBe5lQi4qRoTzUo6RF5EByEZ4n/eZmW= k7MaHViGeO4yPXhQYyTK4O5XbRknXon4ApQcxsh EaTj0QfoDLYYZ2/CL9p9G8aN2RCoXdcDrYwZ7KyRLdFnCZvUuvv4VZNZW8/h4fT7sf0MKl7H9eC= v9OVaKwPJe2pyaNDshfzY12FMQ=3D
  • Decrypting WIF =3D L5UxEELoqFr8eri8nsrBUX2YFmLKZYG6oYBjEUpRSnXwvof= dfbgM
  • Signing_Addr =3D 1HxcmSvFiviw1RDyzoPgktJfzgKcJ4pHeh

Implementations

http://memwallet.info/btcms= sgs.html

Acknowledgements

Implementation by: 76NPRHE2g5pSvbLgP8fEEtBvfPB4zte56veXdxXfaXcsQwRjZB aka 1= Lk96ASyr3k6ZoTFGLrUgxGuctNKF24V5q Credit Must be given to bitaddress.org brainwallet.org, and many others w= ho have made crypto and bitcoin easy to code for in javascript.


--089e013a0606ebfde00503c2049d--