MpOTR/algorithm dump

Revision as of 21:30, 23 July 2014 by Vmon (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Example of an Algorithm in Wiki

Procedure LargestNumber
  Input: A list of numbers L.
  Output: The largest number in the list L.
  largest ← null
  for each item in "L"', do
    if item > largest, then
      largestitem
  return largest

mpOTR algorithms

Chatroom setup

Procedure Chat Initiator Init
Input: newRoomName, participantNick
  Global myId := 1
  Global Nick_{myId} := participantNick
  Global roomName := newRoomName
  Global x_{myId}, y_{myId} := Call 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
  Call Verify Verifiers()
  Global sessionKey := SHA-512(x_{myId}y_{other}, sessionId)
  toBeSigned := SHA-512(SHA-512(sessionId||SHA-512(y_1, v_1)||SHA-512(y_2,v_2)))
  Call Sign Session and Send(toBeSigned)



Join

Procedure Join
Input: newRoomName, Nickname_{myId
  Global myId := participantId
  Global roomName := newRoomName
  x_{myId}, y_{myId} := Call Generate Initial Paramters(Participant ID myId)
  Global signatureKey_{myId} := (x_{myId},y_{myId})
  Call Broadcast(``:3mpCat:3Join:3, myId, Nickname_{myId)
  Global participantList, ephemeralPublicPointList := Call Receive()
  Global sessionId :=  Call Compute Session Id(roomName, participantList, ephemeralPublicPointList)
  Call Sign and Send Key Confirmation and Shares()
  Call Wait On Receive(``:3mpCat:3KeyConfirmationShare:3)
  Global keyShareList, keyConfirmationList, signatureList := Call Receive()
  Call Verify Key Confirmations and Signatures(keyConfirmationList, signatureList)
  Call 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
  Call Broadcast(``:3mpCat:3Join:3, myId, Nickname_{myId)
  Call Wait On Receive(``:3mpCat:3Join:3)
  Global nick_{NewParticipant}, ephemeralPublicPoint_{NewParticipant} :=  Call Receive()
  Call Update Lists(nick_{NewParticipant)
  Global sessionId :=  Call Compute Session Id(roomName, participantList, ephemeralPublicPointList)
  Call Sign and Send Key Confirmation and Shares()
  Call Wait On Receive(``:3mpCat:3KeyConfirmationShare:3)
  Global keyShareList, keyConfirmationList, signatureList := Call Receive()
  Call Verify Key Confirmations and Signatures(keyConfirmationList, signatureList)
  Call Update Session Key()
  Call Send(sessionDigest)


Farewell

Procedure Shrink on Leave
Input: leaverId
  Remove leaverId from participantIdList
  Global sessionId := Call Compute Session Id()
 \If{|participantList| > 1}
  Call Sign and Send Key Shares()
  Call Wait On Receive(``:3mpCat:3KeyShare:3)
  keyShareList := Receive{}
  Call Update Session Key(keyShareList)


Procedure Sign and Send Key Shares
Input: 
  Global z_{myId -1, myId} := SHA-512(k_{myId,myId-1}, sessionId)
  Global z_{myId, myId+1} := SHA-512(k_{myId,myId+1}, sessionId)
  keyShare_{myId} := z_{myId -1, myId} \oplus z_{myId, myId+1}
  originAuthSignature := Call ED25519Sign(SignatureKey, sessionId || z_{myId)
  Call Broadcast(``:3mpCat:3KeyShare:3, myId, keyShare_{myId)


Send

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


Recieve

Procedure Receive
Input: sender, encryptedMessage, originAuthSignature, sessionDigest
v :=  Call ED25519VerifySignature(ephemeralPublicKeyList[Sender], sessionId || encryptedMessage, originAuthSignature)
Call Assert(v)
message, keyShareMessage := Call AES CTR Decrypt(sessionKey, encryptedMessage)
isMetaMessage = Call UpdateNewKeyStatus(keyShareMessage)
Call Verify Digests(sessionDiges)
Return{isMetaMessage, message}


\subsection{Common functions}


Common functions used by other procedures in different stages

Procedure Generate Initial Paramters
Input: myId
  signaturePrivateKey :=  Call RandomBits(256)
  x_{myId} := Call Ed25519 Scalar(signaturePrivateKey))
  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 SHA-512(k_{myId,participant}, U_{myId})}
      Call Halt()
     ' \If{Call ED25519VerifySignature(ephemeralPublicKeyList[particicpant], sessionId ||keyShares[myId], originAuthSignature)'
      Call Halt()


Procedure Compute Session Id
Input: participantList, ephemeralPublicPointList
  Return SHA-512(roomeName, zip(participantList, ephemeralPublicPointList)) # zip([a,b],[c,d]):=[(a,c),(b,d)]


Procedure Verify Signatures
Input: longPublicList,schnorrRandomPointList, 


Procedure Sign and Send Key Confirmation and Share
Input: schnorrRandomPointList
For each participant \in participantList, do
    k_{myId, participant} := H(g^{lp_{myId}}LP_{participant}y_{participant}^{x_{myId}}) # Triple DH
    kc_{myId} := kc_{myId} | H(k_{myId,participant}, U_{participant})


  Global z_{myId -1, myId} := SHA-512(k_{myId,myId-1}, sessionId)
  Global z_{myId, myId+1} := SHA-512(k_{myId,myId+1}, sessionId)
  keyShare_{myId} := z_{myId -1, myId} \oplus z_{myId, myId+1}


    originAuthSignature := Call ED25519Sign(SignatureKey, sessionId || z_{myId)
  Call Broadcast(``:3mpCat:3KeyConfirmationAndShare:3, myId, keyShare_{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 := SHA-512(z_{j,j+1} | j \in [1...n])


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


Procedure ComputeSessionDigest
Input: lastMessage

For each message in Messages Received from lastDigestedMessage+1 till lastMessage}, do

sesionDigest := Call SHA-512(sessionDigest, message)
Call LRU Cache Store Digest(sessionDigest, message)
Return sessionDigest,lastMessageId