[PATCH] Add GPG compatible symmetric encryption command

[PATCH] Add GPG compatible symmetric encryption command

[Daiki Ueno]

[-- Attachment #1: Type: text/plain, Size: 1866 bytes --]

AFAICS, only real use-case is a symmetric encryption facility without
invoking a subprocess, as Lars said.  This patch tries to add a command
for it.

This is not intended for inclusion (at the moment, at least), but wanted
to show the fact: one would need fair amount of work to implement a
simple and reasonably secure encryption function, even if raw encryption
primitives are available.  So, decrypt function is currently missing on
purpose (now that encryption is available, it is not hard to implement -
just do reverse), and not too secure as it uses `random'.

To try, run admin/merge-gnulib and recompile.  You will then find the
`simple-encrypt-string' function:

--8<---------------cut here---------------start------------->8---
simple-encrypt-string is a built-in function in `C source code'.

(simple-encrypt-string STRING KEY)

Symmetrically encrypt STRING with KEY and returns ciphertext.

The format of the return value is compatible with GnuPG.
This function currently uses 128-bit AES for the cipher algorithm,
SHA-256 for the hash algorithm, and 8-octet random salt for key
derivation.
--8<---------------cut here---------------end--------------->8---

(simple-encrypt-string "string" "key")
=> cipher

(let ((context (epg-make-context 'OpenPGP)))
  (epg-decrypt-string context (simple-encrypt-string "string" "key")))
=> "string"

I chose OpenPGP format not only for interoperability (though Ted doesn't
seem to care), but also because it is well-tested by cryptanalysts:
http://eprint.iacr.org/2005/033.pdf

This is what I suggested to him before, he agreed, but has never been
realized.  To be honest, I doubt that this feature is generally useful
(maybe only Ted and his auth-source.el users are complaining?) and still
prefer EPG because of security, but I'm tired with the repeated
nonsensical discussions with them.

Regards,
--
Daiki Ueno

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Add-GPG-compatible-symmetric-encryption-command.patch --]
[-- Type: text/x-patch, Size: 10459 bytes --]

From 2eb10b8925e2c6c8146f6202527109ba77210301 Mon Sep 17 00:00:00 2001
From: Daiki Ueno <ueno@gnu.org>
Date: Fri, 7 Feb 2014 16:41:29 +0900
Subject: [PATCH] Add GPG compatible symmetric encryption command

* admin/merge-gnulib (GNULIB_MODULES): Add crypto/rijndael.
* src/fns.c: Include rijndael-alg-fst.h and rijndael-api-fst.h.
(randomize, cipher_write_length)
(cipher_write_session_key_packet)
(cipher_write_literal_data_packet)
(cipher_write_encrypted_data_packet, cipher_init)
(cipher_encrypt, Fsimple_encrypt_string): New function.
(syms_of_fns): Register Ssimple_encrypt_string.
---
 admin/merge-gnulib |   2 +-
 src/fns.c          | 354 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 355 insertions(+), 1 deletion(-)

diff --git a/admin/merge-gnulib b/admin/merge-gnulib
index 75808d3..9e759ce 100755
--- a/admin/merge-gnulib
+++ b/admin/merge-gnulib
@@ -28,7 +28,7 @@ GNULIB_URL=git://git.savannah.gnu.org/gnulib.git
 GNULIB_MODULES='
   alloca-opt byteswap c-ctype c-strcase
   careadlinkat close-stream count-one-bits count-trailing-zeros
-  crypto/md5 crypto/sha1 crypto/sha256 crypto/sha512
+  crypto/md5 crypto/sha1 crypto/sha256 crypto/sha512 crypto/rijndael
   dtoastr dtotimespec dup2 environ execinfo faccessat
   fcntl fcntl-h fdatasync fdopendir filemode fstatat fsync
   getloadavg getopt-gnu gettime gettimeofday
diff --git a/src/fns.c b/src/fns.c
index bc53313..8585fb1 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -4842,6 +4842,359 @@ If BINARY is non-nil, returns a string in binary form.  */)
 {
   return secure_hash (algorithm, object, start, end, Qnil, Qnil, binary);
 }
+
+
+\f
+/************************************************************************
+			Symmetric Key Encryption
+************************************************************************/
+
+#include "rijndael-alg-fst.h"
+#include "rijndael-api-fst.h"
+
+struct cipher_handle
+{
+  rijndaelCipherInstance cipher;
+  rijndaelKeyInstance key;
+
+  char iv[RIJNDAEL_BITSPERBLOCK / 8];
+};
+
+/* FIXME: Use a good random source instead of random().  */
+static void
+randomize (unsigned char *buffer, size_t length)
+{
+  int i;
+
+  /* FIXME: Optimize considering the width of EMACS_INT.  */
+  for (i = 0; i < length; i++)
+    buffer[i] = get_random () & 0xFF;
+}
+
+static size_t
+cipher_write_length (unsigned char *output, size_t output_length, size_t length)
+{
+  if (length <= 191 && output_length >= 1)
+    {
+      output[0] = length;
+      return 1;
+    }
+  else if (length <= 8383 && output_length >= 2)
+    {
+      output[0] = ((length >> 8) & 0xFF) + 192;
+      output[1] = (length & 0xFF) - 192;
+      return 2;
+    }
+  else if (length <= 0xFFFFFFFF && output_length >= 5)
+    {
+      output[0] = 0xFF;
+      output[1] = (length >> 24) & 0xFF;
+      output[2] = (length >> 16) & 0xFF;
+      output[3] = (length >> 8) & 0xFF;
+      output[4] = length & 0xFF;
+      return 5;
+    }
+
+  return 0;
+}
+
+static size_t
+cipher_write_session_key_packet (unsigned char *output, size_t output_length,
+				 unsigned char *salt, size_t salt_length)
+{
+  size_t written;
+  unsigned char *p = output;
+
+  if (salt_length < 8)
+    return 0;
+
+  *p++ = 0xC0 | 3;
+  output_length--;
+
+  written = cipher_write_length (p, output_length, 12);
+  if (!written)
+    return 0;
+
+  output_length -= written;
+  p += written;
+
+  if (output_length < 12)
+    return 0;
+
+  *p++ = 4;
+  *p++ = 7;			/* Cipher: AES128 */
+  *p++ = 0x01;			/* Salted S2K */
+  *p++ = 8;			/* Hash: SHA256 */
+  memcpy (p, salt, 8);
+  p += 8;
+
+  return p - output;
+}
+
+static size_t
+cipher_write_literal_data_packet (unsigned char *output,
+				  size_t output_length,
+				  const unsigned char *input,
+				  size_t input_length)
+{
+  size_t written;
+  unsigned char *p = output;
+
+  *p++ = 0xC0 | 11;
+  output_length--;
+
+  written = cipher_write_length (p, output_length, 6 + input_length);
+  if (!written)
+    return 0;
+
+  output_length -= written;
+  p += written;
+
+  if (output_length < 6 + input_length)
+    return 0;
+
+  *p++ = 'b';			/* Format: binary */
+  *p++ = 0;			/* Filename: none */
+  *p++ = 0;			/* Date: none */
+  *p++ = 0;			/* Date: none */
+  *p++ = 0;			/* Date: none */
+  *p++ = 0;			/* Date: none */
+
+  memcpy (p, input, input_length);
+  p += input_length;
+
+  return p - output;
+}
+
+static size_t
+cipher_write_encrypted_data_packet (unsigned char *output,
+				    size_t output_length,
+				    const unsigned char *input,
+				    size_t input_length)
+{
+  size_t written;
+  unsigned char *p = output;
+
+  *p++ = 0xC0 | 9;
+  output_length--;
+
+  written = cipher_write_length (p, output_length, input_length);
+  if (!written)
+    return 0;
+
+  output_length -= written;
+  p += written;
+
+  if (output_length < input_length)
+    return 0;
+
+  /* Memory may overlap as we use the same buffer for encrypting and
+     formatting packets.  */
+  memmove (p, input, input_length);
+  p += input_length;
+
+  return p - output;
+}
+
+static bool
+cipher_init (struct cipher_handle *handle,
+	     const unsigned char *key,
+	     size_t key_length)
+{
+  int rc;
+  char key_hex[32];
+  const size_t block_size = RIJNDAEL_BITSPERBLOCK / 8;
+  char *p;
+  int i;
+
+  if (key_length < block_size)
+    return false;
+
+  memcpy (key_hex, key, key_length);
+  p = key_hex;
+
+  for (i = block_size - 1; i >= 0; i--)
+    {
+      static char const hexdigit[16] = "0123456789abcdef";
+      int p_i = p[i];
+      p[2 * i] = hexdigit[p_i >> 4];
+      p[2 * i + 1] = hexdigit[p_i & 0xf];
+    }
+
+  rc = rijndaelMakeKey (&handle->key,
+			RIJNDAEL_DIR_ENCRYPT,
+			RIJNDAEL_BITSPERBLOCK,
+			key_hex);
+  memset (key_hex, 0, sizeof (key_hex));
+  if (rc != 0)
+    return false;
+
+  rc = rijndaelCipherInit (&handle->cipher, RIJNDAEL_MODE_ECB, NULL);
+  if (rc != 0)
+    return false;
+
+  memset (handle->iv, 0, sizeof (handle->iv));
+
+  return true;
+}
+
+static size_t
+cipher_encrypt (struct cipher_handle *handle,
+		const unsigned char *input,
+		size_t input_length,
+		unsigned char *output,
+		size_t output_length)
+{
+  int rc;
+  const size_t block_size = RIJNDAEL_BITSPERBLOCK / 8;
+  unsigned char header[RIJNDAEL_BITSPERBLOCK / 8 + 2];
+  int i, nblocks;
+  unsigned char *cp = output;
+
+  randomize (header, block_size);
+  header[block_size] = header[block_size - 2];
+  header[block_size + 1] = header[block_size - 1];
+
+  rc = rijndaelBlockEncrypt (&handle->cipher,
+			     &handle->key,
+			     handle->iv,
+			     RIJNDAEL_BITSPERBLOCK,
+			     handle->iv);
+  if (rc < 0)
+    return 0;
+
+  for (i = 0; i < block_size; i++)
+    *cp++ = handle->iv[i] = handle->iv[i] ^ header[i];
+
+  rc = rijndaelBlockEncrypt (&handle->cipher,
+			     &handle->key,
+			     handle->iv,
+			     RIJNDAEL_BITSPERBLOCK,
+			     handle->iv);
+  if (rc < 0)
+    return 0;
+
+  *cp++ = handle->iv[0] ^ header[block_size];
+  *cp++ = handle->iv[1] ^ header[block_size + 1];
+
+  /* Resynchronization.  */
+  for (i = 0; i < block_size; i++)
+    handle->iv[i] = output[i + 2];
+
+  rc = rijndaelBlockEncrypt (&handle->cipher,
+			     &handle->key,
+			     handle->iv,
+			     RIJNDAEL_BITSPERBLOCK,
+			     handle->iv);
+  if (rc < 0)
+    return 0;
+
+  nblocks = (input_length + block_size - 1) / block_size;
+  for (i = 0; i < nblocks; i++)
+    {
+      size_t length = i == nblocks - 1
+	? input_length - i * block_size
+	: block_size;
+      int j;
+
+      for (j = 0; j < length; j++)
+	*cp++ = handle->iv[j] = handle->iv[j] ^ input[16 * i + j];
+
+      rc = rijndaelBlockEncrypt (&handle->cipher,
+				 &handle->key,
+				 handle->iv,
+				 length * 8,
+				 handle->iv);
+      if (rc < 0)
+	return 0;
+    }
+
+  return cp - output;
+}
+
+DEFUN ("simple-encrypt-string", Fsimple_encrypt_string, Ssimple_encrypt_string,
+       2, 2, 0,
+       doc: /* Symmetrically encrypt STRING with KEY and returns ciphertext.
+
+The format of the return value is compatible with GnuPG.
+This function currently uses 128-bit AES for the cipher algorithm,
+SHA-256 for the hash algorithm, and 8-octet random salt for key
+derivation.  */)
+  (Lisp_Object string, Lisp_Object key)
+{
+  ptrdiff_t length, output_length, written;
+  Lisp_Object encoded_string;
+  unsigned char key_hash[SHA256_DIGEST_SIZE];
+  unsigned char salt[8];
+  const size_t block_size = RIJNDAEL_BITSPERBLOCK / 8;
+  struct sha256_ctx ctx;
+  struct cipher_handle handle;
+  unsigned char *output, *p;
+
+  CHECK_STRING (string);
+  CHECK_STRING (key);
+
+  USE_SAFE_ALLOCA;
+
+  length = 32 + SBYTES (string);
+
+  /* Large enough to hold output and work area.  */
+  output_length = 24 + (length + block_size - 1) / block_size * block_size;
+  output = SAFE_ALLOCA (output_length);
+
+  /* Write Encrypted Session Key packet.  */
+  randomize (salt, sizeof (salt));
+
+  p = output;
+  written = cipher_write_session_key_packet (p,
+					     output_length,
+					     salt, sizeof (salt));
+  eassert (written > 0);
+
+  p += written;
+  output_length -= written;
+
+  /* Initialize cipher and set key.  */
+  sha256_init_ctx (&ctx);
+  sha256_process_bytes (salt, sizeof (salt), &ctx);
+  sha256_process_bytes (SSDATA (key), SBYTES (key), &ctx);
+  sha256_finish_ctx (&ctx, key_hash);
+  cipher_init (&handle, key_hash, sizeof (key_hash));
+  memset (key_hash, 0, sizeof (key_hash));
+
+  /* Perform symmetric encryption.  */
+  written =
+    cipher_write_literal_data_packet (p + block_size + 8,
+				      output_length - (block_size + 8),
+				      (const unsigned char *) SSDATA (string),
+				      SBYTES (string));
+  eassert (written > 0);
+
+  written = cipher_encrypt (&handle,
+			    p + block_size + 8,
+			    written,
+			    p + 6,
+			    output_length);
+  eassert (written > 0);
+
+  written = cipher_write_encrypted_data_packet (p,
+						output_length,
+						p + 6,
+						written);
+  eassert (written > 0);
+
+  p += written;
+  output_length -= written;
+
+  /* Clear the rest of OUTPUT, which may contain part of plaintext.  */
+  memset (p, 0, output_length);
+
+  encoded_string = make_unibyte_string ((char *) output, p - output);
+  SAFE_FREE ();
+
+  return encoded_string;
+}
+
 \f
 void
 syms_of_fns (void)
@@ -4999,6 +5352,7 @@ this variable.  */);
   defsubr (&Smd5);
   defsubr (&Ssecure_hash);
   defsubr (&Slocale_info);
+  defsubr (&Ssimple_encrypt_string);
 
   hashtest_eq.name = Qeq;
   hashtest_eq.user_hash_function = Qnil;
-- 
1.8.4.2

Re: [PATCH] Add GPG compatible symmetric encryption command

[Ted Zlatanov]

On Fri, 07 Feb 2014 17:36:32 +0900 Daiki Ueno <ueno@gnu.org> wrote: 

DU> AFAICS, only real use-case is a symmetric encryption facility without
DU> invoking a subprocess, as Lars said.  This patch tries to add a command
DU> for it.

I mentioned many others, and so have other users.  I'm sorry if you find
it hard to believe our other use cases.

DU> This is not intended for inclusion (at the moment, at least), but wanted
DU> to show the fact: one would need fair amount of work to implement a
DU> simple and reasonably secure encryption function, even if raw encryption
DU> primitives are available.  So, decrypt function is currently missing on
DU> purpose (now that encryption is available, it is not hard to implement -
DU> just do reverse), and not too secure as it uses `random'.
...
DU> This is what I suggested to him before, he agreed, but has never been
DU> realized.  To be honest, I doubt that this feature is generally useful
DU> (maybe only Ted and his auth-source.el users are complaining?) and still
DU> prefer EPG because of security, but I'm tired with the repeated
DU> nonsensical discussions with them.

I'm thankful for your attention to users' needs and willingness to try
finding a solution.  I wrote similar integration code in my original
libnettle patch and am sure it could use similar thoroughness.  I have
no reason to oppose using EPG functions to wrap the crypto primitives.

But I don't see how it affects my request to include the crypto
primitives from GnuTLS/libnettle/libhogweed, since you've already argued
the integration work is hard and needs expert attention.  Does your
patch make my request less pertinent?

Sorry if I'm misunderstanding.

Ted

Re: [PATCH] Add GPG compatible symmetric encryption command

[Daiki Ueno]

Ted Zlatanov <tzz@lifelogs.com> writes:

> DU> AFAICS, only real use-case is a symmetric encryption facility without
> DU> invoking a subprocess, as Lars said.  This patch tries to add a command
> DU> for it.
>
> I mentioned many others, and so have other users.  I'm sorry if you find
> it hard to believe our other use cases.

No, at least I couldn't find any (like others including Stefan and Paul).
All your claims look like:

- <abstract function A> is useful to implement <abstract function B>

and there's no mention of how <abstract function B> would be beneficial
to Emacs.
-- 
Daiki Ueno

Re: [PATCH] Add GPG compatible symmetric encryption command

[Ted Zlatanov]

On Fri, 07 Feb 2014 21:24:03 +0900 Daiki Ueno <ueno@gnu.org> wrote: 

DU> All your claims look like:

DU> - <abstract function A> is useful to implement <abstract function B>

DU> and there's no mention of how <abstract function B> would be beneficial
DU> to Emacs.

As I said, I'm sorry you don't find them convincing.

Meanwhile, would you consider continuing with your patch to the point
where Lars can use it from Gnus?  As I said, I don't think it affects my
request for GnuTLS/libnettle/libhogweed primitives[1] and it would help
Lars avoid having to use an ELisp implementation of Rijndael/AES.  I
certainly would like a unified (via EPG) interface, instead of inventing
a new one.

If you're not interested in continuing, I can pick it up (either as an
EPG change or a standalone library), unless you have objections to that.

Thanks
Ted

[1] you omitted an answer to that question from your reply, so I assume
you agree.

Re: [PATCH] Add GPG compatible symmetric encryption command

[Daiki Ueno]

Ted Zlatanov <tzz@lifelogs.com> writes:

> Meanwhile, would you consider continuing with your patch to the point
> where Lars can use it from Gnus?

I wouldn't take that risk, sorry.  Emacs will soon get CVE numbers
assigned, unless the patch will be carefully reviewed by experts and
actively maintained.  I already found a few flaws that may lead to a
security hole.

However, since it is free software, if your writing of this:

> I wrote similar integration code in my original libnettle patch and am
> sure it could use similar thoroughness.

is true and you _really_ understand the background theory of this
"integration" code, you could perhaps complete the task by yourself?

Let's look at your patch:
http://lists.gnu.org/archive/html/emacs-devel/2013-10/msg00144.html

Ouch.  Why do you expose IV to Elisp and don't use any salt?  Are you
aware that you are negating security doing secret key operation in
Elisp?  Why do you always allocate new memory for key on heap,
plaintext, cipher, and why don't you clear them.  How do you check if
password is correct or wrong.

It's much worse than I expected.  I'm afraid to say you can't write any
security related code that people can depend on, at this skill level.

I'd suggest to read GNUTLS or GnuPG code to learn how practical
encryption code works.  Perhaps my patch might also give you some
inspiration.

> As I said, I don't think it affects my request for
> GnuTLS/libnettle/libhogweed primitives[1]

Well, didn't we already decide to use FFI for that?  That implies those
primitives won't be part of Emacs by default.  Emacs is not your
playground to try out your pseudo security feature.  I remember Stefan
already suggested you to do that in your ELPA package even after FFI
becomes available.

> [1] you omitted an answer to that question from your reply, so I assume
> you agree.

Of course not.
-- 
Daiki Ueno

Re: [PATCH] Add GPG compatible symmetric encryption command

[Ted Zlatanov]

On Sat, 08 Feb 2014 15:24:54 +0900 Daiki Ueno <ueno@gnu.org> wrote: 

DU> Ted Zlatanov <tzz@lifelogs.com> writes:
>> Meanwhile, would you consider continuing with your patch to the point
>> where Lars can use it from Gnus?

DU> I wouldn't take that risk, sorry.  Emacs will soon get CVE numbers
DU> assigned, unless the patch will be carefully reviewed by experts and
DU> actively maintained.  I already found a few flaws that may lead to a
DU> security hole.

OK, I understand your concerns.

DU> Let's look at your patch:
DU> http://lists.gnu.org/archive/html/emacs-devel/2013-10/msg00144.html

DU> Ouch.  Why do you expose IV to Elisp and don't use any salt?  Are you
DU> aware that you are negating security doing secret key operation in
DU> Elisp?  Why do you always allocate new memory for key on heap,
DU> plaintext, cipher, and why don't you clear them.  How do you check if
DU> password is correct or wrong.

DU> It's much worse than I expected.  I'm afraid to say you can't write any
DU> security related code that people can depend on, at this skill level.

I acknowledged your patch was a better approach.  Your criticism is
valid, regardless.

My goal was to make the acceptance tests, which are 90% of the code, and
to show a proof of concept for the API.  The code was not intended to go
into the core in that shape.  As I said:

"I would appreciate any comments at this early stage." and more recently
"I'm sure it could use similar thoroughness [to your patch]."

It was rejected for reasons other than code quality so I saw no point in
improving it further.  When I continue, it will be modeled after your
patch and probably structured as an EPG plugin.

I'll also note that the integration of the hash functions is a large
part of my patch and probably does not need as much review or fixing.
Those functions seem (from a casual reading) to be better optimized and
to offer more choice than the ones in the Emacs core.  Going through
FFI, however, *may* negate the speed benefits.  So perhaps importing
just the hashing functions directly would be practically useful.

DU> I'd suggest to read GNUTLS or GnuPG code to learn how practical
DU> encryption code works.  Perhaps my patch might also give you some
DU> inspiration.

It did, and I think it's good code and a good direction.  It's a shame
you don't want to continue with it.

Ted