galaxy_crypto.txt

(C) 2016 Antinet.org Team

All this text is copyrighted as part of Antinet project (e.g.:GPLv3, but see Antinet project licence).



!!! This is a draft. It can contain still mistakes, ERRORS, and will likelly be changed in future. !!!





TODO: This is now partially replaced, check the implementation crypto.?pp for details.



=== Summary of available crypto systems ===
Intro: General summary of crypto available that we COULD use:

Things Vulnerable to QC are marked as <vulnQC>.
Things thought to be resistant to QC are marked as <resistant>.
Hash and SymEncrypt (including SymAuth) are immune to QC.

NTru ---> NTru-Sign PubSign/Chain <resistant>
      '-> NTru-Encr PubEncrypt <resistant>

RSA<vulnQC> (PubSign, PubEncrypt)

EdDSA (PubSign) --------> Ed25519 <vulnQC>
                             ^
                             | because Schnorr
                             v
                  ,---> Curve25519 "X25519" (KeyAgr) <vulnQC>
                  |
DH (KeyAgr) ---> ECDH <vulnQC>
                  |
                  '---> SIDH <resistant> (KeyAgr)

SHA* (Hash)
  |--> Contest NSA ---> SHA-1 --> SHA1
  |
  |--> Contest NSA ---> SHA-2 --> SHA256, SHA512
  |
  '--> Contest NIST ---> Winner ---> Keccak -!-!-> ! SHA-3 (reduced strength?)
               |
               '--> Others ---> Blake <..................
                                                        . blake uses chacha20
                                                        .
                                                        .
AES (SymEncrypt, SymAuth) ~~~~~~> Salsa20 (older) ---> ChaCha20

Hash based crypto ---> Lamport ---> Geport

Poly1305 (HMAC)

BlockChain ------> BC+PoW
   |
   '---> CoinSign

Cjdns (v17) uses:
1) Establish CryptoAuth session - DHDH (X25519 permanent + X25519 ephemeral)
2) Each packet: Poly1305 Salsa20

=== Galaxy42 crypto - overview ===

Galaxy uses following crypto:

For given connection we create a tunnel (for end-to-end session,
and other for peer-to-peer session):

based on session secret K, we symmetrically encrypt and authorize.
More exactly: using Salsa20 and Curve 1305.

This part is very secure against QC and other attacks.
The problem is how to establish K in secure way (next chapter).


=== Galaxy42 crypto - establishing secure session K ===

How to establish the secret K - in a way resistant to QC?
(For comparsion as of 2016-04, Cjdns v17 that uses ECDH X25519 it is NOT resistant to QC attacks).

We use Diffie-Hellman like key exchange & also we use symmetrical crypto;
Both methods protect eachother recursively.
So we use:

DH & SymHash - and more exactly it is:
DHDH & SymHash - and more exactly it is:
ECDH+ECDH & AES+HASH - and more exactly it is:
X25519+X25519 & Salsa20+BLAKE2

But we also use DH-like key exchange with NTru encrypt/sign optionally:

Xchg-Pubkey[NTru-encrypt] and X25519+X25519  &  Salsa20+BLAKE2

These 3 parts can establish 3 shared keys that then are combined into the SK shared key.
If any of them resists attacks, then entire system resisted too.

1. Xchg-Pubkey[NTru-encrypt] - probably resistant to QC.
2. X25519+X25519 - not resistant to QC, but good otherwise.
3. Salsa20+BLAKE2 - resistant to QC by definition, and secure and well tested.

Problem with 3 is that it can not be established between two IPv6 directly as it requires exchange of
another password over secure channel first.
If ANY of previous session was not broken by attacker, e.g. was not monitored by attacker,
then we are safe - since in each we exchange and add the symmetrical
passwords (we keep hashed state known as Historical Password).
We offer 3 solutions:
1. Not observed - we can hope attacker did not archived ALL of Alice conversations to given Bob.
2. Manual - Alice and Bob could at some point meet to protect future transmissions.
3. Not broken - if either DH or NTru holds then after such exchange transmissions are safe.
This is interesting in case if NTru will turn out to be sometimes breakable and sometimes not, based on
today yet unknown mathematical property of given key.

--- Xchg-Pubkey ---

Is a secret key agreement protocol between parties that know each-other public key already,
using assymetrical crypto.

Alice has pubkey PubA ( == the virtual IP)
Bob has pubkey PubB ( == the virtual IP)
Alice ra=random(), encrypts ra to PubB, sends to Bob.
Bob   rb=random(), encrypts rb to PubA, sends to Alice.
Alice: SK = ra xor rb
Bob:   SK = ra xor rb
 or instead (maybe better):
SK = H( H(ra) xor H(rb) xor H(ra xor rb) ) // todo? does it decrease chance of...
// ...other  side to in any way predict anything about SK?

Xchg-Pubkey[NTru-encrypt] is above, using NTru Encrypt as the assymetrical encryption.

=== Galaxy42 crypto - loading the main key ===

We need main key(s).
For example (as in Cjdns v17) a permanent X25519 key.
We call that key the runtime key (e.g. runtime DH = runtime X25519 key).

But we also use other stages of the key - see in chapter "Key levels".

=== Galaxy42 crypto - key levels ===

Alice's vault --- (for PubSign) key Vault - offline computer, saved on disk
Alice's issuer --- (for PubSign) key Issuer - other computer (e.g. offline), saved on disk
Alice's installation --- (for PubSign) key Program - this computer, disk, and this process on startup ONLY!
Alice's program runs --- (for *DH) key Runtime - memory only (same for all users), generated on startup
CA session (to Bob) --- (for *DH) key Temporary/ephemeral - memory only (generated for each user / CA reset)

For each session the program generates temporary/ephemeral key;
And authenticates it by encrypting temporary key to some shared key password1 (and optionaly some
confirmation string like a constant or maybe Poly1305)
and this password1 was agreed upon by exchange X25519 between Alice (and Bob's) runtime key.

The runtime key is again confirmed, by being signed (PubKey sign this time, e.g. with Ed25519),
by the installation key.

Installation key can be optionally signed by issuer key.
Issuer key can be optionally signed by vault key.

The IPv6 hash is create by the highest key: that is by vault key if it exists, else by issuer, else by installation.

Above steps allow to regain controll of IPv6 address after e.g. entire program runtime memory was compromised [Instalation
recovers that],
or when entire installation machine (e.g. a server) was compromised [then Issuer fixes that],
or even when Issuer was compromised (the Vault).

Keys have validity periods, and define the time for the key they sign.

Example:

Vault key 0x99998888 (valid forever) is created;  It's hash defines the IPv6 e.g. fd42cafe4242
Issuer generates key 0x7777.
Vault signs: "key 0x7777 is valid since 2016-01-01 for 744 hours".
Install generates key 0x5555.
Issuer signs: "key 0x5555 is valid since 2016-01-01 for 50 hours".

When program starts, it generates and hold in memory a runtime key 0x4444.


Example:


           SK for ChaCha20 + Poly1305
           ^
           |
         / | \
        /  |  \
SK-Ntru  SN-DHDH  SK-SymHash


For each: K-Ntru, K-DHDH - we load them by delegated steps:


SK-*-Alice-tmp, is generated, and then encrypted with SK-*-Alice-runtime.
Therefore key "runtime" is what we called "permanent" in "DHDH" (DH plus ephemeral; DH PFS)

        SK-*-tmp for example SK-DHDH this is the temporary (ephemeral) key
        ^
        |
     ENCRYPT(+auth by adding constant string) <---- encrypt to password1
        |                         |
  generate_X25519()               |
                                  | from DH exchange with pubkey
                                  |
                         DH to pubkey SK-*-runtime
                                  ^
                                  |
                           generate_X25519() on program startup
                                  ^
                                  |
Sign that key with                |
the 25519 "Installation" ------ PubSign { crypto_scalarmult_base ? }
Key form disk.
     ^
     |
  PubSign <---- signed by Issuer Key
                              ^
                              |
                          signed by Vault key



=== Galaxy42 crypto - all ===

All together, the big picture.

Shortcut names for crypto systems used below:

X     = X25519 (type of ECC) pubkey for key agreement.
E     = Ed25519 (type of ECC) pubkey for pubsig.
NT    = NTru (lattice-based, likely QC resistant) pubkey (for sign and for encry).
Ge    = Geport (Lamport variant, almost certainly QC resistant) pubsig. Includes the tree of signatures as needed.

Mode name    | IPv6        | Vault | Issuer | Install | Runtime  | ephemeral | Packet(SK)
-------------|-------------+-------+--------+---------+----------+-----------|---------
Cjdns        |Hash1(X)     |       |        | X       | =install | X         | Curve1305+Salsa20
Galaxy turbo |Hash2(Vault) | E+NT  |        | X       | =install | X         | Curve1305+ChaCha20
Galaxy fast  |Hash2(Vault) | E+NT  | E+NT   | E+NT    | X+NT     | X+NT      | Curve1305+ChaCha20
Galaxy bank  |Hash2(Vault) |E+NT+Ge|E+NT+Ge | E+NT    | X+NT     | X+NT      | Curve1305+ChaCha20

Hash1(m) = truncate_to(512, SHA512(SHA512(m)))
Hash2(m) could be = Hash1(m) or else:
<<optional>> Hash2(m) = compress4( SHA3x(SHA3x(SHA3x( m ))) )

Compress4 generates an (n/4)-bit output "y" from n-bit input "x", as: y[i/4] = x[i] ^ x[i+1] ^ x[i+2] ^ x[i+3]

--- Full example ---


On example of most advanced crypto.


Generate our own IP:
  generate keypair Ed25519
  generate keypair NTru
  generate keypair Geport<Blake2>
  (generate SIDH once that system becomes usable)
  Extra meta-data like e.g. our Bitcoin address that we want to publish, PGP key etc.
Hash above data:
  Concatenate above data, plus a nonce, and calculate hash2 of it.
  Repeat untill we hit proper hash (considering IP-hashing-type bits) and allowed IP ranges.
Save all data to disk (and backups!) on the Vault computer.

Generate certs on Issuer:
  generate keypair Ed25519
  generate keypair NTru
  generate keypair Geport<Blake2>
  (generate SIDH once that system becomes usable)
  Agreement meta-data:
  - from what date, for how long, we want to be valid
  - from what date, for how long, we will allow our child agreement to be valid if we sign it later.
Generate document with above data, and get it's hash.
Save all data to disk (and backups!) on the Issuer computer.

Vault computer signs the above Issuer *hash* (this is equall to signing the document), 
and generates a detached signature data "vault-signs-issuer".
The signature is just a set of signatures on that *hash* as made by each public key:
  - hash of Issuer document - signed by Vault NTru
  - hash of Issuer document - signed by Vault Ed25519
  - hash of Issuer document - signed by Vault Geport<Blake2>
This signatures are moved to Install.

Install the program on the server (Install keys).
  generate keypair Ed25519
  generate keypair NTru
  (generate SIDH once that system becomes usable)
  - from what date, for how long, we want to be valid
  - from what date, for how long, we will allow our child agreement to be valid if we sign it later.
Generate document, hash, and save - as in previous steps.

Issuer signs the above - as in previous steps:
  - hash of Install document - signed by Issuer Ed25519
  - hash of Install document - signed by Issuer NTru
  - hash of Install document - signed by Issuer Geport<Blake2>
Detached signature (as in previous steps) is delivered to Install.

Runtime: the program starts up, and generates keys on start:
(This is "Alice". This is the permanent key in Cjdns v17 system/naming)
  generate keypair X25519
  generate keypair NTru
this program signs above data (hash of them) by using the Install keys:
  - hash of runtime keys is signed by Install key Ed25519
  - hash of runtime keys is signed by Install key NTru
NOW we SHOULD - delete from MEMORY the Install keys.
Now we have in memory of program only: the Runtime keys. Install keys are removed (only on disk),
and Issuer and Value keys are safe elsewhere (even if this program would be fully exploited).

--- FOR EACH connection when some "Bob" connect ---

Get Bob's Runtime keys.

For each given Bob (session of cryptoauth)
we generate new:
  - generate Ephemeral X25519 keypair (on a fast random generator)
  - generate Ephemeral NTru keypair   (on a fast random generator)
  - generate Ephemeral r1 random
Exchange this data in authorized (and encrypted) way as following:
Generate message M with above data.
Use Alice.Runtime.X25519 key to agree with Bob.Runtime.X25519 on shared key X1 (it is Ephemeral)
(as done in standard D-H key agreement protocol)
Encrypt M with X1 into cyphertext C1.
Encrypt C1 into publickey Bob.Runtime.Tru into C2.
(Encrypt C2 into publickey Bob.Runtime.SIDH into C3 when SIDH is available)
CFA is the finall C... from Assymetric crypto: e.g. C2 now.
Encrypt CFA with KH (Key Historical) into CFS (Crypto Finall Symetrical).

Give the CFS to Bob.
Bob decrypts it and gets:
  - has Alice.Ephemeral.X25519 pubkey
  - has Alice.Ephemeral.NTru pubkey
  - has Alice.Ephemeral.rand value

<<<signature chain>>> TODO

Bob finished key agreement between our Alice.Ephemeral.X25519 (read from CFS)
and his Bob ===> this establishes shared secret SK_DHDH.

Bob generates SK_NTru_bob. And encrypts that into SK_NTru_bob_c for our pubkey Alice.Ephemeral.NTru.
And sends to Alice.
Alice will decrypt, so she has SK_NTru_bob.


SK_NTru = H(SK_NTru_bob) xor H(SK_NTru_alice) xor H(r1) xor H(r2)

SK_SH = H( our history state same for both sides )

SK = SK_NTru xor SK_DHDH xor SK_SH.

Now the SK can be used for symmetrical crypto auth.




--- Q&A ---

Q: Why not just use Runtime key instead of Ephemeral key?
A: It can not regenerate because we want to remove and never again load the Install keys in the runtime of our program
so that code injected into us in runtime (by exploit) has no way to get controll of Install keys and will lose ability
to inpersonate us etc after a rester.
In addition Runtime key is same for all "Bobs" sessions while Ephemeral is different for each session (increasing PFS strength
against memory leaks).




=== IP-hashing-type ===

<< optional ? >>

IP type 0: IPv6 is hash sha512 of: (DH master key)
IP type 1: IPv6 is hash ...... of: (DH master key) and (NTru master key - used for encryption)
IP type 2: IPv6 is hash ...... of: Lamport master root key. It will sign: DH master key, NTru master key
and will allow to in future change to other algorithms (tree of Lamport signatures).
IP type 3: is reserved for future use.

IPv6 type is encoded in the IPv6 bit number 60 and 61.
The IPv6 of given type is generated by rules of given type untill the bits 60 and 61 happen to correctly
encode the desired IP type, e.g. will be "01" for IP type 1.


=== Details ===

<<< this contains typos >>>

DH-DH exchange:


On ID creation:
Ali: ap,AP = Generte_DH // make permanent keys: ap = Ali_DH_Perm_priv , AT = Ali_DH_Perm_Pub

On ID creation:
Bob: bp,BP = Generte_DH // same for Bob



On CA establishing from Alice to Bob:
Alice:
  at,AT = Generte_DH() // make temporary keys: at = Ali_DH_Tmp_priv , AT = Ali_DH_Tmp_Pub
  r1 = credentials_given_by_b || ';' || secure_random
  mt = "AT,r1"; // message with temporary key and temporary random

  KP = complete_DH( ap , BP ) , () // prepare permanent-key based AuthEncr
  uap=secure_random() ; ua = uap || encrypt_symm( KP , uap || mt ) // authenticate temp message

Ali -> Bob: "ua" // NETWORK send

Bob:
  decrypts/checks auth: ua
  has AT, r1

  bt,BT = Generte_DH() // make temporary keys: at = Ali_DH_Tmp_priv , AT = Ali_DH_Tmp_Pub
  r2 = secure_random()
  mt = "BT,r2"; // message with temporary key and temporary random

  KP = complete_DH( bp , AP ) , // prepare permanent-key AuthEncr
  ubp=secure_random() ; ub = ubp || encrypt_symm( KP , ubp || mt ) // authenticate temp message
  ... or ub = encrypt_symm( KP , ubp || ubp || mt )
  ... or ub = encrypt_symm( KP , 'all_is_fine' || mt )

Bob -> Alice: "ub" // NETWORK send

Alice:
  decrypts/checks auth: ub
  has BT, r2

Now both sides calculate the same:
  TSK = complete_DH( at , BT) or = complete_DH( bt , AT) // Temporary Shared Key
  FSSSK = H( H( TSK ) || H( r1 ) || H( r2 ) ) // Forward-Secrecy Session Shared Key
  nonce=1



*** r1,r2 helps when:
attack hardness: badluck-DH << DH-tmp , DH-perm


***
break: bp - bob permanent privkey
impersonate bob: BT' <-- attackers key


=== TODO ===


--- Curve25519 exceptions ---
Q: Is this relevant to any use?

How do I validate Curve25519 public keys? [ https://cr.yp.to/ecdh.html ]
"
Don't. The Curve25519 function was carefully designed to allow all 32-byte strings as Diffie-Hellman public keys. Relevant lower-level facts: the number of points of this elliptic curve over the base field is 8 times the prime 2^252 + 27742317777372353535851937790883648493; the number of points of the twist is 4 times the prime 2^253 - 55484635554744707071703875581767296995. This is discussed in more detail in the curve25519 paper.

There are some unusual non-Diffie-Hellman elliptic-curve protocols that need to ensure ``contributory'' behavior. In those protocols, you should reject the 32-byte strings that, in little-endian form, represent 0, 1, 325606250916557431795983626356110631294008115727848805560023387167927233504 (which has order 8), 39382357235489614581723060781553021112529911719440698176882885853963445705823 (which also has order 8), 2^255 - 19 - 1, 2^255 - 19, 2^255 - 19 + 1, 2^255 - 19 + 325606250916557431795983626356110631294008115727848805560023387167927233504, 2^255 - 19 + 39382357235489614581723060781553021112529911719440698176882885853963445705823, 2(2^255 - 19) - 1, 2(2^255 - 19), and 2(2^255 - 19) + 1. But these exclusions are unnecessary for Diffie-Hellman.
"






#############################################################################################################
#############################################################################################################
#############################################################################################################
EXAMPLES
#############################################################################################################
#############################################################################################################
#############################################################################################################


#############################################################################################################
IDe is encryted with CTab - re bug#m146

Alice encrypts her IDe with CTab:

MARK* /galaxy42/crypto.cpp:1546 Creating IDe - DONE
======================================================================
note: /galaxy42/crypto.cpp:1029 MAKING packetstart: m_packetstart_kexasym = 610 [0x1,t,0x1,0xFD=253,0x2,\,0xFB=251,I ... 0xD6=214,0xA3=163,l,x]
note: /galaxy42/crypto.cpp:1032 MAKING packetstart: m_packetstart_IDe = 655 [G,M,K,a,o,0x2,e,0x1 ... 0xB4=180,0xEA=234,0xF6=246,0xD8=216]
...
note: /galaxy42/crypto.cpp:1013 Got stream K = 32 [0xE6=230,0xB4=180,0x94=148,',I,0xBB=187,0xF4=244,0x9C=156 ... o,0x1A=26,0xC9=201,0xCC=204]





Bob decrypts that Alice-IDe:

note: /galaxy42/crypto.cpp:1013 Got stream K = 32 [0xE6=230,0xB4=180,0x94=148,',I,0xBB=187,0xF4=244,0x9C=156 ... o,0x1A=26,0xC9=201,0xCC=204]
...
note: /galaxy42/crypto.cpp:1474 Bob? Ok created our IDe - DONE
note: /galaxy42/crypto.cpp:1477 Bob? Ok creating final stream
info: /galaxy42/crypto.cpp:1050 Reading packetstart IDe, encr: 671 [Q,0x8D=141,0x8,v,0x19=25,=,0xC5=197,0x93=147 ... 0x9F=159,^,1,0xB8=184]
info: /galaxy42/crypto.cpp:1051 Reading packetstart IDe, decr: 655 [G,M,K,a,o,0x2,e,0x1 ... 0xB4=180,0xEA=234,0xF6=246,0xD8=216]


Bob encrypts own Bob-IDe:
MARK* /galaxy42/crypto.cpp:1489 Bob? created packet starter for CTe...
======================================================================
note: /galaxy42/crypto.cpp:1491 Bob? Creating the crypto tunnel (we are respondent) - DONE
note: /galaxy42/crypto.cpp:1029 MAKING packetstart: m_packetstart_kexasym = 610 [0x1,t,0x1,0xFD=253,0x2,\,),0xE6=230 ... [,l,0xAB=171,0x88=136]
note: /galaxy42/crypto.cpp:1032 MAKING packetstart: m_packetstart_IDe = 655 [G,M,K,a,o,0x2,e,0x1 ... 0xBD=189,S,0xEE=238,0xC0=192]


Alice gets it and decrypts the Bob-IDe:

info: /galaxy42/crypto.cpp:1497 Alice? Creating CTf from packetstart=1287 [0xFD=253,0x2,b,0x1,t,0x1,0xFD=253,0x2 ... j,0xD4=212,0x1C=28,Z]
info: /galaxy42/crypto.cpp:1050 Reading packetstart IDe, encr: 671 [M,!,0x9F=159,0xBF=191,i,0x13=19,0x10=16,2 ... j,0xD4=212,0x1C=28,Z]
info: /galaxy42/crypto.cpp:1051 Reading packetstart IDe, decr: 655 [G,M,K,a,o,0x2,e,0x1 ... 0xBD=189,S,0xEE=238,0xC0=192]
...
note: /galaxy42/crypto.cpp:1013 Got stream K = 32 [0xE5=229,0xC0=192,0xE6=230,0xAF=175,0x1D=29,0xF6=246,0x81=129,0xC3=195 ... .,d,i,0xF5=245]


#############################################################################################################