1 2# Pure-Python SPAKE2 3 4* License: MIT 5* Dependencies: hkdf 6* Compatible With: Python 2.7, 3.3, 3.4, 3.5, 3.6, PyPy2 7* [![Build Status](https://travis-ci.org/warner/python-spake2.png?branch=master)](https://travis-ci.org/warner/python-spake2) [![Coverage Status](https://coveralls.io/repos/warner/python-spake2/badge.svg)](https://coveralls.io/r/warner/python-spake2) 8 9This library implements the SPAKE2 password-authenticated key exchange 10("PAKE") algorithm. This allows two parties, who share a weak password, to 11safely derive a strong shared secret (and therefore build an 12encrypted+authenticated channel). 13 14A passive attacker who eavesdrops on the connection learns no information 15about the password or the generated secret. An active attacker 16(man-in-the-middle) gets exactly one guess at the password, and unless they 17get it right, they learn no information about the password or the generated 18secret. Each execution of the protocol enables one guess. The use of a weak 19password is made safer by the rate-limiting of guesses: no off-line 20dictionary attack is available to the network-level attacker, and the 21protocol does not depend upon having previously-established confidentiality 22of the network (unlike e.g. sending a plaintext password over TLS). 23 24The protocol requires the exchange of one pair of messages, so only one round 25trip is necessary to establish the session key. If key-confirmation is 26necessary, that will require a second round trip. 27 28All messages are bytestrings. For the default security level (using the 29Ed25519 elliptic curve, roughly equivalent to an 128-bit symmetric key), the 30message is 33 bytes long. 31 32## What Is It Good For? 33 34PAKE can be used in a pairing protocol, like the initial version of Firefox 35Sync (the one with J-PAKE), to introduce one device to another and help them 36share secrets. In this mode, one device creates a random code, the user 37copies that code to the second device, then both devices use the code as a 38one-time password and run the PAKE protocol. Once both devices have a shared 39strong key, they can exchange other secrets safely. 40 41PAKE can also be used (carefully) in a login protocol, where SRP is perhaps 42the best-known approach. Traditional non-PAKE login consists of sending a 43plaintext password through a TLS-encrypted channel, to a server which then 44checks it (by hashing/stretching and comparing against a stored verifier). In 45a PAKE login, both sides put the password into their PAKE protocol, and then 46confirm that their generated key is the same. This nominally does not require 47the initial TLS-protected channel. However note that it requires other, 48deeper design considerations (the PAKE protocol must be bound to whatever 49protected channel you end up using, else the attacker can wait for PAKE to 50complete normally and then steal the channel), and is not simply a drop-in 51replacement. In addition, the server cannot hash/stretch the password very 52much (see the note on "Augmented PAKE" below), so unless the client is 53willing to perform key-stretching before running PAKE, the server's stored 54verifier will be vulnerable to a low-cost dictionary attack. 55 56## Usage 57 58Alice and Bob both initialize their SPAKE2 instances with the same (weak) 59password. They will exchange messages to (hopefully) derive a shared secret 60key. The protocol is symmetric: for each operation that Alice does, Bob will 61do the same. 62 63However, there are two roles in the SPAKE2 protocol, "A" and "B". The two 64sides must agree ahead of time which one will play which role (the messages 65they generate depend upon which side they play). There are two separate 66classes, `SPAKE2_A` and `SPAKE2_B`, and a complete interaction will use one 67of each (one `SPAKE2_A` on one computer, and one `SPAKE2_B` on the other 68computer). 69 70Each instance of a SPAKE2 protocol uses a set of shared parameters. These 71include a group, a generator, and a pair of arbitrary group elements. This 72library comes with several pre-generated parameter sets, with various 73security levels. 74 75You start by creating an instance (either `SPAKE2_A` or `SPAKE2_B`) with the 76password. Then you ask the instance for the outbound message by calling 77`msg_out=s.start()`, and send it to your partner. Once you receive the 78corresponding inbound message, you pass it into the instance and extract the 79(shared) key bytestring with `key=s.finish(msg_in)`. For example, the 80client-side might do: 81 82```python 83from spake2 import SPAKE2_A 84s = SPAKE2_A(b"our password") 85msg_out = s.start() 86send(msg_out) # this is message A->B 87msg_in = receive() 88key = s.finish(msg_in) 89``` 90 91while the server-side might do: 92 93```python 94from spake2 import SPAKE2_B 95q = SPAKE2_B(b"our password") 96msg_out = q.start() 97send(msg_out) 98msg_in = receive() # this is message A->B 99key = q.finish(msg_in) 100``` 101 102If both sides used the same password, and there is no man-in-the-middle, then 103both sides will obtain the same `key`. If not, the two sides will get 104different keys, so using "key" for data encryption will result in garbled 105data. 106 107The shared "key" can be used as an HMAC key to provide data integrity on 108subsequent messages, or as an authenticated-encryption key (e.g. 109nacl.secretbox). It can also be fed into [HKDF] [1] to derive other session 110keys as necessary. 111 112The `SPAKE2` instances, and the messages they create, are single-use. Create 113a new one for each new session. 114 115### Key Confirmation 116 117To safely test for identical keys before use, you can perform a second 118message exchange at the end of the protocol, before actually using the key 119(be careful to not simply send the shared key over the wire: this would allow 120a MitM to learn the key that they could otherwise not guess). 121 122Alice does this: 123 124```python 125... 126key = s.finish(msg_in) 127confirm_A = HKDF(key, info="confirm_A", length=32) 128expected_confirm_B = HKDF(key, info="confirm_B", length=32) 129send(confirm_A) 130confirm_B = receive() 131assert confirm_B == expected_confirm_B 132``` 133 134And Bob does this: 135```python 136... 137key = q.finish(msg_in) 138expected_confirm_A = HKDF(key, info="confirm_A", length=32) 139confirm_B = HKDF(key, info="confirm_B", length=32) 140send(confirm_B) 141confirm_A = receive() 142assert confirm_A == expected_confirm_A 143``` 144 145## Symmetric Usage 146 147A single SPAKE2 instance must be used asymmetrically: the two sides must 148somehow decide (ahead of time) which role they will each play. The 149implementation includes the side identifier in the exchanged message to guard 150against an `SPAKE2_A` talking to another `SPAKE2_A`. Typically a "client" 151will take on the `A` role, and the "server" will be `B`. 152 153This is a nuisance for more egalitarian protocols, where there's no clear way 154to assign these roles ahead of time. In this case, use `SPAKE2_Symmetric` on 155both sides. This uses a different set of parameters (so it is not 156interoperable with `SPAKE2_A` or `SPAKE2_B`, but should otherwise behave the 157same way. 158 159Carol does: 160 161```python 162s1 = SPAKE2_Symmetric(pw) 163outmsg1 = s1.start() 164send(outmsg1) 165``` 166 167Dave does the same: 168```python 169s2 = SPAKE2_Symmetric(pw) 170outmsg2 = s2.start() 171send(outmsg2) 172``` 173 174Carol then processes Dave's incoming message: 175```python 176inmsg2 = receive() # this is outmsg1 177key = s1.finish(inmsg2) 178``` 179 180And Dave does the same: 181```python 182inmsg1 = receive() # this is outmsg2 183key = s2.finish(inmsg1) 184``` 185 186## Identifier Strings 187 188The SPAKE2 protocol includes a pair of "identity strings" `idA` and `idB` 189that are included in the final key-derivation hash. This binds the key to a 190single pair of parties, or for some specific purpose. 191 192For example, when user "alice" logs into "example.com", both sides should set 193`idA = b"alice"` and `idB = b"example.com"`. This prevents an attacker from 194substituting messages from unrelated login sessions (other users on the same 195server, or other servers for the same user). 196 197This also makes sure the session is established with the correct service. If 198Alice has one password for "example.com" but uses it for both login and 199file-transfer services, `idB` should be different for the two services. 200Otherwise if Alice is simultaneously connecting to both services, and 201attacker could rearrange the messages and cause her login client to connect 202to the file-transfer server, and vice versa. 203 204If provided, `idA` and `idB` must be bytestrings. They default to an empty 205string. 206 207`SPAKE2_Symmetric` uses a single `idSymmetric=` string, instead of `idA` and 208`idB`. Both sides must provide the same `idSymmetric=`, or leave it empty. 209 210## Serialization 211 212Sometimes, you can't hold the SPAKE2 instance in memory for the whole 213negotiation: perhaps all your program state is stored in a database, and 214nothing lives in RAM for more than a few moments. You can persist the data 215from a SPAKE2 instance with `data = p.serialize()`, after the call to 216`start`. Then later, when the inbound message is received, you can 217reconstruct the instance with `p = SPAKE2_A.from_serialized(data)` before 218calling `p.finish(msg)`. 219 220```python 221def first(): 222 p = SPAKE2_A(password) 223 send(p.start()) 224 open('saved','w').write(p.serialize()) 225 226def second(inbound_message): 227 p = SPAKE2_A.from_serialized(open('saved').read()) 228 key = p.finish(inbound_message) 229 return key 230``` 231 232The instance data is highly sensitive and includes the password: protect it 233carefully. An eavesdropper who learns the instance state from just one side 234will be able to reconstruct the shared key. `data` is a printable ASCII 235bytestring (the JSON-encoding of a small dictionary). For `ParamsEd25519`, 236the serialized data requires 221 bytes. 237 238Note that you must restore the instance with the same side (`SPAKE2_A` vs 239`SPAKE2_B`) and `params=` (if overridden) as you used when first creating it. 240Otherwise `from_serialized()` will throw an exception. If you use non-default 241parameters, you might want to store an indicator along with the serialized 242state. 243 244Also remember that you must never re-use a SPAKE2 instance for multiple key 245agreements: that would reveal the key and/or password. Never use 246`.from_serialized()` more than once on the same saved state, and delete the 247state as soon as the incoming message is processed. SPAKE2 has internal 248checks to throw exceptions when instances are used multiple times, but the 249serialize/restore process can bypass those checks, so use with care. 250 251Database-backed applications should store the outbound message (`p.start()`) 252in the DB next to the serialized SPAKE2 state, so they can re-send the same 253message if the application crashes before it has been successfully delivered. 254`p.start()` cannot be called on the instance that `.from_serialized()` 255produces. 256 257## Security 258 259SPAKE2's strength against cryptographic attacks depends upon the parameters 260you use, which also influence the execution speed. Use the strongest 261parameters your time budget can afford. 262 263The library defaults to the fast and secure Ed25519 elliptic-curve group 264through the `ParamsEd25519` parameter set. This offers a 128-bit security 265level, small messages, and fairly fast execution speed. 266 267If for some reason you don't care for elliptic curves, the `spake2.params` 268module includes three integer-group parameter sets: `Params1024`, 269`Params2048`, `Params3072`, offering 80-bit, 112-bit, and 128-bit security 270levels respectively. 271 272To override the default parameters, include a `params=` value when you create 273the SPAKE2 instance. Both sides must use the same parameters. 274 275```python 276from spake2 import SPAKE2_A 277from spake2.parameters.i3072 import Params3072 278s = SPAKE2_A(b"password", params=Params3072) 279``` 280 281Note that if you serialize an instance with non-default `params=`, you must 282restore it with the same parameters, otherwise you will get an exception: 283 284```python 285s = SPAKE2_A.from_serialized(data, params=Params3072) 286``` 287 288This library is very much *not* constant-time, and does not protect against 289timing attacks. Do not allow attackers to measure how long it takes you to 290create or respond to a message. 291 292This library depends upon a strong source of random numbers. Do not use it on 293a system where os.urandom() is weak. 294 295## Speed 296 297To run the built-in speed tests, just run `python setup.py speed`. 298 299SPAKE2 consists of two phases, separated by a single message exchange. The 300time these phases take is split roughly 40/60. On my 2012 Mac Mini (2.6GHz 301Core-i7), the default `ParamsEd25519` security level takes about 14ms to 302complete both phases. For the integer groups, larger groups are slower and 303require larger messages (and their serialized state is larger), but are more 304secure. The complete output of `python setup.py speed` is: 305 306 ParamsEd25519: msglen= 33, statelen=221, full=13.9ms, start= 5.5ms 307 Params1024 : msglen=129, statelen=197, full= 4.3ms, start= 1.8ms 308 Params2048 : msglen=257, statelen=213, full=20.8ms, start= 8.5ms 309 Params3072 : msglen=385, statelen=221, full=41.5ms, start=16.5ms 310 311A slower CPU (1.8GHz Intel Atom) takes about 8x as long (76/32/157/322ms). 312 313This library uses only Python. A version which used C speedups for the large 314modular multiplication operations would probably be an order of magnitude 315faster. 316 317## Testing 318 319To run the built-in test suite from a source directory, for all supported 320python versions, do: 321 322 tox 323 324On my computer, the tests take approximately two seconds (per version). 325 326## History 327 328The protocol was described as "PAKE2" in ["cryptobook"] [2] from Dan Boneh 329and Victor Shoup. This is a form of "SPAKE2", defined by Abdalla and 330Pointcheval at [RSA 2005] [3]. Additional recommendations for groups and 331distinguished elements were published in [Ladd's IETF draft] [4]. 332 333The Ed25519 implementation uses code adapted from Daniel Bernstein (djb), 334Matthew Dempsky, Daniel Holth, Ron Garret, with further optimizations by 335Brian Warner[5]. The "arbitrary element" computation, which must be the same 336for both participants, is from python-pure25519 version 0.5. 337 338The Boneh/Shoup chapter that defines PAKE2 also defines an augmented variant 339named "PAKE2+", which changes one side (typically a server) to record a 340derivative of the password instead of the actual password. In PAKE2+, a 341server compromise does not immediately give access to the passwords: instead, 342the attacker must perform an offline dictionary attack against the stolen 343data before they can learn the passwords. PAKE2+ support is planned, but not 344yet implemented. 345 346The security of the symmetric case was proved by Kobara/Imai[6] in 2003, and 347uses different (slightly weaker?) reductions than that of the asymmetric 348form. See also Mike Hamburg's analysis[7] from 2015. 349 350Brian Warner first wrote this Python version in July 2010. 351 352#### footnotes 353 354[1]: https://tools.ietf.org/html/rfc5869 "HKDF" 355[2]: http://crypto.stanford.edu/~dabo/cryptobook/ "cryptobook" 356[3]: http://www.di.ens.fr/~pointche/Documents/Papers/2005_rsa.pdf "RSA 2005" 357[4]: https://tools.ietf.org/html/draft-ladd-spake2-01 "Ladd's IETF draft" 358[5]: https://github.com/warner/python-pure25519 359[6]: http://eprint.iacr.org/2003/038.pdf "Pretty-Simple Password-Authenticated Key-Exchange Under Standard Assumptions" 360[7]: https://moderncrypto.org/mail-archive/curves/2015/000419.html "PAKE questions" 361