MpOTR/algorithm dump

Revision as of 20:38, 28 July 2014 by Vmon (Talk | contribs)

Chatroom setup

Procedure Chatroom Init
Input: newRoomName, participantNick
  global myId:=1
  global Nick_{{myId}}:=participantNick
  global roomName:=newRoomName
  global x_{{myId}},y_{{myId}}:= Generate Initial Paramters(myId)
  global signatureKey_{{myId}}:=(x_{{myId}},y_{{myId}})
  participantList:=[Nick_{{myId}}]
  ephemeralPublicPointList:=[y_{{myId}},y_{{other}}]


Procedure Verify Verifier Generate Init Key
Input: schnorrRandomPoint_{{other}}, Hv_{{other}}, v_{{other}}, y_{{other}}, Nick_{{other}}
  Verify Verifiers()
  global sessionKey:=Hash(x_{{myId}}y_{{other}},sessionId)
  toBeSigned:=Hash(Hash(sessionId||Hash(y_{1},v_{1})||Hash(y_{2},v_{2})))
  Sign Session and Send(toBeSigned)

Join

Procedure Join
Input: newRoomName, Nickname_{{myId}}, participantId
  global myId:=participantId
  global roomName:=newRoomName
  x_{{myId}},y_{{myId}}:=Generate Initial Paramters(myId)
  global signatureKey_{{myId}}:=(x_{{myId}},y_{{myId}})
  Broadcast(":3mpCat:3Join:3", myId, Nickname_{{myId}}, y_{{myId}})
  global participantList,ephemeralPublicPointList:= Receive()
  global sessionId:= Compute Session Id(roomName, participantList, ephemeralPublicPointList)
  Sign and Send Key Confirmation and Shares()
  Wait On Receive(":3mpCat:3KeyConfirmationShare:3")
  global keyShareList,keyConfirmationList,signatureList:= Receive()
  Verify Key Confirmations and Signatures(keyConfirmationList, signatureList)
  Update Session Key()


Procedure Receive Session Digest
Input: currentSessionHistoryDigest
  global sessionDigest:=currentSessionHistoryDigest

Protocol for other participants already in the chat to accept the newcomer

Procedure Accept
Input: newParticipant
  Broadcast(":3mpCat:3Join:3", myId, Nickname_{{myId}}, y_{{myId}})
  Wait On Receive(":3mpCat:3Join:3")
  global nick_{{NewParticipant}}, ephemeralPublicPoint_{{NewParticipant}}:= Receive()
  Update Lists(nick_{{NewParticipant}}, ephemeralPublicPoint_{{NewParticipant}})
  global sessionId:= Compute Session Id(roomName, participantList, ephemeralPublicPointList)
  Sign and Send Key Confirmation and Shares()
  Wait On Receive(":3mpCat:3KeyConfirmationShare:3")
  global keyShareList,keyConfirmationList,signatureList:= Receive()
  Verify Key Confirmations and Signatures(keyConfirmationList, signatureList)
  Update Session Key()
  Send(sessionDigest)


Farewell

Procedure Shrink on Leave
Input: leaverId
  remove leaverId from participantIdList
  global sessionId:= Compute Session Id()
  if |participantList|>1, then
    Sign and Send Key Shares()
    Wait On Receive(":3mpCat:3KeyShare:3")
    keyShareList := Receive()
    Update Session Key(keyShareList)


Procedure Sign and Send Key Shares
Input: 
  global z_{{myId-1,myId}}:=Hash(k_{{myId,myId-1}},sessionId)
  global z_{{myId,myId+1}}:=Hash(k_{{myId,myId+1}},sessionId)
  keyShare_{{myId}}:=z_{{myId-1,myId}}\oplus z_{{myId,myId+1}}
  originAuthSignature:= ED25519Sign(SignatureKey, sessionId || z_{{myId}})
  Broadcast(":3mpCat:3KeyShare:3", myId, keyShare_{{myId}}, originAuthSignature)  # we can send this encrypted but leaving person can read it, hence theoretically it is the same as sending it unencrypted.

Send

Procedure Send
Input: metaMessage, message
  keyShareMessage = NewKeyShareMessage(metaMessage)
  cryptMessage := AES CTR Encrypt(sessionKey,message|keyShareMessage)
  originAuthSignature := ED25519Sign(SignatureKey, sessionId || cryptMetatMessage)
  sessionDigest := Compute Session Digest(lastMessage)
  Broadcast(":3mpCat:3", sessionId, cryptMessage, sessionDigest, originAuthSignature,":3")

Recieve

Procedure Receive
Input: sender, encryptedMessage, originAuthSignature, sessionDigest
  v:= ED25519VerifySignature(ephemeralPublicKeyList[Sender], sessionId||encryptedMessage, originAuthSignature)
  Assert(v) or return Reject
  message,keyShareMessage:= AES CTR Decrypt(sessionKey, encryptedMessage){}
  isMetaMessage=UpdateNewKeyStatus(keyShareMessage)
  Verify Digests(sessionDiges)
  return{isMetaMessage,message}  # isMetaMessage is true if the message is purely meta message and there is nothing to display

Common functions used by other procedures in different stages

Procedure Generate Initial Paramters
Input: myId
  signaturePrivateKey:= RandomBits(256)
  x_{{myId}}:= Ed25519 Scalar(signaturePrivateKey)) #{This is both Diffie-Hellman secret and ephemeral signature private key}
  y_{{myId}}:=x_{{myId}}P
  return x,y


Procedure Verify Key Confirmation and Signatures
Input: signatureList, keyConfirmationList
  for each participant\in participantList, do
    if keyConfirmationList[participant][myId]\neq Hash(k_{{myId,participant}},U_{{myId}}), then
      Halt()
    else if ED25519VerifySignature(ephemeralPublicKeyList[particicpant], sessionId|keyShares[myId], originAuthSignature) = Fail , then
      Halt()


Procedure Compute Session Id
Input: participantList, ephemeralPublicPointList
  return Hash(roomeName,zip(participantList,ephemeralPublicPointList))  # zip([a,b],[c,d]):=[(a,c),(b,d)]


Procedure Verify Signatures
Input: longPublicList,schnorrRandomPointList, 
# standard signature verification
Procedure Sign and Send Key Confirmation and Share
Input: schnorrRandomPointList
  for each participant\in participantList, do
    k_{{myId,participant}}:=Hash(x_{{myId}}LP_{{participant}}|lp_{{myId}}y_{{participant}}|x_{{myId}}y_{{participant}})  # Triple DH
    kc_{{myId}}:=kc_{{myId}}|Hash(k_{{myId,participant}},U_{{participant}})
  global z_{{myId-1,myId}}:=Hash(k_{{myId,myId-1}},sessionId)
  global z_{{myId,myId+1}}:=Hash(k_{{myId,myId+1}},sessionId)
  keyShare_{{myId}}:=z_{{myId-1,myId}}\oplus z_{{myId,myId+1}}
  originAuthSignature:= ED25519Sign(SignatureKey, sessionId || z_{{myId}})
  Broadcast(":3mpCat:3KeyConfirmationAndShare:3", myId, keyShare_{{myId}}, originAuthSignature, kc_{{myId}})


Procedure Update Session Key
Input: keyShareList
   i:=myId
  for each {j\in [i,...,i+n-1]}, do
     z_{{j,j+1}}:=z_{{j-1,j}}\oplus keyShareListe[j+1]
    # recovered z_{{i-1,i}} should be equal to its original value
   global sessionKey:=Hash(z_{{j,j+1}}|j\in [1...n])


Procedure Sign Params Update Session Key
Input: toBeSigned, signatureList,keyShareList
  Update Session Key()
  toBeSigned:=Hash(sessionId,||Hash(verifierList,ephemeralPublicPointList,keyShareList)))
  signature_{{myId}}:=Sign Session and Send(toBeSigned)
  Broadcast(":3mpCat:3SignedSessionParameters:3",signature_{{myId}})


Procedure ComputeSessionDigest
Input: lastMessage
  for each message in Messages Received from lastDigestedMessage+1 till lastMessage, do
     sesionDigest:=Hass(sessionDigest,message) 
     LRU Cache Store Digest(sessionDigest, message)
  return sessionDigest,lastMessageId


Procedure NewKeyShareMessage
Input: metaMessage
# Based on metaMessage Determines what type of keyshare needs to be send (Ephemeral point or Group key share) and returen it.


Procedure UpdateNewKeyStatus
Input: keyShareMessage
# Update the table of which participant has sent its new ephemeral point or its new group key share


Procedure Hash
Input: message
   return SHA-512(message)