Kompleksowe szyfrowanie gry w golfa

16

To wyzwanie wiąże się z nagrodą w wysokości 200 punktów za pierwszą odpowiedź i pozostaje niepokonane przez co najmniej 3 dni. Zgłoszony przez użytkownika3080953 .

Ostatnio dużo się mówi o szyfrowaniu typu end-to-end i presji na firmy, by usunęły go z ich produktów. Nie interesuje mnie to, co jest dobre i złe, ale zastanawiałem się: jak krótki może być kod, który zmusiłby firmę do wywierania presji na nieużywanie go?

Wyzwanie polega na wdrożeniu wymiany kluczy Diffie Hellman między dwoma systemami sieciowymi, a następnie umożliwieniu użytkownikom komunikacji w obie strony za pomocą wygenerowanego klucza symetrycznego. Na potrzeby tego zadania nie są wymagane żadne inne zabezpieczenia (np. Nie trzeba cyklicznie zmieniać klucza, weryfikować tożsamości, chronić przed DoS itp.) I można założyć otwarty internet (wszystkie porty, na których nasłuchuje się, są dostępne dla wszystkich). Korzystanie z wbudowanych jest dozwolone i zalecane!

Możesz wybrać jeden z dwóch modeli:

  • Serwer i klient: klient łączy się z serwerem, a następnie serwer lub klient może wysyłać wiadomości do drugiego. Zewnętrzne strony między nimi muszą nie być w stanie odczytać wiadomości. Przykładowy przepływ może być:
    1. Użytkownik A uruchamia serwer
    2. Użytkownik B uruchamia klienta i kieruje go do serwera użytkownika A (np. Przez IP / port), program otwiera połączenie
    3. Program użytkownika A potwierdza połączenie (opcjonalnie najpierw pytając użytkownika o zgodę)
    4. Program użytkownika B rozpoczyna generowanie sekretu DH i wysyła wymagane dane (klucz publiczny, liczba pierwsza, generator, wszystko inne, czego potrzebuje Twoja implementacja) do użytkownika A
    5. Program użytkownika A wykorzystuje przesłane dane do ukończenia generowania wspólnego klucza tajnego i odsyła wymagane dane (klucz publiczny) do użytkownika B. Od tego momentu użytkownik A może wprowadzać wiadomości (np. Przez stdin), które będą szyfrowane i wysyłane do użytkownika B (np. Na standardowe wyjście).
    6. Program użytkownika B kończy generowanie wspólnego klucza tajnego. Od tego momentu użytkownik B może wysyłać wiadomości do użytkownika A.
  • Lub: Serwer z dwoma podłączonymi klientami: każdy klient rozmawia z serwerem, który przekazuje swoją wiadomość do drugiego klienta. Sam serwer (i wszelkie strony trzecie pomiędzy nimi) nie mogą odczytać wiadomości. Poza początkowym połączeniem proces jest taki sam, jak opisany w pierwszej opcji.

Szczegółowe zasady:

  • Możesz podać jeden program lub wiele programów (np. Serwer i klient). Twój wynik to całkowity rozmiar kodu we wszystkich programach.
  • Twój program musi teoretycznie być w stanie komunikować się przez sieć (ale do testowania localhost jest w porządku). Jeśli twój wybrany język nie obsługuje sieci, możesz połączyć go z czymś, co działa (np. Skrypt powłoki); w tym przypadku twój wynik to całkowity rozmiar kodu we wszystkich używanych językach.
  • Generowanie kluczy Diffie Hellman może wykorzystywać zapisane na stałe wartości „p” i „g”.
  • Wygenerowany klucz współdzielony musi mieć co najmniej 1024 bity.
  • Po udostępnieniu klucza wybór szyfrowania symetrycznego zależy od Ciebie, ale nie możesz wybrać metody, która jest obecnie znana z praktycznego ataku na nią (np. Zmiana Cezara jest trywialna, aby cofnąć bez znajomości klucza ). Przykładowe dozwolone algorytmy:
    • AES (dowolny rozmiar klucza)
    • RC4 (teoretycznie uszkodzony, ale nie ma żadnych praktycznych ataków, o których mogę wspomnieć, więc jest to dopuszczalne tutaj)
  • Użytkownicy A i B muszą mieć możliwość wzajemnego wysyłania komunikatów (dwukierunkowa komunikacja) (np. Czytanie linii ze standardowego wejścia, ciągłe monitowanie lub zdarzenia, takie jak naciśnięcie przycisku). Jeśli to ułatwi, możesz podjąć na przemian konwersację (tj. Po wysłaniu wiadomości przez użytkownika, musi on poczekać na odpowiedź przed wysłaniem następnej wiadomości)
  • Wbudowane języki dozwolone (nie trzeba pisać własnych metod kryptograficznych lub sieciowych, jeśli są już obsługiwane).
  • Podstawowy format komunikacji zależy od Ciebie.
  • Podane powyżej kroki komunikacji są przykładem, ale nie musisz ich przestrzegać (o ile niezbędne informacje są udostępniane i żaden środkowy człowiek nie jest w stanie obliczyć wspólnego klucza lub wiadomości)
  • Jeśli szczegóły potrzebne do połączenia z serwerem nie są znane z góry (np. Jeśli nasłuchuje na losowym porcie), dane te muszą zostać wydrukowane. Możesz założyć, że adres IP urządzenia jest znany.
  • Obsługa błędów (np. Nieprawidłowe adresy, utracone połączenia itp.) Nie jest wymagana.
  • Wyzwaniem jest kod golfowy, więc wygrywa najkrótszy kod w bajtach.
Dave
źródło
Czy kodowanie jest dozwolone pi gdozwolone?
Tylko ASCII,
@ Tylko ASCII z tego, co mogę powiedzieć, kodowanie dobrej jakości wartości p & g jest uważane za dobre (chyba że twórca złośliwie wykorzystuje wartości, o których wiadomo, że są podatne na określone ataki). Tak więc w przypadku tego wyzwania jest OK (o ile tajemnica wynikowa ma co najmniej 1024 bity)
Dave

Odpowiedzi:

3

Node.js ( 372 423 + 94 = 517 513 bajtów)

Grał w golfa

Dodano podział linii dla „czytelności”.

chat.js ( 423 419 bajtów)

Brak podziałów linii

[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))})})

Podziały wierszy

[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 bajty)

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

Nie golfił

Węzeł ma wbudowane funkcje sieciowe i kryptograficzne. Używa TCP do sieci (ponieważ jest prostszy niż interfejs Node dla HTTP i ładnie gra ze strumieniami).

Używam szyfru strumieniowego (RC4) zamiast AES, aby uniknąć konieczności radzenia sobie z rozmiarami bloków. Wikipedia wydaje się sądzić, że może być podatna na ataki, więc jeśli ktoś ma wgląd w preferowane szyfry, byłoby świetnie.

Uruchom serwer echa, node echo_server.jsktóry nasłuchuje na porcie 9. Uruchom dwie instancje tego programu za pomocą node chat.js <server IP>inode chat.js <server IP> 1 (ostatni argument po prostu ustawia, który z nich wysyła pierwszą). Każda instancja łączy się z serwerem echa. Pierwsza wiadomość obsługuje generowanie klucza, a kolejne wiadomości korzystają z szyfru strumieniowego.

Serwer echa po prostu wysyła wszystko z powrotem do wszystkich podłączonych klientów oprócz oryginalnego.

Klient

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
        }
    });
})

Serwer Echo

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

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

Dzięki Dave za wszystkie wskazówki + opinie!

użytkownik3080953
źródło
1
Nie dodawaj czytelności do wersji golfowej, po to jest wersja bez golfa. Jeśli to zrobisz, usuń średniki przed przerwaniem linii, aby miała tę samą długość.
mbomb007 20.04.17
@ mbomb007 „czytelność” ma przede wszystkim na celu uniknięcie konieczności przewijania. niestety treść kodu nie ma średników, więc to nie działa. Uznałem, że szybkie znalezienie i zamiana nie byłoby zbyt uciążliwe. z pewnością pamięta jednak o twoich wskazówkach dotyczących przyszłych komentarzy!
user3080953
@Dave dziękuję za wszystkie opinie! Wprowadziłem zmiany, aby użyć waniliowej DH, która faktycznie dodała całkiem sporo długości, ponieważ musisz również wymienić liczby pierwsze, AES faktycznie działa jako zamiennik drop-in, ale problem z AES polega na tym, że nic nie wysyła, dopóki nie zakończysz blok, a wyściółka byłaby bólem. także rc4 jest krótszy niż aes128
user3080953
1
Nie byłem pewien, czy to zadziała przez sieć, ale prawdopodobnie nie zadziała, i napisałem to w autobusie, więc nie miałem możliwości sprawdzenia. nowa wersja używa zamiast tego serwera echa. To także rozwiązuje problem przekroczenia limitu czasu. Próbowałem ominąć serwer + klient, ale jest to o wiele lepsza forma. W końcu, dzięki za to wyzwanie, dowiedziałem się tony o tym, jak właściwie korzystać z węzła zamiast bibliotek po prostu chwytając zewsząd :)
user3080953
@ user3080953 brzmi dobrze. Dzięki tym aktualizacjom powinieneś ubiegać się o nagrodę!
Dave
0

Node.js, 638 607 bajtów

Teraz, gdy został dobrze pokonany (w tym samym języku), oto moja testowa odpowiedź:

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])

Lub z opakowaniem:

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])

Stosowanie

Jest to implementacja serwer / klient; jedna instancja będzie serwerem, a druga klientem. Serwer jest uruchamiany z określonym portem, a następnie klient jest wskazywany na port serwera. Konfiguracja może potrwać kilka sekund, jeśli w urządzeniu brakuje entropii, więc pierwsze wiadomości mogą być nieco opóźnione.

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

Awaria

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

Jedynym wymaganiem dla tokenów jest to, aby zawierały one co najmniej jeden znak niebędący heksadecymem, dlatego w skróconym kodzie używane są inne stałe ciągów (data i hex).

Dave
źródło