Fix Ed25519 keypair generation

Ed25519 private keys, it turns out, have 64 bytes, not 32.

We were previously generating only 32 bytes (which is all that is required to
generate the public key), and then using the public key as the upper 32 bytes
when generating the per-message session key. This meant that everything
appeared to work, but the security of the private key was severely compromised.

By way of fixes:

 * Use the correct algorithm for generating the Ed25519 private key, and store
   all 512 bits of it.

 * Update the account pickle format and refuse to load the old format (since we
   should consider it compromised).

 * Bump the library version, and add a function to retrieve the library
   version, so that applications can verify that they are linked against a
   fixed version of the library.

 * Remove the curve25519_{sign, verify} functions which were unused and of
   dubious quality.

16 files changed, 96 insertions, 172 deletions

diff --git a/CHANGELOG.rst b/CHANGELOG.rst
index 38a8675..9a3f3d7 100644
--- a/CHANGELOG.rst
+++ b/CHANGELOG.rst
@@ -1,3 +1,15 @@
+Changes in `1.1.0 <http://matrix.org/git/olm/commit/?h=1.1.0>`_
+===============================================================
+
+This release includes a fix to a bug which caused Ed25519 keypairs to be
+generated and used insecurely. Any Ed25519 keys generated by libolm 1.0.0
+should be considered compromised.
+
+The fix necessitates a change to the format of the OlmAccount pickle; since
+existing OlmAccounts should in any case be considered compromised (as above),
+the library refuses to load them, returning OLM_BAD_LEGACY_ACCOUNT_PICKLE.
+
+
 Changes in `1.0.0 <http://matrix.org/git/olm/commit/?h=1.0.0>`_
 ===============================================================
 
diff --git a/Makefile b/Makefile
index 1af9b6b..92e3285 100644
--- a/Makefile
+++ b/Makefile
@@ -1,7 +1,7 @@
 #!/usr/bin/make -f
 
 MAJOR := 1
-MINOR := 0
+MINOR := 1
 PATCH := 0
 VERSION := $(MAJOR).$(MINOR).$(PATCH)
 PREFIX ?= /usr/local
@@ -15,9 +15,7 @@ EMCC = emcc
 AFL_CC = afl-gcc
 AFL_CXX = afl-g++
 RELEASE_TARGET := $(BUILD_DIR)/libolm.so.$(VERSION)
-RELEASE_SYMLINKS := $(BUILD_DIR)/libolm.so.$(MAJOR) $(BUILD_DIR)/libolm.so
 DEBUG_TARGET := $(BUILD_DIR)/libolm_debug.so.$(VERSION)
-DEBUG_SYMLINKS := $(BUILD_DIR)/libolm_debug.so.$(MAJOR) $(BUILD_DIR)/libolm_debug.so
 JS_TARGET := javascript/olm.js
 
 JS_EXPORTED_FUNCTIONS := javascript/exported_functions.json
@@ -49,7 +47,10 @@ DOCS := tracing/README.html \
     README.html \
     CHANGELOG.html
 
-CPPFLAGS += -Iinclude -Ilib
+CPPFLAGS += -Iinclude -Ilib \
+    -DOLMLIB_VERSION_MAJOR=$(MAJOR) -DOLMLIB_VERSION_MINOR=$(MINOR) \
+    -DOLMLIB_VERSION_PATCH=$(PATCH)
+
 # we rely on <stdint.h>, which was introduced in C99
 CFLAGS += -Wall -Werror -std=c99 -fPIC
 CXXFLAGS += -Wall -Werror -std=c++11 -fPIC
@@ -98,7 +99,7 @@ $(JS_TARGET): LDFLAGS += $(JS_OPTIMIZE_FLAGS)
 
 ### top-level targets
 
-lib: $(RELEASE_TARGET) $(RELEASE_SYMLINKS)
+lib: $(RELEASE_TARGET)
 .PHONY: lib
 
 $(RELEASE_TARGET): $(RELEASE_OBJECTS)
@@ -106,11 +107,9 @@ $(RELEASE_TARGET): $(RELEASE_OBJECTS)
             -Wl,-soname,libolm.so.$(MAJOR) \
             -Wl,--version-script,version_script.ver \
             $(OUTPUT_OPTION) $(RELEASE_OBJECTS)
+	ldconfig -l $@
 
-$(RELEASE_SYMLINKS):
-	ln -s libolm.so.$(VERSION) $@
-
-debug: $(DEBUG_TARGET) $(DEBUG_SYMLINKS)
+debug: $(DEBUG_TARGET)
 .PHONY: debug
 
 $(DEBUG_TARGET): $(DEBUG_OBJECTS)
@@ -118,9 +117,7 @@ $(DEBUG_TARGET): $(DEBUG_OBJECTS)
             -Wl,-soname,libolm_debug.so.$(MAJOR) \
             -Wl,--version-script,version_script.ver \
             $(OUTPUT_OPTION) $(DEBUG_OBJECTS)
-
-$(DEBUG_SYMLINKS):
-	ln -s libolm_debug.so.$(VERSION) $@
+	ldconfig -l $@
 
 js: $(JS_TARGET)
 .PHONY: js
diff --git a/include/olm/crypto.hh b/include/olm/crypto.hh
index 64e8f7d..484dc83 100644
--- a/include/olm/crypto.hh
+++ b/include/olm/crypto.hh
@@ -25,6 +25,7 @@
 
 namespace olm {
 
+static const std::size_t ED25519_PRIVATE_KEY_LENGTH = 64;
 static const std::size_t KEY_LENGTH = 32;
 static const std::size_t SIGNATURE_LENGTH = 64;
 static const std::size_t IV_LENGTH = 16;
@@ -45,7 +46,7 @@ struct Ed25519PublicKey {
 
 
 struct Ed25519KeyPair : public Ed25519PublicKey {
-    std::uint8_t private_key[KEY_LENGTH];
+    std::uint8_t private_key[ED25519_PRIVATE_KEY_LENGTH];
 };
 
 
@@ -65,24 +66,6 @@ void curve25519_shared_secret(
 );
 
 
-/** Signs the message using our private key.
- * The output buffer must be at least 64 bytes long. */
-void curve25519_sign(
-    Curve25519KeyPair const & our_key,
-    std::uint8_t const * message, std::size_t message_length,
-    std::uint8_t * output
-);
-
-
-/** Verify their message using their public key.
- * The signature input buffer must be 64 bytes long.
- * Returns true if the signature is valid. */
-bool curve25519_verify(
-    Curve25519PublicKey const & their_key,
-    std::uint8_t const * message, std::size_t message_length,
-    std::uint8_t const * signature
-);
-
 /** Generate a curve25519 key pair from 32 random bytes. */
 void ed25519_generate_key(
     std::uint8_t const * random_32_bytes,
diff --git a/include/olm/error.h b/include/olm/error.h
index 98d2cf5..1c44de8 100644
--- a/include/olm/error.h
+++ b/include/olm/error.h
@@ -39,6 +39,13 @@ enum OlmErrorCode {
                                       * known session key.
                                       */
 
+    /**
+     * Attempt to unpickle an account which uses pickle version 1 (which did
+     * not save enough space for the Ed25519 key; the key should be considered
+     * compromised. We don't let the user reload the account.
+     */
+    OLM_BAD_LEGACY_ACCOUNT_PICKLE = 13,
+
     /* remember to update the list of string constants in error.c when updating
      * this list. */
 };
diff --git a/include/olm/olm.h b/include/olm/olm.h
index dbaf71e..0886fa9 100644
--- a/include/olm/olm.h
+++ b/include/olm/olm.h
@@ -33,6 +33,11 @@ typedef struct OlmAccount OlmAccount;
 typedef struct OlmSession OlmSession;
 typedef struct OlmUtility OlmUtility;
 
+/** Get the version number of the library.
+ * Arguments will be updated if non-null.
+ */
+void olm_get_library_version(uint8_t *major, uint8_t *minor, uint8_t *patch);
+
 /** The size of an account object in bytes */
 size_t olm_account_size();
 
diff --git a/javascript/olm_post.js b/javascript/olm_post.js
index f423b93..955d68d 100644
--- a/javascript/olm_post.js
+++ b/javascript/olm_post.js
@@ -402,4 +402,14 @@ Utility.prototype['ed25519_verify'] = restore_stack(function(
 olm_exports["Account"] = Account;
 olm_exports["Session"] = Session;
 olm_exports["Utility"] = Utility;
+
+olm_exports["get_library_version"] = restore_stack(function() {
+    var buf = stack(3);
+    Module['_olm_get_library_version'](buf, buf+1, buf+2);
+    return [
+        getValue(buf, 'i8'),
+        getValue(buf+1, 'i8'),
+        getValue(buf+2, 'i8'),
+    ];
+});
 }();
diff --git a/lib/ed25519_additions.c b/lib/ed25519_additions.c
deleted file mode 100644
index 5fa0c68..0000000
--- a/lib/ed25519_additions.c
+++ /dev/null
@@ -1,43 +0,0 @@
-void convert_curve25519_to_ed25519(
-    unsigned char * public_key,
-    unsigned char * signature
-) {
-    fe mont_x, mont_x_minus_one, mont_x_plus_one, inv_mont_x_plus_one;
-    fe one;
-    fe ed_y;
-
-    fe_frombytes(mont_x, public_key);
-    fe_1(one);
-    fe_sub(mont_x_minus_one, mont_x, one);
-    fe_add(mont_x_plus_one, mont_x, one);
-    fe_invert(inv_mont_x_plus_one, mont_x_plus_one);
-    fe_mul(ed_y, mont_x_minus_one, inv_mont_x_plus_one);
-    fe_tobytes(public_key, ed_y);
-
-    public_key[31] &= 0x7F;
-    public_key[31] |= (signature[63] & 0x80);
-    signature[63] &= 0x7F;
-}
-
-
-void convert_ed25519_to_curve25519(
-    unsigned char const * public_key,
-    unsigned char * signature
-) {
-    unsigned char sign_bit = public_key[31] & 0x80;
-    signature[63] &= 0x7F;
-    signature[63] |= sign_bit;
-}
-
-
-void ed25519_keypair(
-    unsigned char * private_key,
-    unsigned char * public_key
-) {
-    ge_p3 A;
-    private_key[0] &= 248;
-    private_key[31] &= 63;
-    private_key[31] |= 64;
-    ge_scalarmult_base(&A, private_key);
-    ge_p3_tobytes(public_key, &A);
-}
diff --git a/lib/ed25519_additions.h b/lib/ed25519_additions.h
deleted file mode 100644
index e5f93a1..0000000
--- a/lib/ed25519_additions.h
+++ /dev/null
@@ -1,24 +0,0 @@
-#ifndef ED25519_ADDITIONS_H
-#define ED25519_ADDITIONS_H
-
-#ifdef __cplusplus
-extern "C" {
-#endif
-
-void convert_curve25519_to_ed25519(
-    unsigned char * public_key,
-    unsigned char * signature);
-
-void convert_ed25519_to_curve25519(
-    unsigned char const * public_key,
-    unsigned char * signature);
-
-void ed25519_keypair(
-    unsigned char * private_key,
-    unsigned char * public_key);
-
-#ifdef __cplusplus
-}
-#endif
-
-#endif
diff --git a/python/olm/_base.py b/python/olm/_base.py
index 8238957..bc5c206 100644
--- a/python/olm/_base.py
+++ b/python/olm/_base.py
@@ -7,7 +7,7 @@ def read_random(n):
         return f.read(n)
 
 lib = cdll.LoadLibrary(os.path.join(
-    os.path.dirname(__file__), "..", "..", "build", "libolm.so")
+    os.path.dirname(__file__), "..", "..", "build", "libolm.so.1")
 )
 
 lib.olm_error.argtypes = []
diff --git a/src/account.cpp b/src/account.cpp
index c8e6e40..ec763f8 100644
--- a/src/account.cpp
+++ b/src/account.cpp
@@ -326,7 +326,9 @@ static std::uint8_t const * unpickle(
 } // namespace olm
 
 namespace {
-static const std::uint32_t ACCOUNT_PICKLE_VERSION = 1;
+// pickle version 1 used only 32 bytes for the ed25519 private key.
+// Any keys thus used should be considered compromised.
+static const std::uint32_t ACCOUNT_PICKLE_VERSION = 2;
 }
 
 
@@ -360,9 +362,15 @@ std::uint8_t const * olm::unpickle(
 ) {
     uint32_t pickle_version;
     pos = olm::unpickle(pos, end, pickle_version);
-    if (pickle_version != ACCOUNT_PICKLE_VERSION) {
-        value.last_error = OlmErrorCode::OLM_UNKNOWN_PICKLE_VERSION;
-        return end;
+    switch (pickle_version) {
+        case ACCOUNT_PICKLE_VERSION:
+            break;
+        case 1:
+            value.last_error = OlmErrorCode::OLM_BAD_LEGACY_ACCOUNT_PICKLE;
+            return end;
+        default:
+            value.last_error = OlmErrorCode::OLM_UNKNOWN_PICKLE_VERSION;
+            return end;
     }
     pos = olm::unpickle(pos, end, value.identity_keys);
     pos = olm::unpickle(pos, end, value.one_time_keys);
diff --git a/src/crypto.cpp b/src/crypto.cpp
index 4fa92f1..83493be 100644
--- a/src/crypto.cpp
+++ b/src/crypto.cpp
@@ -25,7 +25,6 @@ extern "C" {
 }
 
 #include "ed25519/src/ed25519.h"
-#include "ed25519_additions.h"
 #include "curve25519-donna.h"
 
 namespace {
@@ -121,48 +120,14 @@ void olm::curve25519_shared_secret(
 }
 
 
-void olm::curve25519_sign(
-    olm::Curve25519KeyPair const & our_key,
-    std::uint8_t const * message, std::size_t message_length,
-    std::uint8_t * output
-) {
-    std::uint8_t private_key[KEY_LENGTH];
-    std::uint8_t public_key[KEY_LENGTH];
-    std::memcpy(private_key, our_key.private_key, KEY_LENGTH);
-    ::ed25519_keypair(private_key, public_key);
-    ::ed25519_sign(
-        output,
-        message, message_length,
-        public_key, private_key
-    );
-    ::convert_ed25519_to_curve25519(public_key, output);
-}
-
-
-bool olm::curve25519_verify(
-    olm::Curve25519PublicKey const & their_key,
-    std::uint8_t const * message, std::size_t message_length,
-    std::uint8_t const * signature
-) {
-    std::uint8_t public_key[KEY_LENGTH];
-    std::uint8_t signature_buffer[SIGNATURE_LENGTH];
-    std::memcpy(public_key, their_key.public_key, KEY_LENGTH);
-    std::memcpy(signature_buffer, signature, SIGNATURE_LENGTH);
-    ::convert_curve25519_to_ed25519(public_key, signature_buffer);
-    return 0 != ::ed25519_verify(
-        signature,
-        message, message_length,
-        public_key
-    );
-}
-
-
 void olm::ed25519_generate_key(
     std::uint8_t const * random_32_bytes,
     olm::Ed25519KeyPair & key_pair
 ) {
-    std::memcpy(key_pair.private_key, random_32_bytes, KEY_LENGTH);
-    ::ed25519_keypair(key_pair.private_key, key_pair.public_key);
+    ::ed25519_create_keypair(
+        key_pair.public_key, key_pair.private_key,
+        random_32_bytes
+    );
 }
 
 
diff --git a/src/ed25519.c b/src/ed25519.c
index f4f910d..c7a1a8e 100644
--- a/src/ed25519.c
+++ b/src/ed25519.c
@@ -16,7 +16,7 @@
 #include "ed25519/src/fe.c"
 #include "ed25519/src/sc.c"
 #include "ed25519/src/ge.c"
+#include "ed25519/src/keypair.c"
 #include "ed25519/src/sha512.c"
 #include "ed25519/src/verify.c"
 #include "ed25519/src/sign.c"
-#include "ed25519_additions.c"
diff --git a/src/error.c b/src/error.c
index bd8a39d..b742197 100644
--- a/src/error.c
+++ b/src/error.c
@@ -29,6 +29,7 @@ static const char * ERRORS[] = {
     "CORRUPTED_PICKLE",
     "BAD_SESSION_KEY",
     "UNKNOWN_MESSAGE_INDEX",
+    "BAD_LEGACY_ACCOUNT_PICKLE",
 };
 
 const char * _olm_error_to_string(enum OlmErrorCode error)
diff --git a/src/olm.cpp b/src/olm.cpp
index 0a4a734..682a84c 100644
--- a/src/olm.cpp
+++ b/src/olm.cpp
@@ -98,6 +98,11 @@ std::size_t b64_input(
 
 extern "C" {
 
+void olm_get_library_version(uint8_t *major, uint8_t *minor, uint8_t *patch) {
+    if (major != NULL) *major = OLMLIB_VERSION_MAJOR;
+    if (minor != NULL) *minor = OLMLIB_VERSION_MINOR;
+    if (patch != NULL) *patch = OLMLIB_VERSION_PATCH;
+}
 
 size_t olm_error() {
     return std::size_t(-1);
diff --git a/tests/test_crypto.cpp b/tests/test_crypto.cpp
index 1041538..175f66f 100644
--- a/tests/test_crypto.cpp
+++ b/tests/test_crypto.cpp
@@ -83,35 +83,6 @@ assert_equals(expected_agreement, actual_agreement, 32);
 } /* Curve25529 Test Case 1 */
 
 
-{ /* Curve25519 Signature Test Case 1 */
-TestCase test_case("Curve25519 Signature Test Case 1");
-
-std::uint8_t private_key[33] = "This key is a string of 32 bytes";
-std::uint8_t message[] = "message";
-std::size_t message_length = sizeof(message) - 1;
-
-olm::Curve25519KeyPair key_pair;
-olm::curve25519_generate_key(private_key, key_pair);
-
-std::uint8_t signature[64];
-
-olm::curve25519_sign(
-    key_pair, message, message_length, signature
-);
-
-bool result = olm::curve25519_verify(
-    key_pair, message, message_length, signature
-);
-assert_equals(true, result);
-
-message[0] = 'n';
-result = olm::curve25519_verify(
-    key_pair, message, message_length, signature
-);
-assert_equals(false, result);
-
-} /* Curve25519 Signature Test Case 1 */
-
 {
 TestCase test_case("Ed25519 Signature Test Case 1");
 std::uint8_t private_key[33] = "This key is a string of 32 bytes";
diff --git a/tests/test_olm.cpp b/tests/test_olm.cpp
index de7e236..af2c9f7 100644
--- a/tests/test_olm.cpp
+++ b/tests/test_olm.cpp
@@ -65,6 +65,33 @@ assert_equals(pickle1, pickle2, pickle_length);
 
 }
 
+
+{
+    TestCase test_case("Old account unpickle test");
+
+    // this uses the old pickle format, which did not use enough space
+    // for the Ed25519 key. We should reject it.
+    std::uint8_t pickle[] =
+        "x3h9er86ygvq56pM1yesdAxZou4ResPQC9Rszk/fhEL9JY/umtZ2N/foL/SUgVXS"
+        "v0IxHHZTafYjDdzJU9xr8dQeBoOTGfV9E/lCqDGBnIlu7SZndqjEKXtzGyQr4sP4"
+        "K/A/8TOu9iK2hDFszy6xETiousHnHgh2ZGbRUh4pQx+YMm8ZdNZeRnwFGLnrWyf9"
+        "O5TmXua1FcU";
+
+    std::uint8_t account_buffer[::olm_account_size()];
+    ::OlmAccount *account = ::olm_account(account_buffer);
+    assert_equals(
+        std::size_t(-1),
+        ::olm_unpickle_account(
+            account, "", 0, pickle, sizeof(pickle)-1
+        )
+    );
+    assert_equals(
+        std::string("BAD_LEGACY_ACCOUNT_PICKLE"),
+        std::string(::olm_account_last_error(account))
+    );
+}
+
+
 { /** Pickle session test */
 
 TestCase test_case("Pickle session test");