Repository files navigation

• License: MIT
• Dependencies: "cryptography" (for hkdf)
• Compatible With: Python 3.9, 3.10, 3.11, 3.12, PyPy3
• 

This library implements the SPAKE2 password-authenticated key exchange("PAKE") algorithm. This allows two parties, who share a weak password, tosafely derive a strong shared secret (and therefore build anencrypted+authenticated channel).

A passive attacker who eavesdrops on the connection learns no informationabout the password or the generated secret. An active attacker(man-in-the-middle) gets exactly one guess at the password, and unless theyget it right, they learn no information about the password or the generatedsecret. Each execution of the protocol enables one guess. The use of a weakpassword is made safer by the rate-limiting of guesses: no off-linedictionary attack is available to the network-level attacker, and theprotocol does not depend upon having previously-established confidentialityof the network (unlike e.g. sending a plaintext password over TLS).

The protocol requires the exchange of one pair of messages, so only one roundtrip is necessary to establish the session key. If key-confirmation isnecessary, that will require a second round trip.

All messages are bytestrings. For the default security level (using theEd25519 elliptic curve, roughly equivalent to an 128-bit symmetric key), themessage is 33 bytes long.

PAKE can be used in a pairing protocol, like the initial version of FirefoxSync (the one with J-PAKE), to introduce one device to another and help themshare secrets. In this mode, one device creates a random code, the usercopies that code to the second device, then both devices use the code as aone-time password and run the PAKE protocol. Once both devices have a sharedstrong key, they can exchange other secrets safely.

PAKE can also be used (carefully) in a login protocol, where SRP is perhapsthe best-known approach. Traditional non-PAKE login consists of sending aplaintext password through a TLS-encrypted channel, to a server which thenchecks it (by hashing/stretching and comparing against a stored verifier). Ina PAKE login, both sides put the password into their PAKE protocol, and thenconfirm that their generated key is the same. This nominally does not requirethe initial TLS-protected channel. However note that it requires other,deeper design considerations (the PAKE protocol must be bound to whateverprotected channel you end up using, else the attacker can wait for PAKE tocomplete normally and then steal the channel), and is not simply a drop-inreplacement. In addition, the server cannot hash/stretch the password verymuch (see the note on "Augmented PAKE" below), so unless the client iswilling to perform key-stretching before running PAKE, the server's storedverifier will be vulnerable to a low-cost dictionary attack.

Alice and Bob both initialize their SPAKE2 instances with the same (weak)password. They will exchange messages to (hopefully) derive a shared secretkey. The protocol is symmetric: for each operation that Alice does, Bob willdo the same.

However, there are two roles in the SPAKE2 protocol, "A" and "B". The twosides must agree ahead of time which one will play which role (the messagesthey generate depend upon which side they play). There are two separateclasses,SPAKE2_A andSPAKE2_B, and a complete interaction will use oneof each (oneSPAKE2_A on one computer, and oneSPAKE2_B on the othercomputer).

Each instance of a SPAKE2 protocol uses a set of shared parameters. Theseinclude a group, a generator, and a pair of arbitrary group elements. Thislibrary comes with several pre-generated parameter sets, with varioussecurity levels.

You start by creating an instance (eitherSPAKE2_A orSPAKE2_B) with thepassword. Then you ask the instance for the outbound message by callingmsg_out=s.start(), and send it to your partner. Once you receive thecorresponding inbound message, you pass it into the instance and extract the(shared) key bytestring withkey=s.finish(msg_in). For example, theclient-side might do:

fromspake2importSPAKE2_As=SPAKE2_A(b"our password")msg_out=s.start()send(msg_out)# this is message A->Bmsg_in=receive()key=s.finish(msg_in)

while the server-side might do:

fromspake2importSPAKE2_Bq=SPAKE2_B(b"our password")msg_out=q.start()send(msg_out)msg_in=receive()# this is message A->Bkey=q.finish(msg_in)

If both sides used the same password, and there is no man-in-the-middle, thenboth sides will obtain the samekey. If not, the two sides will getdifferent keys, so using "key" for data encryption will result in garbleddata.

The shared "key" can be used as an HMAC key to provide data integrity onsubsequent messages, or as an authenticated-encryption key (e.g.nacl.secretbox). It can also be fed into [HKDF]1 to derive other sessionkeys as necessary.

TheSPAKE2 instances, and the messages they create, are single-use. Createa new one for each new session.

To safely test for identical keys before use, you can perform a secondmessage exchange at the end of the protocol, before actually using the key(be careful to not simply send the shared key over the wire: this would allowa MitM to learn the key that they could otherwise not guess).

Alice does this:

...key=s.finish(msg_in)confirm_A=HKDF(key,info="confirm_A",length=32)expected_confirm_B=HKDF(key,info="confirm_B",length=32)send(confirm_A)confirm_B=receive()assertconfirm_B==expected_confirm_B

And Bob does this:

...key=q.finish(msg_in)expected_confirm_A=HKDF(key,info="confirm_A",length=32)confirm_B=HKDF(key,info="confirm_B",length=32)send(confirm_B)confirm_A=receive()assertconfirm_A==expected_confirm_A

A single SPAKE2 instance must be used asymmetrically: the two sides mustsomehow decide (ahead of time) which role they will each play. Theimplementation includes the side identifier in the exchanged message to guardagainst anSPAKE2_A talking to anotherSPAKE2_A. Typically a "client"will take on theA role, and the "server" will beB.

This is a nuisance for more egalitarian protocols, where there's no clear wayto assign these roles ahead of time. In this case, useSPAKE2_Symmetric onboth sides. This uses a different set of parameters (so it is notinteroperable withSPAKE2_A orSPAKE2_B, but should otherwise behave thesame way.

Carol does:

s1=SPAKE2_Symmetric(pw)outmsg1=s1.start()send(outmsg1)

Dave does the same:

s2=SPAKE2_Symmetric(pw)outmsg2=s2.start()send(outmsg2)

Carol then processes Dave's incoming message:

inmsg2=receive()# this is outmsg1key=s1.finish(inmsg2)

And Dave does the same:

inmsg1=receive()# this is outmsg2key=s2.finish(inmsg1)

The SPAKE2 protocol includes a pair of "identity strings"idA andidBthat are included in the final key-derivation hash. This binds the key to asingle pair of parties, or for some specific purpose.

For example, when user "alice" logs into "example.com", both sides should setidA = b"alice" andidB = b"example.com". This prevents an attacker fromsubstituting messages from unrelated login sessions (other users on the sameserver, or other servers for the same user).

This also makes sure the session is established with the correct service. IfAlice has one password for "example.com" but uses it for both login andfile-transfer services,idB should be different for the two services.Otherwise if Alice is simultaneously connecting to both services, andattacker could rearrange the messages and cause her login client to connectto the file-transfer server, and vice versa.

If provided,idA andidB must be bytestrings. They default to an emptystring.

SPAKE2_Symmetric uses a singleidSymmetric= string, instead ofidA andidB. Both sides must provide the sameidSymmetric=, or leave it empty.

Sometimes, you can't hold the SPAKE2 instance in memory for the wholenegotiation: perhaps all your program state is stored in a database, andnothing lives in RAM for more than a few moments. You can persist the datafrom a SPAKE2 instance withdata = p.serialize(), after the call tostart. Then later, when the inbound message is received, you canreconstruct the instance withp = SPAKE2_A.from_serialized(data) beforecallingp.finish(msg).

deffirst():p=SPAKE2_A(password)send(p.start())open('saved','w').write(p.serialize())defsecond(inbound_message):p=SPAKE2_A.from_serialized(open('saved').read())key=p.finish(inbound_message)returnkey

The instance data is highly sensitive and includes the password: protect itcarefully. An eavesdropper who learns the instance state from just one sidewill be able to reconstruct the shared key.data is a printable ASCIIbytestring (the JSON-encoding of a small dictionary). ForParamsEd25519,the serialized data requires 221 bytes.

Note that you must restore the instance with the same side (SPAKE2_A vsSPAKE2_B) andparams= (if overridden) as you used when first creating it.Otherwisefrom_serialized() will throw an exception. If you use non-defaultparameters, you might want to store an indicator along with the serializedstate.

Also remember that you must never re-use a SPAKE2 instance for multiple keyagreements: that would reveal the key and/or password. Never use.from_serialized() more than once on the same saved state, and delete thestate as soon as the incoming message is processed. SPAKE2 has internalchecks to throw exceptions when instances are used multiple times, but theserialize/restore process can bypass those checks, so use with care.

Database-backed applications should store the outbound message (p.start())in the DB next to the serialized SPAKE2 state, so they can re-send the samemessage if the application crashes before it has been successfully delivered.p.start() cannot be called on the instance that.from_serialized()produces.

SPAKE2's strength against cryptographic attacks depends upon the parametersyou use, which also influence the execution speed. Use the strongestparameters your time budget can afford.

The library defaults to the fast and secure Ed25519 elliptic-curve groupthrough theParamsEd25519 parameter set. This offers a 128-bit securitylevel, small messages, and fairly fast execution speed.

If for some reason you don't care for elliptic curves, thespake2.paramsmodule includes three integer-group parameter sets:Params1024,Params2048,Params3072, offering 80-bit, 112-bit, and 128-bit securitylevels respectively.

To override the default parameters, include aparams= value when you createthe SPAKE2 instance. Both sides must use the same parameters.

fromspake2importSPAKE2_Afromspake2.parameters.i3072importParams3072s=SPAKE2_A(b"password",params=Params3072)

Note that if you serialize an instance with non-defaultparams=, you mustrestore it with the same parameters, otherwise you will get an exception:

s=SPAKE2_A.from_serialized(data,params=Params3072)

This library is very muchnot constant-time, and does not protect againsttiming attacks. Do not allow attackers to measure how long it takes you tocreate or respond to a message.

This library depends upon a strong source of random numbers. Do not use it ona system where os.urandom() is weak.

To run the built-in speed tests, just runpython setup.py speed.

SPAKE2 consists of two phases, separated by a single message exchange. Thetime these phases take is split roughly 40/60. On my 2012 Mac Mini (2.6GHzCore-i7), the defaultParamsEd25519 security level takes about 14ms tocomplete both phases. For the integer groups, larger groups are slower andrequire larger messages (and their serialized state is larger), but are moresecure. The complete output ofpython setup.py speed is:

ParamsEd25519: msglen= 33, statelen=221, full=13.9ms, start= 5.5msParams1024   : msglen=129, statelen=197, full= 4.3ms, start= 1.8msParams2048   : msglen=257, statelen=213, full=20.8ms, start= 8.5msParams3072   : msglen=385, statelen=221, full=41.5ms, start=16.5ms

A slower CPU (1.8GHz Intel Atom) takes about 8x as long (76/32/157/322ms).

This library uses only Python. A version which used C speedups for the largemodular multiplication operations would probably be an order of magnitudefaster.

To run the built-in test suite from a source directory, for all supportedpython versions, do:

tox

On my computer, the tests take approximately two seconds (per version).

The protocol was described as "PAKE2" in ["cryptobook"]2 from Dan Bonehand Victor Shoup. This is a form of "SPAKE2", defined by Abdalla andPointcheval at [RSA 2005]3. Additional recommendations for groups anddistinguished elements were published in [Ladd's IETF draft]4.

The Ed25519 implementation uses code adapted from Daniel Bernstein (djb),Matthew Dempsky, Daniel Holth, Ron Garret, with further optimizations byBrian Warner5. The "arbitrary element" computation, which must be the samefor both participants, is from python-pure25519 version 0.5.

The Boneh/Shoup chapter that defines PAKE2 also defines an augmented variantnamed "PAKE2+", which changes one side (typically a server) to record aderivative of the password instead of the actual password. In PAKE2+, aserver compromise does not immediately give access to the passwords: instead,the attacker must perform an offline dictionary attack against the stolendata before they can learn the passwords. PAKE2+ support is planned, but notyet implemented.

The security of the symmetric case was proved by Kobara/Imai6 in 2003, anduses different (slightly weaker?) reductions than that of the asymmetricform. See also Mike Hamburg's analysis7 from 2015.

Brian Warner first wrote this Python version in July 2010.