TOC 
DraftB. Laurie
 Google Ltd.
 D. Thomas
 A. Beresford
 University of Cambridge
 February 19, 2013


Nigori: Storing Secrets in the Cloud

Abstract

Nigori is a protocol for storing secrets in the cloud such that the storage need not be trusted and only a single password is required to access secrets.



Table of Contents

1.  Introduction
    1.1.  Aim
    1.2.  Requirements Language
    1.3.  Octets and Concatenation
    1.4.  Functions
    1.5.  Constants
2.  Key and Salt Derivation
    2.1.  Unassisted Password-based Key Derivation
    2.2.  Assisted Password-based Key Derivation
3.  Authentication
4.  Encryption of Secrets
5.  Encoding of Revisions
    5.1.  Examples
6.  Secret Storage at a Single Server
7.  Secret Storage at Multiple Servers
8.  Administration
9.  Protocol Details
    9.1.  Responses
10.  Algorithms
    10.1.  DSA Signature
    10.2.  Shamir Secret Split
        10.2.1.  Pre-calculated values for mod_inverse(x, p)
11.  Acknowledgements
12.  IANA Considerations
13.  Security Considerations
14.  References
    14.1.  Normative References
    14.2.  Informative References
§  Authors' Addresses




 TOC 

1.  Introduction



 TOC 

1.1.  Aim

Many computer users own a smartphone, a tablet, and a laptop, as well as making regular use of several desktop machines. As a result, new computer applications are frequently designed to be accessible from many devices, and seamlessly synchronise user data between them. Synchronisation typically uses cloud storage to act as a highly-available intermediary because mobile devices and home desktop machines are not powered and connected to the Internet at all times.

Nigori specifies a standard way to encrypt an associative array and synchronise its contents with a remote server. Nigori uses distributed version control primitives to ensure that updates received from multiple clients do not corrupt the representation of the associative array stored at any client.

The Nigori storage and communication protocol uses a single password provided by the user to generate all the keys required to encrypt and decrypt data stored in the associative array, ensure the integrity of any updates provided by the server, and to sign all messages sent between client and server.



 TOC 

1.2.  Requirements Language

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119] (Bradner, S., “Key words for use in RFCs to Indicate Requirement Levels,” March 1997.).



 TOC 

1.3.  Octets and Concatenation

"abc" represents the octets inside the quoted characters using the UTF-8 character set without termination for interpretation. For example, "abc" is the octets (in hex) 61 62 63.

A | B represents the concatenation of the octets of A and B. For example "abc" | "defgh" represents the octets (in hex) 61 62 63 64 65 66 67 68.

A || B represents the concatenation of the octets of A and B with each octet preceded by its own length represented as a positive integer stored in 4 octets in network byte order. For example, "abc" || "defgh" represents the octets (in hex) 00 00 00 03 61 62 63 00 00 00 05 64 65 66 67 68.



 TOC 

1.4.  Functions

SHA1(M) computes the SHA-1 hash as defined in [RFC3174] (Eastlake, D. and P. Jones, “US Secure Hash Algorithm 1 (SHA1),” September 2001.).

PBKDF2(PRF, P, S, C, dkLen) is the password-based key derivation function specified in [RFC2898] (Kaliski, B., “PKCS #5: Password-Based Cryptography Specification Version 2.0,” September 2000.), where PRF is a pseudorandom function, P is the user-supplied password, S is salt, C is the number of iterations, and dkLen is the output length. In this specification we use PRF = SHA1 since SHA-1 is secure for this purpose and SHA-256 is not permitted by [RFC2898] (Kaliski, B., “PKCS #5: Password-Based Cryptography Specification Version 2.0,” September 2000.).

HMAC(K, M) is the hash-based message authentication code of M with key K and hash function SHA-256 specified in [RFC2104] (Krawczyk, H., Bellare, M., and R. Canetti, “HMAC: Keyed-Hashing for Message Authentication,” February 1997.).

Enc(K1, K2, P) = R | C | HMAC(K2, C) where R is a random IV for AES-256 and C represents the encryption of plaintext P using AES-256 (see [aes] (National Institute of Standards and Technology, U.S. Department of Commerce, “Advanced Encryption Standard,” November 2001.)) in CBC mode with initial vector R, standard padding (i.e. octets are padded to a multiple of 16) and key K1.

EncDet(K1, K2, K3, P) = G | C | HMAC(K2, C) where G = F1 xor F2 and F1 | F2= HMAC(k3, P) and C represents the encryption of plaintext P using AES-256 in CBC mode with initial vector G, standard padding (i.e. octets are padded to a multiple of 16) and key K1.

DSAPubKey(K) represents the public key defined by the Digital Signature Algorithm (DSA Signature) (DSA) generated using the secret key K.

Sign(K, M) = S where S represents the signature of message M using DSA with the secret key K.

Verify(PK, M, S) returns true iff S is a valid DSA signature of message M using public key PK.



 TOC 

1.5.  Constants



NameValueNotes
Nsalt 1000 [1]
Nuser Nsalt + 1 [1]
Nenc Nsalt + 2 [1]
Nmac Nsalt + 3 [1]
Niv Nsalt + 4 [1]
Nmaster Nsalt + 5 [1]
Bsuser 16 size in octets for Suser, must be at least 10 for FIPS-198 compliance with HMAC-SHA1
Bkdsa 32 size in octets for Kuser
Bkenc 32 symmetric encryption key size (currently AES-256) (Kenc)
Bkmac 16 encryption MAC key size (Kmac)
Bkiv 16 iv HMAC key size (Kiv)
Bkmaster 16 size in octets of Kmaster
Usersalt "user salt" non-terminated ascii string used as salt for user key derivation.

[1] should be at least 1000 and different from other N values - the properties of PBKDF2 then ensure that no key can be derived from any other key.

 Constants 



 TOC 

2.  Key and Salt Derivation

Four keys are required for the Nigori protocol

Kuser represents the private component of the user authentication key and is used to authenticate the user to the Nigori server(s). Note that this is used in a way which does not give an eavesdropper a dictionary attack against the master password from which it is derived.

Kenc represents the secret encryption key and is used to encrypt the user's secrets at the Nigori server(s)

Kmac represents the secret authentication key and is used to generate a message authentication code to authenticate the encrypted secrets.

Kiv: is a deterministic initial vector generation key and is used to deterministically generate an initial vector given a plaintext. This prevents common prefix attacks when deterministic encryption is required.

There are two specified mechanisms for key derivation: (1) client-side key derivation with no recovery, and (2) assisted key derivation which allows password recovery via a trusted third party.

Both key derivation methods use the same per-user, per-server, salt value:

Suser = PBKDF2(Username || Servername, Usersalt, Nsalt, Bsuser)

Where Servername = Sname | ":" | Port. Sname is the DNS name or IP address of the server and Port is the port to connect to (i.e. 443 for https). Username is the UTF-8 representation of the username, this MUST be unqiue to the user and per store e.g. a suitably large random string (>128 bits), email address or phone number plus some store specific string.



 TOC 

2.1.  Unassisted Password-based Key Derivation

In unassisted password-based key derivation, the only input is the user's master password, P. Keys are derived as follows:

Kuser = PBKDF2(P, Suser, Nuser, Bkdsa)

Kenc = PBKDF2(P, Suser, Nenc, Bkenc)

Kmac = PBKDF2(P, Suser, Nmac, Bkmac)

Kiv = PBKDF2(P, Suser, Niv, Bkiv)

If the user forgets the password, there is no way to recover the various keys, unless either the password or the derived keys are escrowed in some way. Such escrow is outside the scope of this protocol.



 TOC 

2.2.  Assisted Password-based Key Derivation

Note: this has not been implemented.

In this mode, the user has an account at some server which will supply a master encryption key, Kmaster, if the user successfully authenticates. The means by which the username and the master key is retrieved from the user or server is outside the scope of this document. We recommend that the server derive the master key from a salted hash of the user's password stored at the server, denoted PHash. This will typically be the password used when the user logs in. Kmaster can then be derived as follows:

Kmaster = PBKDF2(PHash, Sserver, Nmaster, Bkmaster)

where Sserver is a secret known only to the server. This prevents dictionary attacks to try to derive the password from Kmaster. If the user forgets his password, the server can still derive Kmaster from the old password hash once the user has recovered his account. However, obviously, the server can also derive Kmaster without the assistance of the user.

Keys for Nigori are then derived as follows:

Kuser = PBKDF2(Kmaster, Suser, Nuser, Bsuser)

Kenc = PBKDF2(Kmaster, Suser, Nenc, Bkenc)

Kmac = PBKDF2(Kmaster, Suser, Nmac, Bkmac)

Kiv = PBKDF2(Kmaster, Suser, Niv, Bkiv)

If the user forgets their password there is now the possibility of account recovery using traditional recovery mechanisms. Note that the client should be able to cache Kmaster so it doesn't always have to contact the server.



 TOC 

3.  Authentication

When the user registers at a server, he presents DSAPubKey(Kuser) and a token asserting his right to do so. The token is used to support any administration features such as restrictions on creating accounts or quotas as discussed in Section 8 (Administration). Servers which require no token MUST accept the empty octet array and clients SHOULD default to the empty octet array.

To authenticate a message M to the server the client sends:

SHA1(DSAPubKey(Kuser)), S, T, R, M, DSASign(Kuser, S || T || R || C || M)

where S is the server name, T is the time in seconds since 1st January 1970, R is a (32 bit) nonce, C is the command as defined in Section 9 (Protocol Details) and the output of DSASign is defined in Section 10.1 (DSA Signature). At least one field must be different every time a message is sent to the server, therefore clients MUST ensure that T || R is different for every request. The server MUST check that S || T || R || M has not been seen before; to enable it to do so without keeping an unbounded database of old requests, the server MUST reject messages whose value of T is not recent as invalid requests.

If S || T || R || M has not been seen before, and the signature is correct, the message is deemed authentic and it's contents processed as described later in this document. If the signature does not match, the message MUST be rejected as invalid.



 TOC 

4.  Encryption of Secrets

Each value stored in the associative array on the server consists of three components, an Index into the array, a Revision summarising the history of previous values seen by the client (see Section 5 (Encoding of Revisions)), and the Value itself. These values are encrypted as EIndex, ERevision and EValue respectively. The encrypted values are calculated as follows:

EIindex = EncDet(Kenc, Kmac, Kiv, index).

ERevision = EncDet(Kenc, Kmac, Kiv, revision).

EValue = Enc(Kenc, Kmac, V).



 TOC 

5.  Encoding of Revisions

To allow for distributed asynchronous access to the nigori store, revisions are required which encode a directed acyclic graph (DAG) of the history of a value. This encoding needs to be deterministic so that it can be performed on multiple devices and detect any interference with past history (such as the removal of old revisions) by the server. It also needs to encode sufficient information that it is not necessary to download the values to construct the DAG.

The octet array (in network byte order) of a revision is consists of a list of ID || RevList pairs where the size of the ID is the size of the output of SHA-1 and RevList consists of a (possibly empty) lexicographically sorted sequence of ID entries for the revisions immediately preceding the current one (e.g. 'ID1 || ID2 || ID3').

The ID is constructed as SHA1(Value || RevList)



No parents case:
 0                   1                   2
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0 0 1 0|         ID = SHA-1(value)     |0 0 0 0|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
At least one parent case:
 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0 0 1 0|   ID = SHA-1(value,revlist)   |X X X X|0 0 1 0| First
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  parent revision ID    |0 0 1 0|   Second parent revision ID   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0 0 1 0|          And so on...         |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Note that one tick mark represents one octet position. Octets 20 onward constitute the revlist which is hashed using SHA-1 when generating the ID.

 Revision format 

Future specifications may require functions other than SHA-1, if they do they MUST use a different size for the hash output (i.e. not 16 bytes).

Revision history diverges if multiple revisions specify the same revision(s) as their parent (or if multiple revisions specify no parent). Revision history can be merged again if a new revision specifies a revlist of multiple parents as then that new revision supersedes all its parents.

By examining the DAG of revision history a client can determine which revisions form the set of dominating or head revisions. The head revisions can then be presented as multiple options to the user. Alternatively the client can perform an automatic merge on these head revisions to produce a single value to show to the user and possibly commit this back to the server.

This scheme is similar to that used in Git and Mercurial.



 TOC 

5.1.  Examples



    +-+-+-+-+
    | F:D,E |
    +-+-+-+-+
     /   \
+-+-+-+ +-+-+-+-+
| D:B | | E:B,C |
+-+-+-+ +-+-+-+-+
^       ^   ^
|       /   |
|      /    |
+-+-+-+     +-+-+-+
| B:A |     | C:A |
+-+-+-+     +-+-+-+
      ^     ^
      |     |
      +-+-+-+
      | A:  |
      +-+-+-+

Here revision IDs have been abbreviated to the first character of their hex representation. Revision A specifies no parent, both B and C specify A as their parent, E merges B and C but D depends only on B, F specifies D and E as its parents and so merges them resulting in one head revision.

 Example DAG of revision history 



 TOC 

6.  Secret Storage at a Single Server

The client and server communicate by means of messages with the client sending requests and receiving responses.

The following message types are defined with detailed specification in Section 9 (Protocol Details):

RegisterRequest used to register at the server.

AuthenticateRequest used to determine that the client can connect to the server and authenticate it is also a component of all the other requests.

UnregisterRequest unregisters the user.

GetRequest request revision, value pair(s) from the server.

GetResponse the revision, value pair(s) requested.

GetIndicesRequest request the list of indices held by the server

GetIndicesResponse the list of indices requested.

GetRevisionsRequest request the list of revisions for an index.

GetRevisionsResponse the list of revisions requested.

PutRequest request that a value be put for a particular index and revision.

DeleteRequest delete a particular index or revision.



 TOC 

7.  Secret Storage at Multiple Servers

Note: This is not yet implemented in Java though it is implemented in Python.

This looks exactly the same to each server as storage at a single server would. However, the client takes the value, V, it would store at a single server and splits it using a Shamir split (Shamir Secret Split), with the k value (number of splits required for reconstruction) as determined by the user (n is equal to the number of servers). Each split is then stored at server i as Enc(Kenc, Kmac, i || Si).



 TOC 

8.  Administration

Details of how administrative access to the storage server are provided are as yet undefined.

Depending on policy decisions made by the server administrator, registration may be restricted and not open to everyone. To support this there is the opaque token octet array specified during registration which can be interpreted as the server chooses.

Another consideration is limiting the quantity of space which an individual user can use through the imposition of quotas. The server can provide a response (Responses) that indicates the user has insufficient quota to perform the requested operation.

TODO(drt24): some mechanism is required for users to be able to provide some token from which the server can grant them additional resources. Some out of band mechanism is required for obtaining these tokens, perhaps some sort of ecash but that is an unsolved problem.

Administrators will require the ability to view the list of users and of administrators, how much space they are using and what their quota limits are, to delete users, to edit quotas and to create and delete administrators.



 TOC 

9.  Protocol Details

All requests MUST be performed over HTTPS. The client MUST check the certificate is valid, where "check" means that the certificate is in date and it is the same certificate as seen when the user registered with the server.

TODO(drt24): We need to have some mechanism allowing the server to change its certificate.

There are two possible encodings of data being transmitted over HTTPS to the server: JSON (Crockford, D., “The application/json Media Type for JavaScript Object Notation (JSON),” July 2006.) [RFC4627] and Protobuf (Google, “Protocol Buffers,” April 2011.) [protobuf]. Clients and servers MUST implement the JSON encoding and SHOULD implement Protobuf. Protobuf is significantly more efficient but not standardised.

Clients MUST specify which encodings they support in the Accept header they send. If a client supports Protobuf it MUST send: `Accept : application/x-google-protobuf, application/json` If a client only supports JSON it MUST send `Accept : application/json`.

If a server receives a request message with a mimetype it does not support it MUST return 406 (Not Acceptable) with a list of supported mimetypes (Responses).

If a server supports Protobuf and receives a message from a client which indicates support for Protobuf then it should reply with Protobuf regardless of the mimetype of the request.

Clients MAY try Protobuf first without having received a Protobuf response from the server but MUST retry with JSON if this fails with 406 (Not Acceptable) (Responses).

Further mimetypes MAY be added in future but a specification is required. Which mimetype to use should be determined as for Protobuf and JSON with the ordering in the Accept header being used by the server to determine which mimetype the client prefers.

When using JSON all octet strings are transmitted as base64 (Josefsson, S., “The Base16, Base32, and Base64 Data Encodings,” October 2006.) [RFC4648].

It is easy to convert between JSON and Protobuf either statically or dynamically however Protobuf lends itself to providing a specification and a JSON specification does not supply tag numbers which need to be identical for two Protobuf specifications to interoperate. Hence the message specification is given as a .proto file.



package nigori;

message AuthenticateRequest {
  required bytes public_key = 1;
  required bytes sig = 2;
  required bytes nonce = 3;
  required string server_name = 4;
}

message RegisterRequest {
  required bytes public_key = 1;
  required bytes token = 2;
}

message UnregisterRequest {
  required AuthenticateRequest auth = 1;
}

message RevisionValue {
  required bytes revision = 1;
  required bytes value = 2;
}

message GetRequest {
  required AuthenticateRequest auth = 1;
  required bytes key = 2;
  optional bytes revision = 3;
}

message GetResponse {
  repeated RevisionValue revisions = 1;
  optional bytes key = 2;// optional as may want to keep packet size down.
}

message GetIndicesRequest {
  required AuthenticateRequest auth = 1;
}

message GetIndicesResponse {
  repeated bytes indices = 1;
}

message GetRevisionsRequest {
  required AuthenticateRequest auth = 1;
  required bytes key = 2;
}
message GetRevisionsResponse {
  repeated bytes revisions = 1;
  optional bytes key = 2;
}

message PutRequest {
  required AuthenticateRequest auth = 1;
  required bytes key = 2;
  required bytes revision = 3;
  required bytes value = 4;
}

message DeleteRequest {
  required AuthenticateRequest auth = 1;
  required bytes key = 2;
  optional bytes revision = 3;
}

The Protobuf specification is converted to a JSON one by encoding both `bytes` and `string` as base64 (Josefsson, S., “The Base16, Base32, and Base64 Data Encodings,” October 2006.) [RFC4648] strings, and keeping the field names identical.

 Protobuf specification of nigori messages 

Messages are sent to the server by a POST request to [server]/command where command is the result of removing the Request or Response from the string inserting a - between words and making lower case. e.g. GetRequest => get, GetIndicesRequest => get-indices.

The nonce in AuthenticateRequest is a 64 bit value formed by R | T where R is a 32 bit random number and T is the 32 bit integer representing time since epoch in seconds.



 TOC 

9.1.  Responses

Responses are of the form HTTP error code, space, nigori minor error code, description of the error.

200 OK

401 1 Signature does not verify

401 2 This is a replay

403 1 Signature verifies but ACL doesn't

403 1 Insufficient quota

406 1 Request mime type not supported



 TOC 

10.  Algorithms



 TOC 

10.1.  DSA Signature

The Digital Signature Algorithm (DSA) is defined in [FIPS186‑3] (National Institute of Standards and Technology, “Federal Information Processing Standards Publication (FIPS PUB), Digital Signature Standard (DSS),” June 2009.). A public key size (L) of 3072 bits and a private key size (N) of 256 bits gives 128 bits of security Section 5, Table 2 (National Institute of Standards and Technology, “SP 800-57 Recommendation for Key Management – Part 1: General,” March 2007.) [SP800‑57] which is the best that can be achieved while using SHA-1 for key derivation Section 5, Table 3 (National Institute of Standards and Technology, “SP 800-57 Recommendation for Key Management – Part 1: General,” March 2007.) [SP800‑57].

A DSA signature is composed of two components r and s, these are stored in the sig field of the AuthenticateRequest as r || s.

The DSA parameters for a 3072 bit modulus were chosen from the NIST example DSA parameters which are also used for J-PAKE.

P:
90066455 B5CFC38F 9CAA4A48 B4281F29 2C260FEE F01FD610
37E56258 A7795A1C 7AD46076 982CE6BB 956936C6 AB4DCFE0
5E678458 6940CA54 4B9B2140 E1EB523F 009D20A7 E7880E4E
5BFA690F 1B9004A2 7811CD99 04AF7042 0EEFD6EA 11EF7DA1
29F58835 FF56B89F AA637BC9 AC2EFAAB 90340222 9F491D8D
3485261C D068699B 6BA58A1D DBBEF6DB 51E8FE34 E8A78E54
2D7BA351 C21EA8D8 F1D29F5D 5D159394 87E27F44 16B0CA63
2C59EFD1 B1EB6651 1A5A0FBF 615B766C 5862D0BD 8A3FE7A0
E0DA0FB2 FE1FCB19 E8F9996A 8EA0FCCD E5381752 38FC8B0E
E6F29AF7 F642773E BE8CD540 2415A014 51A84047 6B2FCEB0
E388D30D 4B376C37 FE401C2A 2C2F941D AD179C54 0C1C8CE0
30D460C4 D983BE9A B0B20F69 144C1AE1 3F9383EA 1C08504F
B0BF3215 03EFE434 88310DD8 DC77EC5B 8349B8BF E97C2C56
0EA878DE 87C11E3D 597F1FEA 742D73EE C7F37BE4 3949EF1A
0D15C3F3 E3FC0A83 35617055 AC91328E C22B50FC 15B941D3
D1624CD8 8BC25F3E 941FDDC6 20068958 1BFEC416 B4B2CB73

Q:
CFA0478A 54717B08 CE64805B 76E5B142 49A77A48 38469DF7
F7DC987E FCCFB11D

G:
5E5CBA99 2E0A680D 885EB903 AEA78E4A 45A46910 3D448EDE
3B7ACCC5 4D521E37 F84A4BDD 5B06B097 0CC2D2BB B715F7B8
2846F9A0 C393914C 792E6A92 3E2117AB 805276A9 75AADB52
61D91673 EA9AAFFE ECBFA618 3DFCB5D3 B7332AA1 9275AFA1
F8EC0B60 FB6F66CC 23AE4870 791D5982 AAD1AA94 85FD8F4A
60126FEB 2CF05DB8 A7F0F09B 3397F393 7F2E90B9 E5B9C9B6
EFEF642B C48351C4 6FB171B9 BFA9EF17 A961CE96 C7E7A7CC
3D3D03DF AD1078BA 21DA4251 98F07D24 81622BCE 45969D9C
4D6063D7 2AB7A0F0 8B2F49A7 CC6AF335 E08C4720 E31476B6
7299E231 F8BD90B3 9AC3AE3B E0C6B6CA CEF8289A 2E2873D5
8E51E029 CAFBD55E 6841489A B66B5B4B 9BA6E2F7 84660896
AFF387D9 2844CCB8 B6947549 6DE19DA2 E58259B0 90489AC8
E62363CD F82CFD8E F2A427AB CD65750B 506F56DD E3B98856
7A88126B 914D7828 E2B63A6D 7ED0747E C59E0E0A 23CE7D8A
74C1D2C2 A7AFB6A2 9799620F 00E11C33 787F7DED 3B30E1A2
2D09F1FB DA1ABBBF BF25CAE0 5A13F812 E34563F9 9410E73B


 TOC 

10.2.  Shamir Secret Split

Note: This is not yet implemented in the Java code though it is implemented in the Python.

A Shamir secret split takes some secret (a number less than the public parameter, p) and splits it into n components such that any k components can be used to retrieve it. The public parameter is the same for all implementations and is the 4096 bit verified prime:

p =
FFFFFFFFFFFFFFFF C90FDAA22168C234 C4C6628B80DC1CD1 29024E088A67CC74
020BBEA63B139B22 514A08798E3404DD EF9519B3CD3A431B 302B0A6DF25F1437
4FE1356D6D51C245 E485B576625E7EC6 F44C42E9A637ED6B 0BFF5CB6F406B7ED
EE386BFB5A899FA5 AE9F24117C4B1FE6 49286651ECE45B3D C2007CB8A163BF05
98DA48361C55D39A 69163FA8FD24CF5F 83655D23DCA3AD96 1C62F356208552BB
9ED529077096966D 670C354E4ABC9804 F1746C08CA18217C 32905E462E36CE3B
E39E772C180E8603 9B2783A2EC07A28F B5C55DF06F4C52C9 DE2BCBF695581718
3995497CEA956AE5 15D2261898FA0510 15728E5A8AAAC42D AD33170D04507A33
A85521ABDF1CBA64 ECFB850458DBEF0A 8AEA71575D060C7D B3970F85A6E1E4C7
ABF5AE8CDB0933D7 1E8C94E04A25619D CEE3D2261AD2EE6B F12FFA06D98A0864
D87602733EC86A64 521F2B18177B200C BBE117577A615D6C 770988C0BAD946E2
08E24FA074E5AB31 43DB5BFCE0FD108E 4B82D120A9210801 1A723C12A787E6D7
88719A10BDBA5B26 99C327186AF4E23C 1A946834B6150BDA 2583E9CA2AD44CE8
DBBBC2DB04DE8EF9 2E8EFC141FBECAA6 287C59474E6BC05D 99B2964FA090C3A2
233BA186515BE7ED 1F612970CEE2D7AF B81BDD762170481C D0069127D5B05AA9
93B4EA988D8FDDC1 86FFB7DC90A6C08F 4DF435C934063199 FFFFFFFFFFFFFFFF

Because the secret we want to split is in fact an arbitrary sequence of octets, we need to first encode it into a number. We do this by prefixing the octet sequence with a single octet with the value 01 and then interpreting the octet sequence as a bigendian number. When recovering the secret from the split this 01 octet MUST be checked and stripped.

To split:

  1. Create an array, a, of length k.
  2. Set a[0] = secret.
  3. Set a[1] to a[k-1] to random integers in the range [0,p) (i.e. 0 ≤ a[i] < p). Use a cryptographic random number generator.[anchor15] (Ian Goldberg points out that 0 has to be allowed or a small amount of data is leaked: e.g. if k=2 and some share is s, then the secret cannot be s (proof left as an exercise for the reader))
  4. For i in the range 1 to n inclusive, compute poly(a, i) (see below), the result is the i'th share.

poly(a, i):

  1. Set t = 0.
  2. for j in the range 0 to k-1 inclusive, compute t = (t + a[j] * i^j) mod p
  3. return t

To recover the secret:

  1. Retrieve k of the shares.
  2. Set secret = 0.
  3. For each retrieved share, set i to the share number (1 ≤ i ≤ n).
    1. Set c = 1.
    2. For each retrieved share, set j to the share number (1 ≤ j ≤ n)
      1. if i is not equal to j, c = (c * j * mod_inverse(j - i, p)) mod p
    3. secret = (secret + c * share[i]) mod p

That's it.

mod_inverse(x, p) is the inverse of x in Zp - that is, x * mod_inverse(x, p) mod p = 1. Note that many implementations require x to be in the range [1,p) so it may be necessary to calculate mod_inverse((j-i) mod p, p) to avoid an error (note that j-i mod p = j-i if j-i ≥ 0 and = j-i+p if j-i < 0). Also note that since i and j are small and p is fixed, mod_inverse(j-i, p) could be pre-calculated or cached (see below for pre-calculated values).

[anchor16] ([Daniel Bleichenbacher points out: to compute expressions of the form a*b^{-1} mod p, where b is a small integer. An efficient method to do this is to compute k = -a*p^{-1} mod b. Then the integer a + kp is divisible by b and hence a*b^{-1} == (a+kp)/b (mod p). I.e. this method takes O(log(p)log(b)), rather than O(log(p)^2) for the current method. (I have my doubts because of the cache, but I should test it) ])



 TOC 

10.2.1.  Pre-calculated values for mod_inverse(x, p)

mod_inverse(-10, p) =
4ccccccccccccccc bc518e63d6d2a0a9 6e3b83f6a6a86f0b 8c4d7dcf5cb8bd56
009d1f9844ec4823 e52fcf57aaa934a8 fb13214f8a5e4754 f4d9b6542f1c8610
97f6c33a6d988714 f7c1b67050b5f2d5 494a1412e510c739 b6cc9bd07c686a60
faaa86cb67f6164b 4dfc8ad20bb0232b 7c58eb7efa4481c5 ba33589dca0452e8
14417c103bb35914 b920464c4bf17169 743802578efde746 a21daf66a35b326b
7c7325e8a1c6c6ba 6bb6dccab00560ce 486fba02a3073d3e dbf81c4841107111
f77c56f3a0d12834 4825744a7a024a5e 50219c2e87ca18d6 290d2396c6673a20
de132fa5799339ab 202571d42de49b1e 6cd5911b2999a140 e728ed50b47e8b0f
7f4cbd4d29556b1e 471841814ddb9483 29acbb9a3581d08c 1c46eb0e7edd5e3b
e6c9b45d74e92926 ef909310163e6a15 be112571d4d8e120 61f4cb020e0fcf51
7423672292d5b984 7f0959ba6d71bcd0 9ec38700a4b6cf3a 23b60f6d04dac877
02aa4b16897819c1 fac1cecbdd18b82a b040d85699238266 bb224538cbdbf873
dc22149e9f5181be c7ba8bba867caa45 3b2c85a969d31d27 d80df956400c7d79
0eb8540e8175f7b1 27914b9fa31fa331 d8f21ac89786b9b5 ae1bf9e4b02b6de3
d75eb07518685f2d 8969f2d50adda71b 1da1f5a3706e7c08 a4cec5258ce81b32
df83132dc4118f53 a87fea5bc4fed35e 30fc768929350ee1 6666666666666666

mod_inverse(-9, p) =
38e38e38e38e38e3 820385eb23de640b b9f33257e3bf22d9 258ebc01e5de2d6f
1ce62a5dd43d3eeb 2e823ac5add2abbf 8a92e944667eb994 4397c96dc41520ef
d8dcb68a184b0eba 32c86136c086c6d6 e0f480a5b328df6d 1f1c4d7dfd56d38a
34f017fef7acce24 d178b2ae8d660716 baec8883fbc0f7d4 d5c73829076b7fc8
5adb2c7dcd6867e9 6caf9c5e71249fdc 56168679bf40d13d cd6b5284eac84b46
234bd03a8acc216d a51f284a497f3e39 fcc489c9107723e2 b5e73164edd34a46
3294fe09cc750156 227a8f07c2ac5d03 7dba14e018bba09e a3262d533da1cc3e
45af65a9fb3da5fa 04d95dcc93c5c83c 768b3c141ed09d5f 7bd276e672bc8cef
08f67942a35bb7a4 a670c839dadb8a74 1edec3da86731f38 60cc3c5696dcdd81
b46f7c1f4d1e7d4c 3fad766abb24c05b f5162eb32267c334 6e7c70734cc95732
dac4e4199c2c896b a078b43e3e1b5c74 9b875a8537a3dbdf 36e5ac9c9b4cba6b
1e6b2e23a8330999 2b861471158d91e6 bb72675c975cac72 05e07f209701c185
3ac3e9590db7a27a 5b0eec3e50a83246 3ecba5610c04ad4c ebe46cd797bd666c
a29b80a272dc1fc5 98918d59ce2a65ec 08ff3048bc17f1db e9442167073c9d40
799b793a4af7faa6 78c042191187be27 0c77f85323e01006 671de75e2f7c85ec
cb7d89773be714d5 ac38d38659089c91 9f8b9a2cb63a43e9 5555555555555555

mod_inverse(-8, p) =
dfffffffffffffff cfeddf4ddd3ba9ee 2c2d963a10c09937 03e20447791ad2e5
81ca46d173b127be 0720c76a5c6d8442 31a2767d5392fab7 ca25a920341331b0
65e50ebfbfa789fd 27f4fec79612aeee 15c2ba8c7170efbd aa7f71201585e0f0
30715e7bef386bb0 f8cb3f8f4cc1bbe9 80035987af47cfd6 09c06d218d374724
e5beff2f58cb1927 1bf377b3dd803573 92f8b17f610f37e3 58d694eb5c74a864
2afa83e68283c39f ba2aaea481650504 5345de87b0d51d4c ac3e527d686ff474
672aa846950cb543 27c2932e8e86ae3d bf0cb2326162c870 a2665277c2ad1435
3262a04d4d42bd88 7317e15585dac46e 12c43c8f39556ba7 f78cb42b63c66aed
334a7d7663392318 4f5c1463cdc07129 398d232c71654aed fd242d94f205a82e
b676f8bb3fa80d5c 3abb024440e0b56a 150757e15778909e 7309fac5fe58c758
3d674224d6ef5d17 c7db45b5148bbc0b 2464f46c8b1531be e82857a8a37e1e05
c7c605ac6648f5cb 1b5ff07d44dd6e7c 821276fc93fce700 f723f4905296e9fc
976366cea6030fc1 c68ac2355d9645f4 9741db2e1f526a5e e0d36c90e579c34b
c0444a7fa442bd1a 08bd1c919bc6f151 636cce1e649e4851 e67c4385ac7eab2d
ded42d5587306aef 7b750442b5067cb9 c11861c75d423f19 3605bf02dafa4f54
613e4d457bdde209 561fc0e0fe91e87d 6435af100d856b66 bfffffffffffffff

mod_inverse(-7, p) =
6db6db6db6db6db6 c3e23920e9bf2ea8 e69e2a3bc982e7c7 5ab7d84ccd9a330d
2572bf6bd02cf957 d9b203a1cf3add83 afd22f9633621cc2 825b96c167df9af3
223bf25377fe77d4 cfa704a0734d11c2 fafc1cad473c8a52 72db27bc1f7097f8
4185e52294841fd9 4ad67d2c10b27b62 b1a39990d33d4bac c0dba32a8e4f51dd
d3cb4384e7927f42 2d0988ff47eb344d 817495a1a7b3dcae 0c2a68497ba6da50
68a47f4c54d2d2c1 2c29cdb3d6e31c94 677b09ba9fc132ec 15ab961e13ce5862
cf43e9ee5373f04a b035818ef770fc86 bb9dba8b9d69da56 83c9a08e40012e78
18adb1c7d240093d 9ba334e5f86b26bd c00c8626cdb6e65c b7f1530594227d83
da6da0b75f9e9906 aeb4efdd4aa76672 3b890c00deb97311 4cf798f022f318e7
dbfb93f3394d1637 9f60d216fb34978c c661a334e6ecaf52 d5148fb9caf20398
ef0e010cd1c39b4f 90e8c95377c70dbc 50850a00eb4e4c9c 3304160974a642f3
2860fd8de8f4b715 1d14de47ce23503c fbca59a0487bdedb e6c33e51233a3e5c
5f0c1d74e399027e 41e5ec2f094460f5 2ff675cd729b4e38 eb81ad56a4a420f6
150753826fcd18b3 ef61d9bf7b51c490 5a7e6f67b3e5094c af95ae22203e0ab3
33abd782b5276365 9fbbed3058aa5c6f e130837bc5301ee7 c6de3e35a4b94b6d
3f4d891ccef4839c 154905a7abb52df4 45faf27acd2739d4 4924924924924924

mod_inverse(-6, p) =
d555555555555555 278d3631c681f72b f94ffcc9960cc2ae 4cd741071e012a60
ac5f1edfdbe5abf1 ee685c654bd6040e 47a6eac0805b37eb fd79335b9f4f3b83
6d3bac85db19773a 3e6f6c8d51f969a5 cb94e26d5fd945d9 34aa229876059946
468459fc20c8050a 11849e0e923e9a95 3cf6ffeef013a15e 21ab1299dbd31f2f
54b5e6d7c24785ab 57928a622849577a 42d478488d3310a7 c2527572706f1a47
045c4cdb887d7d5b 2b34d716939d2959 73e104b1fdbec692 2a22f93a7bd85687
3daeb8a4beb6c503 014b985d1a065ccd 1779ce485cbf9a52 e3cf29f8271ebde9
8551bd3d6e272e69 922f1fbf2a25aee2 bc8a214b738e4e26 10553de02e431080
619c46b9e497f0a9 7026eed8f4b74733 73c35e73782fb513 6afde244b5bc3ea6
64a21175613255dd eeca7c103dc9d158 d7132f1fc1051c04 9e52a5b05ff306fe
b462576009a70353 99c4a3e968e69ab5 473b937390a67885 0ddd474b465fbb11
b211ed05b6bf63fe 6336cca810d2e321 3eed039b379b86ab 9609dcba364695b3
9c5eab0df370a14a d577f5e9ae76bc87 6b7bac2bed1189e0 7498982879064017
61c722612eb97724 fc21d210c51efe35 21bcf510c159caf8 aabf7d425b234db1
c807069a9921ebf0 44d0f7de01bd0912 6ec1e337c6883c18 02b023a13212f637
fb16c37f20a28e21 45d51937cde04b22 164b8227ab5a7eaa ffffffffffffffff

mod_inverse(-5, p) =
9999999999999999 78a31cc7ada54152 dc7707ed4d50de17 189afb9eb9717aac
013a3f3089d89047 ca5f9eaf55526951 f626429f14bc8ea9 e9b36ca85e390c21
2fed8674db310e29 ef836ce0a16be5aa 92942825ca218e73 6d9937a0f8d0d4c1
f5550d96cfec2c96 9bf915a417604656 f8b1d6fdf489038b 7466b13b9408a5d0
2882f8207766b229 72408c9897e2e2d2 e87004af1dfbce8d 443b5ecd46b664d6
f8e64bd1438d8d74 d76db995600ac19c 90df7405460e7a7d b7f038908220e223
eef8ade741a25068 904ae894f40494bc a043385d0f9431ac 521a472d8cce7441
bc265f4af3267356 404ae3a85bc9363c d9ab223653334281 ce51daa168fd161e
fe997a9a52aad63c 8e3083029bb72906 535977346b03a118 388dd61cfdbabc77
cd9368bae9d2524d df2126202c7cd42b 7c224ae3a9b1c240 c3e996041c1f9ea2
e846ce4525ab7308 fe12b374dae379a1 3d870e01496d9e74 476c1eda09b590ee
0554962d12f03383 f5839d97ba317055 6081b0ad324704cd 76448a7197b7f0e7
b844293d3ea3037d 8f7517750cf9548a 76590b52d3a63a4f b01bf2ac8018faf2
1d70a81d02ebef62 4f22973f463f4663 b1e435912f0d736b 5c37f3c96056dbc7
aebd60ea30d0be5b 12d3e5aa15bb4e36 3b43eb46e0dcf811 499d8a4b19d03665
bf06265b88231ea7 50ffd4b789fda6bc 61f8ed12526a1dc2 cccccccccccccccc

mod_inverse(-4, p) =
bfffffffffffffff d6cbe3f9990e91a7 9394c9e8a0a5159c dec1ba8667cdd957
0188cefcac4eb459 bcf7865b2aa703a6 73afd346d9ebb254 642047d275c74f29
7be8e81211fd51b4 6b644818c9c6df15 3739322f3ca9f210 48ff8589370509f2
72aa50fc83e737bc 42f75b0d1d3857ec b6de4cbd71ab446e 51805d8a790acf44
32a3b62895405eb3 ced0afbebddb9b87 a28c05dae57ac230 954a36809863fe0c
b71fdec59470f0d2 0d4927fab80d7203 b51751069792191d 25ec46b4a2a91aac
eab6d961120ae482 b45da2ba3105b9eb c854067453793e17 66a0d8f8f0021152
2b2ff71daff0102b d05d9c9272bb83cc 1015eac3e8001322 41e65149c33c5ba6
be3fd940e7558bcb b1bca3c342a4f347 e82fd50185c4895e 46b14ba43d296b95
c0f842e9a446e6e1 56e96fa8379c0936 5b2add9c941e32d0 f4e3fb852327864b
a25881d66f164fcb 3d976052119c5809 8ce8d1819bc90611 594726908c22f529
86a9bbb857ac4064 f2e484fda8bdcc6a b8a21cd87ed8c600 d3d5ad0dfda5ed21
a655338c8e4bc45c f3525d525037a9ad 13ef4e27888fc8e3 9c22ef57a01f39ae
a4ccd22443a6eb3a e2eb3d0f17cf17fc 9e5d42f57ad0d046 3345f0bbb86c92b9
9a6cb924bd04edf1 d788df149b2a21c3 ca14e61899143615 9c04ecdde04443ff
2ec7aff26a2be651 253fc9e56c7d106b 7a772856e704a533 7fffffffffffffff

mod_inverse(-3, p) =
aaaaaaaaaaaaaaaa 860a91c16b9b2c23 2dd99707ab3d688b 70ac3405b19a884d
56b27f197cb7bcc1 8b86b0510978033e 9fb8bbcd337c2cbc cac75c494c3f62cf
8a96239e48e12c2e 985923a441945484 a2dd81f1197a9e47 5d54e879f8047a9e
9ed047fce7066a6e 746a180ba8321544 30c5998bf342e77e 8155a87b16427f59
10918579683937bc 460ed51b536ddf95 0243936d3dc273b9 6841f78ec058e1d2
69e370afa0646448 ef5d78dedc7dbaad f64d9d5b31656ba8 21b5942ec979ded2
97befa1d655f0402 676fad174805170a 792e3ea04a32e1db e97287f9b8e564ba
d10e30fdf1b8f1ee 0e8c1965bb5158b5 63a1b43c5c71d81e 737764b35835a6cd
1ae36bc7ea1326ed f35258ad90929f5c 5c9c4b8f93595da9 2264b503c4969885
1d4e745de75b77e4 bf086340316e4113 df428c196737499d 4b755159e65c0598
904eac4cd4859c42 e16a1cbaba52155d d2960f8fa6eb939d a4b105d5d1e62f41
5b418a6af8991ccb 82923d5340a8b5b4 32573615c6160556 11a17d61c505448f
b04bbc0b2926e76f 112cc4baf1f896d2 bc62f023240e07e6 c3ad4686c7383345
e7d281e758945f50 c9b4a80d6a7f31c4 1afd90da3447d593 bbcc643515b5d7c1
6cd26baee0e7eff3 6a40c64b34973a75 2567e8f96ba03013 3559b61a8e7591c6
62789c65b3b53e81 04aa7a930b19d5b4 dea2ce8622aecbbb ffffffffffffffff

mod_inverse(-2, p) =
7fffffffffffffff e487ed5110b4611a 62633145c06e0e68 948127044533e63a
0105df531d89cd91 28a5043cc71a026e f7ca8cd9e69d218d 98158536f92f8a1b
a7f09ab6b6a8e122 f242dabb312f3f63 7a262174d31bf6b5 85ffae5b7a035bf6
f71c35fdad44cfd2 d74f9208be258ff3 24943328f6722d9e e1003e5c50b1df82
cc6d241b0e2ae9cd 348b1fd47e9267af c1b2ae91ee51d6cb 0e3179ab1042a95d
cf6a9483b84b4b36 b3861aa7255e4c02 78ba3604650c10be 19482f23171b671d
f1cf3b960c074301 cd93c1d17603d147 dae2aef837a62964 ef15e5fb4aac0b8c
1ccaa4be754ab572 8ae9130c4c7d0288 0ab9472d45556216 d6998b8682283d19
d42a90d5ef8e5d32 767dc2822c6df785 457538abae83063e d9cb87c2d370f263
d5fad7466d8499eb 8f464a702512b0ce e771e9130d697735 f897fd036cc50432
6c3b01399f643532 290f958c0bbd9006 5df08babbd30aeb6 3b84c4605d6ca371
047127d03a72d598 a1edadfe707e8847 25c1689054908400 8d391e0953c3f36b
c438cd085edd2d93 4ce1938c357a711e 0d4a341a5b0a85ed 12c1f4e5156a2674
6ddde16d826f477c 97477e0a0fdf6553 143e2ca3a735e02e ccd94b27d04861d1
119dd0c328adf3f6 8fb094b867716bd7 dc0deebb10b8240e 68034893ead82d54
c9da754c46c7eee0 c37fdbee48536047 a6fa1ae49a0318cc ffffffffffffffff

mod_inverse(-1, p) =
ffffffffffffffff c90fdaa22168c234 c4c6628b80dc1cd1 29024e088a67cc74
020bbea63b139b22 514a08798e3404dd ef9519b3cd3a431b 302b0a6df25f1437
4fe1356d6d51c245 e485b576625e7ec6 f44c42e9a637ed6b 0bff5cb6f406b7ed
ee386bfb5a899fa5 ae9f24117c4b1fe6 49286651ece45b3d c2007cb8a163bf05
98da48361c55d39a 69163fa8fd24cf5f 83655d23dca3ad96 1c62f356208552bb
9ed529077096966d 670c354e4abc9804 f1746c08ca18217c 32905e462e36ce3b
e39e772c180e8603 9b2783a2ec07a28f b5c55df06f4c52c9 de2bcbf695581718
3995497cea956ae5 15d2261898fa0510 15728e5a8aaac42d ad33170d04507a33
a85521abdf1cba64 ecfb850458dbef0a 8aea71575d060c7d b3970f85a6e1e4c7
abf5ae8cdb0933d7 1e8c94e04a25619d cee3d2261ad2ee6b f12ffa06d98a0864
d87602733ec86a64 521f2b18177b200c bbe117577a615d6c 770988c0bad946e2
08e24fa074e5ab31 43db5bfce0fd108e 4b82d120a9210801 1a723c12a787e6d7
88719a10bdba5b26 99c327186af4e23c 1a946834b6150bda 2583e9ca2ad44ce8
dbbbc2db04de8ef9 2e8efc141fbecaa6 287c59474e6bc05d 99b2964fa090c3a2
233ba186515be7ed 1f612970cee2d7af b81bdd762170481c d0069127d5b05aa9
93b4ea988d8fddc1 86ffb7dc90a6c08f 4df435c934063199 fffffffffffffffe

mod_inverse(1, p) = 1

mod_inverse(2, p) =
7fffffffffffffff e487ed5110b4611a 62633145c06e0e68 948127044533e63a
0105df531d89cd91 28a5043cc71a026e f7ca8cd9e69d218d 98158536f92f8a1b
a7f09ab6b6a8e122 f242dabb312f3f63 7a262174d31bf6b5 85ffae5b7a035bf6
f71c35fdad44cfd2 d74f9208be258ff3 24943328f6722d9e e1003e5c50b1df82
cc6d241b0e2ae9cd 348b1fd47e9267af c1b2ae91ee51d6cb 0e3179ab1042a95d
cf6a9483b84b4b36 b3861aa7255e4c02 78ba3604650c10be 19482f23171b671d
f1cf3b960c074301 cd93c1d17603d147 dae2aef837a62964 ef15e5fb4aac0b8c
1ccaa4be754ab572 8ae9130c4c7d0288 0ab9472d45556216 d6998b8682283d19
d42a90d5ef8e5d32 767dc2822c6df785 457538abae83063e d9cb87c2d370f263
d5fad7466d8499eb 8f464a702512b0ce e771e9130d697735 f897fd036cc50432
6c3b01399f643532 290f958c0bbd9006 5df08babbd30aeb6 3b84c4605d6ca371
047127d03a72d598 a1edadfe707e8847 25c1689054908400 8d391e0953c3f36b
c438cd085edd2d93 4ce1938c357a711e 0d4a341a5b0a85ed 12c1f4e5156a2674
6ddde16d826f477c 97477e0a0fdf6553 143e2ca3a735e02e ccd94b27d04861d1
119dd0c328adf3f6 8fb094b867716bd7 dc0deebb10b8240e 68034893ead82d54
c9da754c46c7eee0 c37fdbee48536047 a6fa1ae49a0318cd 0000000000000000

mod_inverse(3, p) =
5555555555555555 430548e0b5cd9611 96eccb83d59eb445 b8561a02d8cd4426
ab593f8cbe5bde60 c5c3582884bc019f 4fdc5de699be165e 6563ae24a61fb167
c54b11cf24709617 4c2c91d220ca2a42 516ec0f88cbd4f23 aeaa743cfc023d4f
4f6823fe73833537 3a350c05d4190aa2 1862ccc5f9a173bf 40aad43d8b213fac
8848c2bcb41c9bde 23076a8da9b6efca 8121c9b69ee139dc b420fbc7602c70e9
34f1b857d0323224 77aebc6f6e3edd56 fb26cead98b2b5d4 10daca1764bcef69
4bdf7d0eb2af8201 33b7d68ba4028b85 3c971f50251970ed f4b943fcdc72b25d
6887187ef8dc78f7 07460cb2dda8ac5a b1d0da1e2e38ec0f 39bbb259ac1ad366
8d71b5e3f5099376 f9a92c56c8494fae 2e4e25c7c9acaed4 91325a81e24b4c42
8ea73a2ef3adbbf2 5f8431a018b72089 efa1460cb39ba4ce a5baa8acf32e02cc
482756266a42ce21 70b50e5d5d290aae e94b07c7d375c9ce d25882eae8f317a0
ada0c5357c4c8e65 c1491ea9a0545ada 192b9b0ae30b02ab 08d0beb0e282a247
d825de05949373b7 8896625d78fc4b69 5e317811920703f3 61d6a343639c19a2
f3e940f3ac4a2fa8 64da5406b53f98e2 0d7ec86d1a23eac9 dde6321a8adaebe0
b66935d77073f7f9 b52063259a4b9d3a 92b3f47cb5d01809 9aacdb0d473ac8e3
313c4e32d9da9f40 82553d49858ceada 6f516743115765de 0000000000000000

mod_inverse(4, p) =
3fffffffffffffff f243f6a8885a308d 313198a2e0370734 4a4093822299f31d
0082efa98ec4e6c8 9452821e638d0137 7be5466cf34e90c6 cc0ac29b7c97c50d
d3f84d5b5b547091 79216d5d98979fb1 bd1310ba698dfb5a c2ffd72dbd01adfb
7b8e1afed6a267e9 6ba7c9045f12c7f9 924a19947b3916cf 70801f2e2858efc1
6636920d871574e6 9a458fea3f4933d7 e0d95748f728eb65 8718bcd5882154ae
e7b54a41dc25a59b 59c30d5392af2601 3c5d1b023286085f 0ca417918b8db38e
f8e79dcb0603a180 e6c9e0e8bb01e8a3 ed71577c1bd314b2 778af2fda55605c6
0e65525f3aa55ab9 45748986263e8144 055ca396a2aab10b 6b4cc5c341141e8c
ea15486af7c72e99 3b3ee1411636fbc2 a2ba9c55d741831f 6ce5c3e169b87931
eafd6ba336c24cf5 c7a3253812895867 73b8f48986b4bb9a fc4bfe81b6628219
361d809ccfb21a99 1487cac605dec803 2ef845d5de98575b 1dc262302eb651b8
823893e81d396acc 50f6d6ff383f4423 92e0b4482a484200 469c8f04a9e1f9b5
e21c66842f6e96c9 a670c9c61abd388f 06a51a0d2d8542f6 8960fa728ab5133a
36eef0b6c137a3be 4ba3bf0507efb2a9 8a1f1651d39af017 666ca593e82430e8
88cee8619456f9fb 47d84a5c33b8b5eb ee06f75d885c1207 3401a449f56c16aa
64ed3aa62363f770 61bfedf72429b023 d37d0d724d018c66 8000000000000000

mod_inverse(5, p) =
6666666666666666 506cbdda73c380e1 e84f5a9e338b3eba 10675269d0f651c8
00d17f75b13b0ada 86ea69ca38e19b8b f96ed714b87db471 46779dc594260816
1ff3aef89220b41b f5024895c0f2991c 61b81ac3dc165ef7 9e662515fb35e32b
f8e35e648a9d730f 12a60e6d64ead98f 50768f53f85b57b2 4d99cb7d0d5b1935
70575015a4ef2170 f6d5b3106541ec8c 9af55874bea7df08 d8279488d9ceede4
a5eedd362d0908f8 8f9e7bb8eab1d668 6094f8038409a6fe 7aa025b5ac15ec17
f4a5c944d66c359b 0adc9b0df8030dd3 158225935fb8211d 8c1184c90889a2d6
7d6eea31f76ef78e d58742703d30ced3 3bc76c24377781ab dee13c6b9b536414
a9bba7118c71e428 5ecb0201bd24c604 3790fa22f2026b65 7b093968a927284f
de6245d1f136e189 3f6b6ec01da88d72 52c1874271212c2b 2d466402bd6a69c1
f02f342e191cf75b 540c77a33c97a66b 7e5a095630f3bef8 2f9d69e6b123b5f4
038db97361f577ad 4e57be6526cba038 eb01207376da0333 a42db1a10fcff5ef
d02d70d37f1757a9 0a4e0fa35dfb8db1 a43b5ce1e26ed18a 7567f71daabb51f6
be4b1abe01f29f96 df6c64d4d97f8442 769823b61f5e4cf2 3d7aa2864039e7da
747e409c208b2992 0c8d43c6b9278979 7cd7f22f4093500b 866906dcbbe02443
d4aec43d056cbf1a 35ffe32506a919d2 ebfb48b6e19c13d7 3333333333333333

mod_inverse(6, p) =
2aaaaaaaaaaaaaaa a182a4705ae6cb08 cb7665c1eacf5a22 dc2b0d016c66a213
55ac9fc65f2def30 62e1ac14425e00cf a7ee2ef34cdf0b2f 32b1d712530fd8b3
e2a588e792384b0b a61648e910651521 28b7607c465ea791 d7553a1e7e011ea7
a7b411ff39c19a9b 9d1a8602ea0c8551 0c316662fcd0b9df a0556a1ec5909fd6
4424615e5a0e4def 1183b546d4db77e5 4090e4db4f709cee 5a107de3b0163874
9a78dc2be8191912 3bd75e37b71f6eab 7d936756cc595aea 086d650bb25e77b4
a5efbe875957c100 99dbeb45d20145c2 9e4b8fa8128cb876 fa5ca1fe6e39592e
b4438c3f7c6e3c7b 83a306596ed4562d 58e86d0f171c7607 9cddd92cd60d69b3
46b8daf1fa84c9bb 7cd4962b6424a7d7 172712e3e4d6576a 48992d40f125a621
47539d1779d6ddf9 2fc218d00c5b9044 f7d0a30659cdd267 52dd545679970166
2413ab1335216710 b85a872eae948557 74a583e3e9bae4e7 692c417574798bd0
56d0629abe264732 e0a48f54d02a2d6d 0c95cd8571858155 84685f5871415123
ec12ef02ca49b9db c44b312ebc7e25b4 af18bc08c90381f9 b0eb51a1b1ce0cd1
79f4a079d62517d4 326d2a035a9fcc71 06bf64368d11f564 eef3190d456d75f0
5b349aebb839fbfc da903192cd25ce9d 4959fa3e5ae80c04 cd566d86a39d6471
989e27196ced4fa0 412a9ea4c2c6756d 37a8b3a188abb2ef 0000000000000000

mod_inverse(7, p) =
9249249249249249 052da18137a9938b de28384fb7593509 ce4a75bbbccd9966
dc98ff3a6ae6a1ca 779804d7bef9275a 3fc2ea1d99d82658 adcf73ac8a7f7944
2da54319f5534a71 14deb0d5ef116d03 f950263c5efb6318 992434fad4961ff5
acb286d8c6057fcc 63c8a6e56b98a483 9784ccc119a70f91 0124d98e13146d27
c50f04b134c35458 3c0cb6a9b5399b12 01f0c78234efd0e8 10388b0ca4de786b
3630a9bb1bc3c3ac 3ae2679a73d97b70 89f9624e2a56ee90 1ce4c8281a6875d9
145a8d3dc49a95b8 eaf20213f496a608 fa27a364d1e27873 5a622b685556e8a0
20e797b5185561a7 7a2ef132a08ede52 55660833bcf3ddd0 f541c407702dfcaf
cde780f47f7e215e 3e4695270e348898 4f6165567e4c996c 669f769583eecbdf
cffa1a99a1bc1d9f 7f2bc2c94ef0ca11 08822ef133e63f19 1c1b6a4d0e9804cb
e96801666d04cf14 c13661c49fb41250 6b5c0d568f1310d0 440572b7463303ee
e08152128bf0f41c 26c67db512d9c051 4fb8778060a52925 33aefdc1844da87b
29657c9bda2158a8 57dd3ae961b08146 ea9df2674379bda1 3a023c7386302bf2
c6b46f5895117645 3f2d2254a46d0615 cdfde9df9a86b710 ea1ce82d8052b8ee
ef8fca039c348487 7fa53c4076387b3f d6eb59fa5c402935 092852f230f70f3c
5467617bbe9b5a25 71b6b234e4f1929b 07f9434e66def7c5 b6db6db6db6db6db

mod_inverse(8, p) =
1fffffffffffffff f921fb54442d1846 9898cc51701b839a 252049c1114cf98e
804177d4c7627364 4a29410f31c6809b bdf2a33679a74863 6605614dbe4be286
e9fc26adadaa3848 bc90b6aecc4bcfd8 de89885d34c6fdad 617feb96de80d6fd
bdc70d7f6b5133f4 b5d3e4822f8963fc c9250cca3d9c8b67 b8400f97142c77e0
b31b4906c38aba73 4d22c7f51fa499eb f06caba47b9475b2 c38c5e6ac410aa57
73daa520ee12d2cd ace186a9c9579300 9e2e8d811943042f 86520bc8c5c6d9c7
7c73cee58301d0c0 7364f0745d80f451 f6b8abbe0de98a59 3bc5797ed2ab02e3
0732a92f9d52ad5c a2ba44c3131f40a2 02ae51cb51555885 b5a662e1a08a0f46
750aa4357be3974c 9d9f70a08b1b7de1 515d4e2aeba0c18f b672e1f0b4dc3c98
f57eb5d19b61267a e3d1929c0944ac33 b9dc7a44c35a5dcd 7e25ff40db31410c
9b0ec04e67d90d4c 8a43e56302ef6401 977c22eaef4c2bad 8ee13118175b28dc
411c49f40e9cb566 287b6b7f9c1fa211 c9705a2415242100 234e478254f0fcda
f10e334217b74b64 d33864e30d5e9c47 83528d0696c2a17b 44b07d39455a899d
1b77785b609bd1df 25d1df8283f7d954 c50f8b28e9cd780b b33652c9f4121874
44677430ca2b7cfd a3ec252e19dc5af5 f7037baec42e0903 9a00d224fab60b55
32769d5311b1fbb8 30dff6fb9214d811 e9be86b92680c633 4000000000000000

mod_inverse(9, p) =
c71c71c71c71c71c 470c54b6fd8a5e29 0ad330339d1cf9f8 03739206a4899f04
e525944866d65c37 22c7cdb3e061591e 6502306f66bb8986 ec9341002e49f347
77047ee35506b38b b1bd543fa1d7b7f0 1357c243f30f0dfd ece30f38f6afe463
b94853fc62dcd180 dd267162eee518cf 8e3bddcdf1236368 ec39448f99f83f3d
3dff1bb84eed6bb0 fc66a34a8c002f83 2d4ed6aa1d62dc58 4ef7a0d135bd0775
7b8958cce5ca74ff c1ed0d04013d59ca f4afe23fb9a0fd99 7ca92ce1406383f5
b10979224b9984ad 78acf49b295b458c 380b49105690b22b 3b059ea357b64ad9
f3e5e3d2ef57c4eb 10f8c84c05343cd3 9ee752466bda26ce 3160a0269193ed44
9f5ea8693bc102c0 468abcca7e006496 6c0bad7cd692ed45 52cad32f10050745
f786326d8deab68a dedf1e758f00a141 d9cda372f86b2b37 82b389938cc0b131
fdb11e59a29be0f8 b1a676d9d95fc398 2059bcd242bd818d 4023dc241f8c8c76
ea77217cccb2a198 1855478bcb6f7ea7 901069c411c45b8f 1491bcf210862552
4dadb0b7b002b8ac 3eb43ada1a4caff5 dbc8c2d3aa105e8d 399f7cf29316e67c
3920423892026f33 95fd6eba519464ba 1f7d28fe9253ce81 b06e74e899542661
a9a0284c0663ed46 a6a0e757bd5b1988 aba3e522fd903816 68e8a9c9a633d4bc
c837612151a8c8eb dac6e456379e23fd ae689b9c7dcbedb0 aaaaaaaaaaaaaaaa

mod_inverse(10, p) =
b333333333333333 0cbe4c3e4a96218b 568ade94da33adc5 9cb4d0392daf0f1e
016e9f0df62752fe 6c1a3921e38ad034 f481f86442dbfbc6 3b515419c3428e26
b7ea7232ffb93b30 ecc3ff0611a88bf1 ab022ed6c1272631 5532c0e6779e4d8c
f38de52ff293895a 60a2993f709afcba cccf7ad2f29fd978 07cd241ad75f6c1d
8498cc25e0a27a85 aff5f95cb1335df6 0f2d5acc4da5c64f 7a4543ef7d2a2050
2262031ececfcfb2 fb5558839ab73736 a904b2062710e43d 569841fded265d29
ec222038773d5dcf 53020f5872055831 65a3c1c1e78239f3 b51ea85fcef0dcf7
5b8219d771023139 f5acb4446b1569f1 a89cfd3f611122ec c60a29bc4fd1ef24
2908645eb5c74f46 a5e343830b005a87 613db5bd27843bf1 975024772804868b
c52bfa2f66200ab0 2efc01d033e6f788 10d2acb445fa0d4b 8f3b2f04cb7a3913
64529b50abf2b0df d315d15daa09633c 1d1d9056d5aa8e32 53537953b5fe7e6b
06380489eb6d916f 49198d3103e45863 9b41f8ca0ffd859a 5f4ff6d9dbabee63
ac4f85721e68d967 d2089b5de47837f6 df67e28b4c41eeb2 4d75f073eac7cf6f
cd036ecc83689748 06fdb0747c9f2774 4f8a3e7eb6e506a7 eb969c6af06555be
4bdcf11138f388bf 95f7369bc4053094 9a79e7d2b101cc14 2b37cc0248c83f76
b431d76ac97e4e6d de7fcd80cba7ed31 1cf7bf400ad122b8 9999999999999999


 TOC 

11.  Acknowledgements

Thanks to Wan-Teh Chang, Adam Langley, Ian Goldberg and Daniel Bleichanbacher for feedback on earlier versions. TODO(benl): Update this list.



 TOC 

12.  IANA Considerations

This memo includes no request to IANA.



 TOC 

13.  Security Considerations

When storing at multiple servers using Shamir split, the servers might guess they're part of a split because the value will be longer than a non-split value.

The role of the user's password is critical and must therefore be strongly protected. Obvious risks to the password are phishing and malware.

If Nigori can achieve its aim of providing storage for all a user's credentials, it is hoped that users can be protected from phishing, since they should only ever have to use a single password in a single context.

Although Nigori only specifies password-based security for the stored secrets, this is anticipated to be the base level of security. Some users and stores may choose to layer other mechanisms on top of, or instead of, passwords, such as one-time passwords or keying material on a hardware devices and so forth.

Protection against malware is beyond Nigori's scope, but it is worth noting that a user with malware on his machine is already completely exposed anyway.



 TOC 

14.  References



 TOC 

14.1. Normative References

[RFC2104] Krawczyk, H., Bellare, M., and R. Canetti, “HMAC: Keyed-Hashing for Message Authentication,” RFC 2104, February 1997 (TXT).
[RFC2119] Bradner, S., “Key words for use in RFCs to Indicate Requirement Levels,” BCP 14, RFC 2119, March 1997 (TXT, HTML, XML).
[RFC2898] Kaliski, B., “PKCS #5: Password-Based Cryptography Specification Version 2.0,” RFC 2898, September 2000 (TXT).
[RFC3174] Eastlake, D. and P. Jones, “US Secure Hash Algorithm 1 (SHA1),” RFC 3174, September 2001 (TXT).
[RFC4627] Crockford, D., “The application/json Media Type for JavaScript Object Notation (JSON),” RFC 4627, July 2006 (TXT).
[RFC4648] Josefsson, S., “The Base16, Base32, and Base64 Data Encodings,” RFC 4648, October 2006 (TXT).
[aes] National Institute of Standards and Technology, U.S. Department of Commerce, “Advanced Encryption Standard,” November 2001.
[protobuf] Google, “Protocol Buffers,” April 2011.
[FIPS186-3] National Institute of Standards and Technology, “Federal Information Processing Standards Publication (FIPS PUB), Digital Signature Standard (DSS),” June 2009.


 TOC 

14.2. Informative References

[SP800-57] National Institute of Standards and Technology, “SP 800-57 Recommendation for Key Management – Part 1: General,” March 2007.


 TOC 

Editorial Comments

anchor15: Ian Goldberg points out that 0 has to be allowed or a small amount of data is leaked: e.g. if k=2 and some share is s, then the secret cannot be s (proof left as an exercise for the reader)
anchor16: [Daniel Bleichenbacher points out: to compute expressions of the form a*b^{-1} mod p, where b is a small integer. An efficient method to do this is to compute k = -a*p^{-1} mod b. Then the integer a + kp is divisible by b and hence a*b^{-1} == (a+kp)/b (mod p). I.e. this method takes O(log(p)log(b)), rather than O(log(p)^2) for the current method. (I have my doubts because of the cache, but I should test it) ]


 TOC 

Authors' Addresses

  Ben Laurie
  Google Ltd.
  London,
  UK
Email:  benl@google.com
  
  Daniel Thomas
  University of Cambridge
  15 JJ Thomson Avenue
  Cambridge, CB3 0FD
  UK
Email:  Daniel.Thomas@cl.cam.ac.uk
  
  Alastair Beresford
  University of Cambridge
  15 JJ Thomson Avenue
  Cambridge, CB3 0FD
  UK
Email:  Alastair.Beresford@cl.cam.ac.uk