Axolotl Erklärt

Wie funktioniert die Crypto hinter Signal und WhatsApp

Max Bruckner (FSMaxB)

Über mich


  • Ich ...
    • bin kein Kryptologe
    • war nicht an der Entwicklung von Axolotl beteiligt

Warum Axolotl?

  PGP OTR Axolotl
Synchron :x:1 :heavy_check_mark: :heavy_check_mark:
Asynchron :heavy_check_mark: :x: :heavy_check_mark:
Forward Secrecy :x: :heavy_check_mark: :heavy_check_mark:
Plausible Deniability :x:2 :heavy_check_mark: :heavy_check_mark:

1: Definitionssache
2: Mit Signatur

Das Protokoll

Each party stores the following values per conversation in persistent

RK         : 32-byte root key which gets updated by DH ratchet
HKs, HKr   : 32-byte header keys (send and recv versions)
NHKs, NHKr : 32-byte next header keys (")
CKs, CKr   : 32-byte chain keys (used for forward-secrecy updating)
DHRs, DHRr : DH or ECDH Ratchet keys
Ns, Nr     : Message numbers (reset to 0 with each new ratchet)
PNs        : Previous message numbers (# of msgs sent under prev ratchet)
ratchet_flag  : True if the party will send a new ratchet key in next msg
skipped_HK_MK : A list of stored message keys and associated header keys for "skipped" messages, i.e. messages that have
                not been received despite the reception of more recent messages.  Entries may be stored with a timestamp,
                and deleted after a certain age.

master_key : shared secret between Alice and Bob
B1         : Bob's initial DH ratchet key

  KDF from master_key: RK, HKs=<none>, HKr, NHKs, NHKr, CKs=<none>, CKr
  DHRs, DHRr = <none>, B1
  Ns, Nr = 0, 0
  PNs = 0
  ratchet_flag = True
  KDF from master_key: RK, HKr=<none>, HKs, NHKr, NHKs, CKr=<none>, CKs
  DHRs, DHRr = B1, <none>
  Ns, Nr = 0, 0
  PNs = 0
  ratchet_flag = False
Sending messages
Local variables:
  MK  : message key

if ratchet_flag:
  DHRs = generateECDH()
  HKs = NHKs
  PNs = Ns
  Ns = 0
  ratchet_flag = False
MK = HMAC-HASH(CKs, "0")
msg = Enc(HKs, Ns || PNs || DHRs) || Enc(MK, plaintext)
Ns = Ns + 1
CKs = HMAC-HASH(CKs, "1")
return msg

Receiving messages
Local variables:
  MK  : message key
  Np  : Purported message number
  PNp : Purported previous message number
  CKp : Purported new chain key
  DHp : Purported new DHr
  RKp : Purported new root key
  NHKp, HKp : Purported new header keys

Helper functions:
  try_skipped_header_and_message_keys() : Attempt to decrypt the message
  with skipped-over message keys (and their associated header keys) from persistent storage.

  stage_skipped_header_and_message_keys() : Given a current header key, a current message number, a future message number,
  and a chain key, calculates and stores all skipped-over message keys (if any) in a staging area where they can later be
  committed, along with their associated header key.  Returns the chain key and message key corresponding to the future
  message number.  If passed a chain key with value <none>, this function does nothing.

  commit_skipped_header_and_message_keys() : Commits any skipped-over
  message keys from the staging area to persistent storage (along with their associated header keys).

if (plaintext = try_skipped_header_and_message_keys()):
  return plaintext

if HKr != <none> and Dec(HKr, header):
  Np = read()
  CKp, MK = stage_skipped_header_and_message_keys(HKr, Nr, Np, CKr)
  if not Dec(MK, ciphertext):
    raise undecryptable
  if ratchet_flag or not Dec(NHKr, header):
    raise undecryptable()
  Np = read()
  PNp = read()
  DHRp = read()
  stage_skipped_header_and_message_keys(HKr, Nr, PNp, CKr)
  HKp = NHKr
  CKp, MK = stage_skipped_header_and_message_keys(HKp, 0, Np, CKp)
  if not Dec(MK, ciphertext):
    raise undecryptable()
  RK = RKp
  HKr = HKp
  NHKr = NHKp
  DHRr = DHRp
  ratchet_flag = True
Nr = Np + 1
CKr = CKp
return read()

* Header encryption may be omitted if the underlying transport is already leaking metadata, and space is at a premium.
  * In that case, the presence of a new ratchet key signals the recipient that the DH ratchet is advancing (instead of
    using encryption by the next header key as the signal).
  * Instead of storing old header keys for skipped messages, old ratchet keys can be used to recognize delayed messages.
* The chain keys could be updated on a time basis as well as a per-message basis.
  * For example: If 24 hours elapse without receiving a message, you might wish to move to the next chain key in case
    there's an intercepted message you're unaware of.




Message Authentication Codes (1)

:woman:     :man:



Message Authentication Codes (2)


Message Authentication Codes (3)


Signaturen (1)

:zipper_mouth::key:, :loudspeaker::key:
SIGN(:page_facing_up:, :zipper_mouth::key:)
VERIFY(:page_facing_up:, :pencil2:, :loudspeaker::key:)

Signaturen (2)


Plausible Deniability

:cop: :chains::woman:

Symmetrische Verschlüsselung

:woman:     :man:









Diffie Hellman

:zipper_mouth::key:, :loudspeaker::key:
:loudspeaker::key:, :zipper_mouth::key:

:woman:: DH(:woman::zipper_mouth::key:, :man::loudspeaker::key:) = :couple::key:
:man:: DH(:man::zipper_mouth::key:, :woman::loudspeaker::key:) = :couple::key:

Forward Secrecy (1)

:page_facing_up:1, :page_facing_up:2
:mag_right::lock:1, :mag_right::lock:2
:page_facing_up:1, :page_facing_up:2

:sunglasses::detective:: :lock:1, :lock:2
:page_facing_up:1, :page_facing_up:2

Forward Secrecy (2)

:page_facing_up:1, :page_facing_up:2
:mag_right::lock:1, :mag_right::lock:2
:page_facing_up:1, :page_facing_up:2

:cry::detective:: :lock:1, :lock:2

Key Derivation

KDF(:key2:, 1)
KDF(:key2:, 2)
:key:1, :key:2
$\nsim$ :key:2



Root Keys

:seedling::key:i, :zipper_mouth::stopwatch::key:, :loudspeaker::stopwatch::key:

KDF(:seedling::key:i|DH(:zipper_mouth::stopwatch::key:, :loudspeaker::stopwatch::key:), 1)


:seedling:1, :woman::zipper_mouth:1, :man::loudspeaker:1→
←:seedling:1, :man::zipper_mouth:1, :woman::loudspeaker:1
:seedling:2, :woman::zipper_mouth:1, :man::loudspeaker:2→
←:seedling:2, :man::zipper_mouth:2, :woman::loudspeaker:1
:seedling:3, :woman::zipper_mouth:2, :man::loudspeaker:2→
←:seedling:3, :man::zipper_mouth:2, :woman::loudspeaker:2

Ratchet (nochmal)


Symmetrische Schlüssel

KDF(:seedling::key:i|DH(:zipper_mouth::stopwatch::key:, :loudspeaker::stopwatch::key:), 1)


Message Chain

KDF(:chains::key:i, 1)
KDF(:chains::key:i, 2)


Ratchet: Rückblick


Verschlüsseln einer Nachricht

:tophat::key:, :speech_balloon::key:
:tophat:: :1234:|:track_previous::1234:|:loudspeaker::stopwatch::key:


:package:: :lock::tophat:|:lock::speech_balloon:

Übersprungene Nachrichten

:woman:: :speech_balloon:1, :speech_balloon:2, :speech_balloon:3, :speech_balloon:4  :man:: :speech_balloon:1  :woman:: :speech_balloon:1

:man:: :inbox_tray:: :speech_balloon:1, :speech_balloon:3 :outbox_tray:::speech_balloon:1 :inbox_tray:: :speech_balloon:1 (:track_previous::1234: = 4)

:man:: :tophat::key:1,:speech_balloon::key:2; :tophat::key:1,:speech_balloon::key:4


Soweit so gut

Das war das Axolotl-Protokoll!

Aber: Es fehlen noch Infos.

Master Key

{:zipper_mouth:,:loudspeaker:}:id::key:; {:zipper_mouth:,:loudspeaker:}:stopwatch::key:
{:zipper_mouth:,:loudspeaker:}:id::key:; {:zipper_mouth:,:loudspeaker:}:stopwatch::key:

:woman:: KDF(
:man:: KDF(
DH(:woman::zipper_mouth::id:, :man::loudspeaker::stopwatch:)|   
DH(:man::zipper_mouth::stopwatch:, :woman::loudspeaker::id:)|   
DH(:woman::zipper_mouth::stopwatch:, :man::loudspeaker::id:)|   
DH(:man::zipper_mouth::id:, :woman::loudspeaker::stopwatch:)|   
DH(:woman::zipper_mouth::stopwatch:, :man::loudspeaker::stopwatch:), 1)
DH(:man::zipper_mouth::stopwatch:, :woman::loudspeaker::stopwatch:), 1)


:man:: :new:{:zipper_mouth:,:loudspeaker:}:stopwatch::key:(1…n)
:cloud:: :man::loudspeaker::stopwatch::key:(1…n)
:woman:: :man:i
:cloud:: :man::loudspeaker::stopwatch::key:(1…n)
:woman:: :man::loudspeaker::stopwatch:i
:cloud:: :man::loudspeaker::stopwatch::key:(1…n)- i)

Signal-Logo WhatsApp-Logo

  • :id::key:: Curve25519
  • :stopwatch::key:: Curve25519
  • :speech_balloon::key:: AES-256 + HMAC-SHA256
  • :tophat::key:: Keiner

Signal-Logo Gruppenchat

  • Jeder mit jedem ⟶ $\binom{N}{2}$ gleichzeitige Verbindungen
  • Gruppennachricht muss N mal verschickt werden

WhatsApp-Logo Gruppenchat

:chains::key:0 → :speech_balloon::key:0
:chains::key:1 → :speech_balloon::key:1

Bei Austritt werden alle Keys neu generiert






  1. Titelfolie
  2. Über mich
  3. Disclaimer
  4. Warum Axolotl?
  5. Protokoll
  6. Hash-Funktion
  7. Message Authentication Codes  (1)  (2)  (3)
  8. Signaturen (1) (2)
  9. Plausible Deniability
  10. Symmetrische Verschlüsselung
  11. Diffie Hellman
  12. Forward Secrecy  (1)  (2)
  13. Key Derivation
  14. Ratchet-Übersicht
  15. Root Keys
  16. Ratchet
  17. Ratchet (Nochmal)
  18. Symmetrische Schlüssel
  19. Message Chain
  20. Ratchet: Rückblick
  21. Verschlüsseln einer Nachricht
  22. Übersprungene Nachrichten
  23. Soweit so gut
  24. Master Key
  25. Prekeys
  26. Signal und WhatsApp
  27. Signal Gruppenchat
  28. WhatsApp Gruppenchat
  29. Quellen
  30. Ende


key:key: closed_lock_with_key:closed_lock_with_key: lock_with_ink_pen:lock_with_ink_pen:
lock:lock: unlock:unlock: key2:key2:
page_facing_up:page_facing_up: page_with_curl:page_with_curl: pencil:pencil:
clipboard:clipboard: cloud:cloud: book:book:
woman:woman: man:man: bust_in_silhouette:bust_in_silhouette:
busts_in_silhouette:busts_in_silhouette: heavy_check_mark:heavy_check_mark: smiling_imp:smiling_imp:
computer:computer: desktop:desktop: electric_plug:electric_plug:
thinking:thinking: detective:detective: closed_book:closed_book:
book:book: paperclip:paperclip: chains:chains:
speech_balloon:speech_balloon: couple:couple: package:package:
loudspeaker:loudspeaker: x:x: zipper_mouth:zipper_mouth:
zap:zap: wastebasket:wastebasket: hourglass_flowing_sand:hourglass_flowing_sand:
mag:mag: mag_right:mag_right: sunglasses:sunglasses:
cry:cry: pencil2:pencil2: tophat:tophat:
1234:1234: stopwatch:stopwatch: track_previous:track_previous:
seedling:seedling: crown:crown: inbox_tray:inbox_tray:
outbox_tray:outbox_tray: new:new: id:id: