16
\$\begingroup\$

This challenge carries a bounty of 200 points for the first to answer and remain unbeaten for at least 3 days. Claimed by user3080953.

There's a lot of talk lately about end-to-end encryption, and pressure on companies to remove it from their products. I'm not interested in the rights-and-wrongs of that, but I wondered: how short can code be that would get a company pressured into not using it?

The challenge here is to implement a Diffie Hellman key exchange between two networked systems, then allow the users to communicate back-and-forth using the generated symmetric key. For the purpose of this task, no other protections are required (e.g. no need to cycle the key, verify identities, protect against DoS, etc.) and you can assume an open internet (any ports you listen on are available to everyone). Use of builtins is allowed and encouraged!

You may choose one of two models:

  • A server and a client: the client connects to the server, then server or client can send messages to the other. Third-parties in between the two must be unable to read the messages. An example flow could be:
    1. User A launches server
    2. User B launches client and directs it to user A's server (e.g. via IP/port), the program opens a connection
    3. User A's program acknowledges the connection (optionally asking the user for consent first)
    4. User B's program begins generation of a DH secret, and sends the required data (public key, prime, generator, anything else your implementation needs) to User A
    5. User A's program uses the sent data to complete generation of the shared secret and sends back the required data (public key) to User B. From this point, User A can enter messages (e.g. via stdin) which will be encrypted and sent to User B (e.g. to stdout).
    6. User B's program completes generation of the shared secret. From this point, User B can send messages to User A.
  • Or: A server with two clients connected to it: each client talks to the server, which forwards their message to the other client. The server itself (and any third-parties in between) must be unable to read the messages. Other than the initial connection, the process is the same as that described in the first option.

Detailed rules:

  • You can provide a single program, or multiple programs (e.g. server & client). Your score is the total code size across all programs.
  • Your program must be theoretically capable of communicating over a network (but for testing, localhost is fine). If your language of choice doesn't support networking, you can combine it with something that does (e.g. a shell script); in this case your score is the total code size across all languages used.
  • The Diffie Hellman key generation can use hard-coded "p" and "g" values.
  • The generated shared key must be at least 1024 bits.
  • Once the key is shared, the choice of symmetric-key encryption is up to you, but you must not pick a method which is currently known to have a practical attack against it (e.g. a caesar shift is trivial to reverse without knowledge of the key). Example permitted algorithms:
    • AES (any key size)
    • RC4 (theoretically broken, but no practical attacks that I can find mention of, so it's allowable here)
  • Users A and B must both be able to send messages to each other (two-way communication) interactively (e.g. reading lines from stdin, continually prompting, or events such as pressing a button). If it makes it easier, you may assume an alternating conversation (i.e. after a user sends a message, they must wait for a response before sending their next message)
  • Language builtins are permitted (no need to write your own cryptographic or networking methods if they're already supported).
  • The underlying communication format is up to you.
  • The communication steps given above are an example, but you are not required to follow them (as long as the necessary information is shared, and no middle-men are able to calculate the shared key or messages)
  • If the details needed to connect to your server are not known in advance (e.g. if it listens on a random port), these details must be printed. You can assume that the IP address of the machine is known.
  • Error handling (e.g. invalid addresses, lost connections, etc.) is not required.
  • The challenge is code golf, so the shortest code in bytes wins.
\$\endgroup\$
  • \$\begingroup\$ Is hardcoding p and g allowed? \$\endgroup\$ – ASCII-only Apr 14 '17 at 23:52
  • \$\begingroup\$ @ASCII-only from what I can tell, hard-coding good quality p & g values is considered fine (unless the developer maliciously uses values known to be vulnerable to particular attacks). So for this challenge it's OK (as long as the resulting secret is at least 1024 bits) \$\endgroup\$ – Dave Apr 15 '17 at 5:26
2
+200
\$\begingroup\$

Node.js (372 423+94=517 513 bytes)

Golfed

Linebreaks added for "readability".

chat.js (423 419 bytes)

No line breaks

[n,c,p]=["net","crypto","process"].map(require);r="rc4",a="create",h="DiffieHellman",z="pipe",w="write",o=128,g=p.argv;s=e=d=0,y=c[a+h](8*o),k=y.generateKeys();v=n.connect(9,g[2],_=>{g[3]&&(v[w](y.getPrime()),v[w](k));v.on("data",b=>{s||(g[3]||(y=c[a+h](b.slice(0,o)),k=y.generateKeys(),v[w](k),b=b.slice(o)),s=y.computeSecret(b),e=c[a+"Cipher"](r,s),p.stdin[z](e)[z](v),d=c[a+"Decipher"](r,s),v[z](d)[z](p.stdout))})})

Line breaks

[n,c,p]=["net","crypto","process"].map(require);
r="rc4",a="create",h="DiffieHellman",z="pipe",w="write",o=128,g=p.argv;
s=e=d=0,y=c[a+h](8*o),k=y.generateKeys();
v=n.connect(9,g[2],_=>{g[3]&&(v[w](y.getPrime()),v[w](k));
v.on("data",b=>{s||(g[3]||(y=c[a+h](b.slice(0,o)),k=y.generateKeys(),
v[w](k),b=b.slice(o)),s=y.computeSecret(b),e=c[a+"Cipher"](r,s),p.stdin[z](e)[z](v)
,d=c[a+"Decipher"](r,s),v[z](d)[z](p.stdout))})})

echo_server.js (94 bytes)

c=[],require("net").createServer(a=>{c.forEach(b=>{a.pipe(b),b.pipe(a)});c.push(a)}).listen(9);

Ungolfed

Node has built-in networking and crypto capabilities. This uses TCP for networking (because it's simpler than Node's interface for HTTP, and it plays nicely with streams).

I use a stream cipher (RC4) instead of AES to avoid having to deal with block sizes. Wikipedia seems to think it can be vulnerable, so if anyone has any insights into which ciphers are preferred, that would be great.

Run the echo server node echo_server.js which will listen on port 9. Run two instances of this program with node chat.js <server IP> and node chat.js <server IP> 1 (the last argument just sets which one sends a prime). Each instance connects to the echo server. The first message handles the key generation, and subsequent messages use the stream cipher.

The echo server just sends everything back to all the connected clients except the original.

Client

var net = require('net');
var crypto = require('crypto');
var process = require('process');
let [serverIP, first] = process.argv.slice(2);

var keys = crypto.createDiffieHellman(1024); // DH key exchange
var prime = keys.getPrime();
var k = keys.generateKeys();
var secret;

var cipher; // symmetric cipher
var decipher;

// broadcast prime
server = net.connect(9, serverIP, () => {
    console.log('connect')
    if(first) {
        server.write(prime);
        console.log('prime length', prime.length)
        server.write(k);
    }

    server.on('data', x => {
        if(!secret) { // if we still need to get the ciphers
            if(!first) { // generate a key with the received prime
                keys = crypto.createDiffieHellman(x.slice(0,128)); // separate prime and key
                k = keys.generateKeys();
                server.write(k);
                x = x.slice(128)
            }

            // generate the secret
            console.log('length x', x.length);
            secret = keys.computeSecret(x);
            console.log('secret', secret, secret.length) // verify that secret key is the same
            cipher = crypto.createCipher('rc4', secret);
            process.stdin.pipe(cipher).pipe(server);
            decipher = crypto.createDecipher('rc4', secret);
            server.pipe(decipher).pipe(process.stdout);
        }
        else {
            console.log('sent text ', x.toString()) // verify that text is sent encrypted
        }
    });
})

Echo server

var net = require('net');
clients = [];

net.createServer(socket => {
    clients.forEach(c=>{socket.pipe(c); c.pipe(socket)});
    clients.push(socket);
}).listen(9)

Thanks Dave for all the tips + feedback!

\$\endgroup\$
  • 1
    \$\begingroup\$ Don't add readability to the golfed version, that's what the ungolfed version is for. Or if you do that, remove the semicolons before the line breaks, so it's the same length. \$\endgroup\$ – mbomb007 Apr 20 '17 at 17:58
  • \$\begingroup\$ @mbomb007 the "readability" is mostly to avoid having to scroll. unfortunately, the body of the code has no semicolons, so that doesn't work. I figured a quick find and replace wouldn't be too onerous. will definitely keep your tip in mind for future comments though! \$\endgroup\$ – user3080953 Apr 21 '17 at 7:12
  • \$\begingroup\$ @Dave thanks for all the feedback! I've made changes to use vanilla DH, which actually added quite a bit of length because you need to exchange primes as well AES actually works as a drop-in replacement, but the problem with AES is that nothing sends until you've completed a block, and padding would be a pain. also rc4 is shorter than aes128 \$\endgroup\$ – user3080953 Apr 21 '17 at 7:17
  • 1
    \$\begingroup\$ I wasn't sure if it would work over a network, but it probably won't, and I wrote it on a bus so I had no way of checking. the new version uses an echo server instead. This also solves the timeout problem. I was trying to avoid a server + client, but it is much better form. finally, thanks for this challenge, I learned a tonne about how to actually use node instead of just grabbing libraries from everywhere :) \$\endgroup\$ – user3080953 Apr 21 '17 at 7:19
  • \$\begingroup\$ @user3080953 sounds good. With those updates you should be in the running for the bounty! \$\endgroup\$ – Dave Apr 21 '17 at 7:25
0
\$\begingroup\$

Node.js, 638 607 bytes

Now that it's been well and truly beaten (and in the same language), here's my test answer:

R=require,P=process,s=R('net'),y=R('crypto'),w=0,C='create',W='write',D='data',B='hex',G=_=>a.generateKeys(B),Y=(t,m,g,f)=>g((c=y[C+t+'ipher']('aes192',w,k='')).on('readable',_=>k+=(c.read()||'').toString(m)).on('end',_=>f(k)))+c.end(),F=C+'DiffieHellman',X=s=>s.on(D,x=>(x+'').split(B).map(p=>p&&(w?Y('Dec','utf8',c=>c[W](p,B),console.log):P.stdin.on(D,m=>Y('C',B,c=>c[W](m),r=>s[W](r+B)),([p,q,r]=p.split(D),r&&s[W](G(a=y[F](q,B,r,B))),w=a.computeSecret(p,B))))));(R=P.argv)[3]?X(s.Socket()).connect(R[3],R[2]):s[C+'Server'](s=>X(s,a=y[F](2<<9))[W](G()+D+a.getPrime(B)+D+a.getGenerator(B)+B)).listen(R[2])

Or with wrapping:

R=require,P=process,s=R('net'),y=R('crypto'),w=0,C='create',W='write',D='data',B
='hex',G=_=>a.generateKeys(B),Y=(t,m,g,f)=>g((c=y[C+t+'ipher']('aes192',w,k=''))
.on('readable',_=>k+=(c.read()||'').toString(m)).on('end',_=>f(k)))+c.end(),F=C+
'DiffieHellman',X=s=>s.on(D,x=>(x+'').split(B).map(p=>p&&(w?Y('Dec','utf8',c=>c[
W](p,B),console.log):P.stdin.on(D,m=>Y('C',B,c=>c[W](m),r=>s[W](r+B)),([p,q,r]=p
.split(D),r&&s[W](G(a=y[F](q,B,r,B))),w=a.computeSecret(p,B))))));(R=P.argv)[3]?
X(s.Socket()).connect(R[3],R[2]):s[C+'Server'](s=>X(s,a=y[F](2<<9))[W](G()+D+a.
getPrime(B)+D+a.getGenerator(B)+B)).listen(R[2])

Usage

This is a server/client implementation; one instantiation will be the server, and the other the client. The server is launched with a specific port, then the client is pointed to the server's port. DH can take a few seconds to set-up if your machine is low on entropy, so the first messages may be delayed a little.

MACHINE 1                       MACHINE 2
$ node e2e.js <port>            :
:                               $ node e2e.js <address> <port>
$ hello                         :
:                               : hello
:                               $ hi
: hi                            :

Breakdown

s=require('net'),
y=require('crypto'),
w=0,                                      // Shared secret starts unknown
Y=(t,m,g,f)=>g(                           // Helper for encryption & decryption
  (c=y['create'+t+'ipher']('aes192',w,k=''))
  .on('readable',_=>k+=(c.read()||'').toString(m))
  .on('end',_=>f(k)))+c.end();
X=s=>s.on('data',x=>(x+'').split('TOKEN2').map(p=>
  p&&(w                                   // Have we completed handshake?
    ?Y('Dec','utf8',c=>c.write(p,'hex'),console.log) // Decrypt + print messages
    :                                     // Haven't completed handshake:
     process.stdin.on('data',m=>          //  Prepare to encrypt + send input
       Y('C','hex',c=>c.write(m),r=>s.write(r+'TOKEN2')),(
       [p,q,r]=p.split('TOKEN1'),         //  Split up DH data sent to us
       r&&                                //  Given DH details? (client)
          s.write(
            (a=y.createDiffieHellman(     //   Compute key pair...
              q,'hex',r,'hex')            //   ...using the received params
            ).generateKeys('hex')),       //   And send the public key
       w=a.computeSecret(p,'hex')         //  Compute shared secret
       //,console.log(w.toString('hex'))  //  Print if you want to verify no MITM
))))),
(R=process.argv)[3]                       // Are we running as a client?
  ?X(s.Socket()).connect(R[3],R[2])       // Connect & start chat
  :s.createServer(s=>                     // Start server. On connection:
    X(s,                                  //  Start chat,
      a=y.createDiffieHellman(1024))      //  Calc DiffieHellman,
    .write(                               //  Send public key & public DH details
      a.generateKeys('hex')+'TOKEN1'+
      a.getPrime('hex')+'TOKEN1'+
      a.getGenerator('hex')+'TOKEN2')
  ).listen(R[2])                          // Listen on requested port

The only requirement for the tokens is that they contain at least one non-hex character, so in the minified code other string constants are used (data and hex).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.