Encode public keys with Elligator before sending over the wire

This should prevent detection of successful password guess try.
Thanks to Watson Ladd for the suggestion!

Signed-off-by: Sergey Matveev <stargrave@stargrave.org>

diff --git a/doc/developer.texi b/doc/developer.texi
index 3fd23ed817fae43d18409af8c9862dc351163aad..be57f2c8a3f117d87b6988c8154b2a1324281804 100644 (file)
--- a/doc/developer.texi
+++ b/doc/developer.texi
@@ -11,6 +11,8 @@
 @item Password authenticated key agreement
 DH-A-EKE powered by @url{http://cr.yp.to/ecdh.html, Curve25519}
 and @url{http://ed25519.cr.yp.to/, Ed25519}
+@item DH elliptic-curve point encoding for public keys
+@url{http://elligator.cr.yp.to/, Elligator}
 @item Key derivation function for verifier generation
 @url{https://en.wikipedia.org/wiki/PBKDF2, PBKDF2} based on
 @url{https://en.wikipedia.org/wiki/SHA-2, SHA-512}

diff --git a/doc/govpn.texi b/doc/govpn.texi
index fe842b3a04d73c9f6944f52d6b60d629836f3d12..a22e85f98efe9e633c825c5a31f348f22e8b33b7 100644 (file)
--- a/doc/govpn.texi
+++ b/doc/govpn.texi
@@ -7,7 +7,7 @@
 This manual is for GoVPN -- simple secure free software virtual private
 network (VPN) daemon, written entirely on Go programming language.
 
-Copyright @copyright{} 2014-2015 Sergey Matveev @email{stargrave@@stargrave.org}
+Copyright @copyright{} 2014-2015 @email{stargrave@@stargrave.org, Sergey Matveev}
 
 @quotation
 Permission is granted to copy, distribute and/or modify this document

diff --git a/doc/handshake.texi b/doc/handshake.texi
index 7e0cc5301e903239d82a6300a80d568f2edef84e..0b7f4bd840dea447bbaaab0d5e895c26f59165b9 100644 (file)
--- a/doc/handshake.texi
+++ b/doc/handshake.texi
@@ -23,19 +23,20 @@ Client computes verifier which produces @code{DSAPriv} and
 @item
 Client generates DH keypair: @code{CDHPub} and @code{CDHPriv}.
 Also it generates random 64-bit @code{R} that is used as a nonce for
-symmetric encryption.
+symmetric encryption. @code{El()} is Elligator point encoding algorithm.
 @end enumerate
 
 @strong{Interaction stage}:
 
 @enumerate
 @item
-@verb{|R + enc(H(DSAPub), R, CDHPub) + IDtag -> Server|} [48 bytes]
+@verb{|R + enc(H(DSAPub), R, El(CDHPub)) + IDtag -> Server|} [48 bytes]
 
 @item
 @itemize @bullet
 @item Server remembers client address.
-@item Decrypts @code{CDHPub}.
+@item Decrypts @code{El(CDHPub)}.
+@item Inverts @code{El()} encoding and gets @code{CDHPub}.
 @item Generates DH keypair: @code{SDHPriv}/@code{SDHPub}.
 @item Computes common shared key @code{K = H(DH(SDHPriv, CDHPub))}.
 @item Generates 64-bit random number @code{RS}.
@@ -43,11 +44,12 @@ symmetric encryption.
 @end itemize
 
 @item
-@verb{|enc(H(DSAPub), R+1, SDHPub) + enc(K, R, RS + SS) + IDtag -> Client|} [80 bytes]
+@verb{|enc(H(DSAPub), R+1, El(SDHPub)) + enc(K, R, RS + SS) + IDtag -> Client|} [80 bytes]
 
 @item
 @itemize @bullet
-@item Client decrypts @code{SDHPub}.
+@item Client decrypts @code{El(SDHPub)}.
+@item Inverts @code{El()} encoding and gets @code{SDHPub}.
 @item Computes @code{K}.
 @item Decrypts @code{RS} and @code{SS}.
 @item Remembers @code{SS}.

diff --git a/doc/handshake.txt b/doc/handshake.txt
index 8c3eb3898be080c96303456a928645b296292610..8804ae1cc684211b3f248d5cbf22824920de57cd 100644 (file)
--- a/doc/handshake.txt
+++ b/doc/handshake.txt
@@ -4,12 +4,12 @@ participant Server
 
 Client -> Client : R=rand(64bit)
 Client -> Client : CDHPriv=rand(256bit)
-Client -> Server : R, enc(H(DSAPub), R, CDHPub)
+Client -> Server : R, enc(H(DSAPub), R, El(CDHPub))
 Server -> Server : SDHPriv=rand(256bit)
 Server -> Server : K=H(DH(SDHPriv, CDHPub))
 Server -> Server : RS=rand(64bit)
 Server -> Server : SS=rand(256bit)
-Server -> Client : enc(H(DSAPub), R+1, SDHPub); enc(K, R, RS+SS)
+Server -> Client : enc(H(DSAPub), R+1, El(SDHPub)); enc(K, R, RS+SS)
 Client -> Client : K=H(DH(CDHPriv, SDHPub))
 Client -> Client : RC=rand(64bit); SC=rand(256bit)
 Client -> Server : enc(K, R+1, RS+RC+SC+Sign(DSAPriv, K))

diff --git a/doc/keywords.texi b/doc/keywords.texi
index 39a20e33dc439b44312ebc9a965701d04d04ab9d..a513724a640648574277389211b6c56f4627447c 100644 (file)
--- a/doc/keywords.texi
+++ b/doc/keywords.texi
@@ -2,7 +2,7 @@ Some keywords describing this project: encryption, authentication, key
 exchange, EKE, Diffie-Hellman, DH, DH-EKE, Augmented EKE, A-EKE,
 security, encrypted key exchange, 128-bit margin, DPI, censorship,
 resistance, free software, GPLv3+, reviewability, easy, simple,
-Curve25519, Ed25519, SHA-512, Salsa20, Poly1305, AEAD, XTEA, PBKDF2,
+Curve25519, Ed25519, Elligator, SHA-512, Salsa20, Poly1305, AEAD, XTEA, PBKDF2,
 PRP, signatures, asymmetric cryptography, zero-knowledge password proof,
 PAKE, password, passphrase, password authenticated key exchange, perfect
 forward secrecy, PFS, MAC, nonce, verifier, rehandshake, heartbeat,

diff --git a/doc/overview.texi b/doc/overview.texi
index f6b81ac771075f02233896e49d58619ac6f45b16..dc68994470bfa4776cb60685c1fd9545b5e4d260 100644 (file)
--- a/doc/overview.texi
+++ b/doc/overview.texi
@@ -20,8 +20,9 @@ function based on @url{https://en.wikipedia.org/wiki/SHA-2, SHA-512}
 hash function,
 @url{https://en.wikipedia.org/wiki/Encrypted_key_exchange,
 Diffie-Hellman Augmented Encrypted Key Exchange}
-(DH-A-EKE) powered by @url{http://cr.yp.to/ecdh.html, Curve25519} and
-@url{http://ed25519.cr.yp.to/, Ed25519} signatures.
+(DH-A-EKE) powered by @url{http://cr.yp.to/ecdh.html, Curve25519},
+@url{http://ed25519.cr.yp.to/, Ed25519} signatures and
+@url{http://elligator.cr.yp.to/, Elligator} curve-point encoding.
 Strong
 @url{https://en.wikipedia.org/wiki/Zero-knowledge_password_proof, zero-knowledge}
 mutual authentication with key exchange stage is invulnerable

diff --git a/doc/thanks.texi b/doc/thanks.texi
index 69223702f4e025fee3b04e6f777eefbe98ab78bd..5d68d1c217af2b4d01ae73a1b19db86e90da6ea2 100644 (file)
--- a/doc/thanks.texi
+++ b/doc/thanks.texi
@@ -4,16 +4,18 @@
 @itemize @bullet
 @item
 @url{https://www.schneier.com/books/applied_cryptography/, Applied Cryptography}
-@copyright{} 1996 Bruce Schneier
+@copyright{} 1996 Bruce Schneier.
 @item
 @url{http://tnlandforms.us/cns05/speke.pdf, Strong Password-Only Authenticated Key Exchange}
-@copyright{} 1996 David P. Jablon
+@copyright{} 1996 David P. Jablon.
 @item
 @url{https://www.cs.columbia.edu/~smb/papers/aeke.pdf, Augmented Encrypted Key Exchange}:
 a Password-Based Protocol Secure Against Dictionary Attacks and Password
-File Compromise @copyright{} Steven M. Belloving, Michael Merrit
-@item @url{http://cr.yp.to/ecdh.html, A state-of-the-art Diffie-Hellman function}
-@item @url{http://cr.yp.to/snuffle.html, Snuffle 2005: the Salsa20 encryption function}
-@item @url{http://cr.yp.to/mac.html, A state-of-the-art message-authentication code}
-@item @url{http://ed25519.cr.yp.to/, Ed25519: high-speed high-security signatures}
+File Compromise @copyright{} Steven M. Belloving, Michael Merrit.
+@item @url{http://cr.yp.to/ecdh.html, A state-of-the-art Diffie-Hellman function}.
+@item @url{http://cr.yp.to/snuffle.html, Snuffle 2005: the Salsa20 encryption function}.
+@item @url{http://cr.yp.to/mac.html, A state-of-the-art message-authentication code}.
+@item @url{http://ed25519.cr.yp.to/, Ed25519: high-speed high-security signatures}.
+@item @email{watsonbladd@@gmail.com, Watson Ladd} for suggestion of
+    @url{http://elligator.cr.yp.to/, Elligator} encoding.
 @end itemize

diff --git a/handshake.go b/handshake.go
index 0fee82c77d0e70db8d23d8febf4aaa8021f92394..73cb4e2d35f39c3256e81d278328d30e38ff6c3b 100644 (file)
--- a/handshake.go
+++ b/handshake.go
@@ -27,6 +27,7 @@ import (
        "time"
 
        "github.com/agl/ed25519"
+       "github.com/agl/ed25519/extra25519"
        "golang.org/x/crypto/curve25519"
        "golang.org/x/crypto/salsa20"
        "golang.org/x/crypto/salsa20/salsa"
@@ -100,12 +101,18 @@ func (h *Handshake) rNonceNext(count uint64) []byte {
        return nonce
 }
 
-func dhPrivGen() *[32]byte {
-       dh := new([32]byte)
-       if _, err := rand.Read(dh[:]); err != nil {
-               panic("Can not read random for DH private key")
+func dhKeypairGen() (*[32]byte, *[32]byte) {
+       priv := new([32]byte)
+       pub := new([32]byte)
+       repr := new([32]byte)
+       reprFound := false
+       for !reprFound {
+               if _, err := rand.Read(priv[:]); err != nil {
+                       panic("Can not read random for DH private key")
+               }
+               reprFound = extra25519.ScalarBaseMult(pub, repr, priv)
        }
-       return dh
+       return priv, repr
 }
 
 func dhKeyGen(priv, pub *[32]byte) *[32]byte {
@@ -146,16 +153,15 @@ func idTag(id *PeerId, data []byte) []byte {
 func HandshakeStart(conf *PeerConf, conn *net.UDPConn, addr *net.UDPAddr) *Handshake {
        state := HandshakeNew(addr, conf)
 
-       state.dhPriv = dhPrivGen()
-       dhPub := new([32]byte)
-       curve25519.ScalarBaseMult(dhPub, state.dhPriv)
+       var dhPubRepr *[32]byte
+       state.dhPriv, dhPubRepr = dhKeypairGen()
 
        state.rNonce = new([RSize]byte)
        if _, err := rand.Read(state.rNonce[:]); err != nil {
                panic("Can not read random for handshake nonce")
        }
        enc := make([]byte, 32)
-       salsa20.XORKeyStream(enc, dhPub[:], state.rNonce[:], state.dsaPubH)
+       salsa20.XORKeyStream(enc, dhPubRepr[:], state.rNonce[:], state.dsaPubH)
        data := append(state.rNonce[:], enc...)
        data = append(data, idTag(state.Conf.Id, state.rNonce[:])...)
        if _, err := conn.WriteTo(data, addr); err != nil {
@@ -171,23 +177,29 @@ func HandshakeStart(conf *PeerConf, conn *net.UDPConn, addr *net.UDPAddr) *Hands
 // will be created and used as a transport. If no mutually
 // authenticated Peer is ready, then return nil.
 func (h *Handshake) Server(conn *net.UDPConn, data []byte) *Peer {
-       // R + ENC(H(DSAPub), R, CDHPub) + IDtag
+       // R + ENC(H(DSAPub), R, El(CDHPub)) + IDtag
        if len(data) == 48 && h.rNonce == nil {
-               // Generate private DH key
-               h.dhPriv = dhPrivGen()
-               dhPub := new([32]byte)
-               curve25519.ScalarBaseMult(dhPub, h.dhPriv)
+               // Generate DH keypair
+               var dhPubRepr *[32]byte
+               h.dhPriv, dhPubRepr = dhKeypairGen()
 
                h.rNonce = new([RSize]byte)
                copy(h.rNonce[:], data[:RSize])
 
                // Decrypt remote public key and compute shared key
-               dec := new([32]byte)
-               salsa20.XORKeyStream(dec[:], data[RSize:RSize+32], h.rNonce[:], h.dsaPubH)
-               h.key = dhKeyGen(h.dhPriv, dec)
+               cDHRepr := new([32]byte)
+               salsa20.XORKeyStream(
+                       cDHRepr[:],
+                       data[RSize:RSize+32],
+                       h.rNonce[:],
+                       h.dsaPubH,
+               )
+               cDH := new([32]byte)
+               extra25519.RepresentativeToPublicKey(cDH, cDHRepr)
+               h.key = dhKeyGen(h.dhPriv, cDH)
 
                encPub := make([]byte, 32)
-               salsa20.XORKeyStream(encPub, dhPub[:], h.rNonceNext(1), h.dsaPubH)
+               salsa20.XORKeyStream(encPub, dhPubRepr[:], h.rNonceNext(1), h.dsaPubH)
 
                // Generate R* and encrypt them
                h.rServer = new([RSize]byte)
@@ -259,16 +271,18 @@ func (h *Handshake) Server(conn *net.UDPConn, data []byte) *Peer {
 // authenticated Peer is ready, then return nil.
 func (h *Handshake) Client(conn *net.UDPConn, data []byte) *Peer {
        switch len(data) {
-       case 80: // ENC(H(DSAPub), R+1, SDHPub) + ENC(K, R, RS + SS) + IDtag
+       case 80: // ENC(H(DSAPub), R+1, El(SDHPub)) + ENC(K, R, RS + SS) + IDtag
                if h.key != nil {
                        log.Println("Invalid handshake stage from", h.addr)
                        return nil
                }
 
                // Decrypt remote public key and compute shared key
-               dec := new([32]byte)
-               salsa20.XORKeyStream(dec[:], data[:32], h.rNonceNext(1), h.dsaPubH)
-               h.key = dhKeyGen(h.dhPriv, dec)
+               sDHRepr := new([32]byte)
+               salsa20.XORKeyStream(sDHRepr[:], data[:32], h.rNonceNext(1), h.dsaPubH)
+               sDH := new([32]byte)
+               extra25519.RepresentativeToPublicKey(sDH, sDHRepr)
+               h.key = dhKeyGen(h.dhPriv, sDH)
 
                // Decrypt Rs
                decRs := make([]byte, RSize+SSize)