Difference between revisions of "MpOTR/algorithm dump"

(Created page with "===Example of an Algorithm in Wiki=== {{algorithm-begin|name=LargestNumber}} Input: A list of numbers ''L''. Output: The largest number in the list ''L''. ''largest'...")
 
(Common functions used by other procedures in different stages)
 
(8 intermediate revisions by the same user not shown)
Line 1: Line 1:
===Example of an Algorithm in Wiki===
 
{{algorithm-begin|name=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'''
 
      ''largest'' ← ''item''
 
  '''return''' ''largest''
 
{{algorithm-end}}
 
 
===mpOTR algorithms===
 
 
====Chatroom setup====
 
====Chatroom setup====
 
<!--alg_chat_setup-->
 
<!--alg_chat_setup-->
{{algorithm-begin|name=Chat Initiator Init}}
+
{{algorithm-begin|name=Chatroom Init}}
  Input: ''newRoomName'', ''participantNick''
+
  Input: <math>newRoomName</math>, <math>participantNick</math>
  Global ''myId := 1''
+
  '''global''' <math>myId := 1</math>
   Global ''Nick_{myId} := participantNick''
+
   '''global''' <math>Nick_{myId} := participantNick</math>
   Global ''roomName := newRoomName''
+
   '''global''' <math>roomName := newRoomName</math>
   Global ''x_{myId}, y_{myId} :='' '''Call''' '''Generate Initial Paramters'''(''myId'')
+
   '''global''' <math>x_{myId}, y_{myId} :=</math> <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Generate Initial Paramters</span>'''(<math>myId</math>)
   Global ''signatureKey_{myId} := (x_{myId},y_{myId})''
+
   '''global''' <math>signatureKey_{myId} := (x_{myId},y_{myId})</math>
   ''participantList := [Nick_{myId}]''
+
   <math>participantList := [Nick_{myId}]</math>
   ''ephemeralPublicPointList := [y_{myId}, y_{other}]''
+
   <math>ephemeralPublicPointList := [y_{myId}, y_{other}]</math>
 
{{algorithm-end}}
 
{{algorithm-end}}
  
  
 
{{algorithm-begin|name=Verify Verifier Generate Init Key}}
 
{{algorithm-begin|name=Verify Verifier Generate Init Key}}
  Input: ''schnorrRandomPoint_{other''
+
  Input: <math>schnorrRandomPoint_{other}</math>, <math>Hv_{other}</math>, <math>v_{other}</math>, <math>y_{other}</math>, <math>Nick_{other}</math>
   '''Call''' '''Verify Verifiers'''()
+
   <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Verify Verifiers</span>'''()
   Global ''sessionKey := SHA-512(x_{myId}y_{other}, sessionId)''
+
   '''global''' <math>sessionKey := Hash(x_{myId}y_{other}, sessionId)</math>
   ''toBeSigned := SHA-512(SHA-512(sessionId||SHA-512(y_1, v_1)||SHA-512(y_2,v_2)))''
+
   <math>toBeSigned := Hash(Hash(sessionId||Hash(y_1, v_1)||Hash(y_2,v_2)))</math>
   '''Call''' '''Sign Session and Send'''(''toBeSigned'')
+
   <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Sign Session and Send</span>'''(<math>toBeSigned</math>)
 
{{algorithm-end}}
 
{{algorithm-end}}
 
 
 
  
 
====Join====
 
====Join====
 
<!--alg_join-->
 
<!--alg_join-->
 
{{algorithm-begin|name=Join}}
 
{{algorithm-begin|name=Join}}
  Input: ''newRoomName'', ''Nickname_{myId''
+
  Input: <math>newRoomName</math>, <math>Nickname_{myId}</math>, <math>participantId</math>
   Global ''myId := participantId''
+
   '''global''' <math>myId := participantId</math>
   Global ''roomName := newRoomName''
+
   '''global''' <math>roomName := newRoomName</math>
   ''x_{myId}, y_{myId} := '''''Call''' '''Generate Initial Paramters'''(Participant ID ''myId'')
+
   <math>x_{myId}, y_{myId} := </math><span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Generate Initial Paramters</span>'''(<math>myId</math>)
  Global ''signatureKey_{myId} := (x_{myId},y_{myId})''
+
  '''global''' <math>signatureKey_{myId} := (x_{myId},y_{myId})</math>
   '''Call''' '''Broadcast'''(``:3mpCat:3Join:3'', ''myId'', ''Nickname_{myId'')
+
   <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Broadcast</span>'''(":3mpCat:3Join:3", <math>myId</math>, <math>Nickname_{myId}</math>, <math>y_{myId}</math>)
   Global ''participantList, ephemeralPublicPointList :='' '''Call''' '''Receive'''()
+
   '''global''' <math>participantList, ephemeralPublicPointList :=</math> <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Receive</span>'''()
   Global ''sessionId := '' '''Call''' '''Compute Session Id'''(''roomName'', ''participantList'', ''ephemeralPublicPointList'')
+
   '''global''' <math>sessionId := </math> <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Compute Session Id</span>'''(<math>roomName</math>, <math>participantList</math>, <math>ephemeralPublicPointList</math>)
   '''Call''' '''Sign and Send Key Confirmation and Shares'''()
+
   <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Sign and Send Key Confirmation and Shares</span>'''()
   '''Call''' '''Wait On Receive'''(``:3mpCat:3KeyConfirmationShare:3'')
+
   <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Wait On Receive</span>'''(":3mpCat:3KeyConfirmationShare:3")
   Global ''keyShareList, keyConfirmationList, signatureList :='' '''Call''' '''Receive'''()
+
   '''global''' <math>keyShareList, keyConfirmationList, signatureList :=</math> <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Receive</span>'''()
   '''Call''' '''Verify Key Confirmations and Signatures'''(''keyConfirmationList'', ''signatureList'')
+
   <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Verify Key Confirmations and Signatures</span>'''(<math>keyConfirmationList</math>, <math>signatureList</math>)
   '''Call''' '''Update Session Key'''()
+
   <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Update Session Key</span>'''()
 
{{algorithm-end}}
 
{{algorithm-end}}
  
  
 
{{algorithm-begin|name=Receive Session Digest}}
 
{{algorithm-begin|name=Receive Session Digest}}
  Input: ''currentSessionHistoryDigest''
+
  Input: <math>currentSessionHistoryDigest</math>
  Global ''sessionDigest := currentSessionHistoryDigest''
+
  '''global''' <math>sessionDigest := currentSessionHistoryDigest</math>
 
{{algorithm-end}}
 
{{algorithm-end}}
  
 +
====Protocol for other participants already in the chat to accept the newcomer====
  
 
 
====Protocol for other participants already in the chat to accept the newcomer====
 
 
<!--alg_accept-->
 
<!--alg_accept-->
 
{{algorithm-begin|name=Accept}}
 
{{algorithm-begin|name=Accept}}
  Input: newParticipant
+
  Input: <math>newParticipant</math>
   '''Call''' '''Broadcast'''(``:3mpCat:3Join:3'', ''myId'', ''Nickname_{myId'')
+
   <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Broadcast</span>'''(":3mpCat:3Join:3", <math>myId</math>, <math>Nickname_{myId}</math>, <math>y_{myId}</math>)
   '''Call''' '''Wait On Receive'''(``:3mpCat:3Join:3'')
+
   <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Wait On Receive</span>'''(":3mpCat:3Join:3")
   Global ''nick_{NewParticipant}'', ''ephemeralPublicPoint_{NewParticipant} := '' '''Call''' '''Receive'''()
+
   '''global''' <math>nick_{NewParticipant}</math>, <math>ephemeralPublicPoint_{NewParticipant} := </math> <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Receive</span>'''()
   '''Call''' '''Update Lists'''(''nick_{NewParticipant'')
+
   <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Update Lists</span>'''(<math>nick_{NewParticipant}</math>, <math>ephemeralPublicPoint_{NewParticipant}</math>)
   Global ''sessionId := '' '''Call''' '''Compute Session Id'''(''roomName'', ''participantList'', ''ephemeralPublicPointList'')
+
   '''global''' <math>sessionId := </math> <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Compute Session Id</span>'''(<math>roomName</math>, <math>participantList</math>, <math>ephemeralPublicPointList</math>)
   '''Call''' '''Sign and Send Key Confirmation and Shares'''()
+
   <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Sign and Send Key Confirmation and Shares</span>'''()
   '''Call''' '''Wait On Receive'''(``:3mpCat:3KeyConfirmationShare:3'')
+
   <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Wait On Receive</span>'''(":3mpCat:3KeyConfirmationShare:3")
   Global ''keyShareList, keyConfirmationList, signatureList :='' '''Call''' '''Receive'''()
+
   '''global''' <math>keyShareList, keyConfirmationList, signatureList :=</math> <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Receive</span>'''()
   '''Call''' '''Verify Key Confirmations and Signatures'''(''keyConfirmationList'', ''signatureList'')
+
   <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Verify Key Confirmations and Signatures</span>'''(<math>keyConfirmationList</math>, <math>signatureList</math>)
   '''Call''' '''Update Session Key'''()
+
   <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Update Session Key</span>'''()
   '''Call''' '''Send'''(''sessionDigest'')
+
   <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Send</span>'''(<math>sessionDigest</math>)
 
{{algorithm-end}}
 
{{algorithm-end}}
  
Line 85: Line 67:
 
<!--alg_farewell-->
 
<!--alg_farewell-->
 
{{algorithm-begin|name=Shrink on Leave}}
 
{{algorithm-begin|name=Shrink on Leave}}
  Input: ''leaverId''
+
  Input: <math>leaverId</math>
   Remove ''leaverId'' from ''participantIdList''
+
   '''remove''' <math>leaverId</math> from <math>participantIdList</math>
   Global ''sessionId :='' '''Call''' '''Compute Session Id'''()
+
   '''global''' <math>sessionId :=</math> <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Compute Session Id</span>'''()
  \If{''|participantList| > 1''}
+
  '''if''' <math>|participantList| > 1</math>''', then'''
  '''Call''' '''Sign and Send Key Shares'''()
+
    <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Sign and Send Key Shares</span>'''()
  '''Call''' '''Wait On Receive'''(``:3mpCat:3KeyShare:3'')
+
    <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Wait On Receive</span>'''(":3mpCat:3KeyShare:3")
  ''keyShareList'' := Receive{}
+
    <math>keyShareList</math> := <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Receive</span>'''()
  '''Call''' '''Update Session Key'''(''keyShareList'')
+
    <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Update Session Key</span>'''(<math>keyShareList</math>)
 
{{algorithm-end}}
 
{{algorithm-end}}
  
Line 98: Line 80:
 
{{algorithm-begin|name=Sign and Send Key Shares}}
 
{{algorithm-begin|name=Sign and Send Key Shares}}
 
  Input:  
 
  Input:  
   Global ''z_{myId -1, myId} := SHA-512(k_{myId,myId-1}, sessionId)''
+
   '''global''' <math>z_{myId -1, myId} := Hash(k_{myId,myId-1}, sessionId)</math>
   Global ''z_{myId, myId+1} := SHA-512(k_{myId,myId+1}, sessionId)''
+
   '''global''' <math>z_{myId, myId+1} := Hash(k_{myId,myId+1}, sessionId)</math>
   ''keyShare_{myId} := z_{myId -1, myId} \oplus z_{myId, myId+1}''
+
   <math>keyShare_{myId} := z_{myId -1, myId} \oplus z_{myId, myId+1}</math>
   ''originAuthSignature :='' '''Call''' '''ED25519Sign'''(''SignatureKey'', ''sessionId'' || ''z_{myId'')
+
   <math>originAuthSignature :=</math> <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''ED25519Sign</span>'''(<math>SignatureKey</math>, <math>sessionId</math> || <math>z_{myId}</math>)
   '''Call''' '''Broadcast'''(``:3mpCat:3KeyShare:3'', ''myId'', ''keyShare_{myId'')
+
   <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Broadcast</span>'''(":3mpCat:3KeyShare:3", <math>myId</math>, <math>keyShare_{myId}</math>, <math>originAuthSignature</math>) # we can send this encrypted but leaving person can read it, hence theoretically it is the same as sending it unencrypted.
 
{{algorithm-end}}
 
{{algorithm-end}}
 
  
 
====Send====
 
====Send====
 
<!--alg_send-->
 
<!--alg_send-->
 
{{algorithm-begin|name=Send}}
 
{{algorithm-begin|name=Send}}
  Input: Message
+
  Input: <math>metaMessage</math>, <math>message</math>
''keyShareMessage'' = '''Call''' '''NewKeyShareMessage'''(MetaMessage)
+
  <math>keyShareMessage</math> = <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''NewKeyShareMessage</span>'''(<math>metaMessage</math>)
''cryptMessage'' := '''Call''' '''AES CTR Encrypt'''(''sessionKey'',''message | keyShareMessage'')
+
  <math>cryptMessage</math> := <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''AES CTR Encrypt</span>'''(<math>sessionKey</math>,<math>message | keyShareMessage</math>)
''originAuthSignature'' := '''Call''' '''ED25519Sign'''(''SignatureKey'', ''sessionId'' || ''cryptMetatMessage'')
+
  <math>originAuthSignature</math> := <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''ED25519Sign</span>'''(<math>SignatureKey</math>, <math>sessionId</math> || <math>cryptMetatMessage</math>)
''sessionDigest'' := '''Call''' '''Compute Session Digest'''(''lastMessage'')
+
  <math>sessionDigest</math> := <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Compute Session Digest</span>'''(<math>lastMessage</math>)
'''Call''' '''Broadcast'''(``:3mpCat:3'', ''sessionId'', ''cryptMessage'', ''sessionDigest'', ''originAuthSignature'',``:3'')
+
  <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Broadcast</span>'''(":3mpCat:3", <math>sessionId</math>, <math>cryptMessage</math>, <math>sessionDigest</math>, <math>originAuthSignature</math>,":3")
 
{{algorithm-end}}
 
{{algorithm-end}}
 
  
 
====Recieve====
 
====Recieve====
 
<!--alg_recv-->
 
<!--alg_recv-->
 
{{algorithm-begin|name=Receive}}
 
{{algorithm-begin|name=Receive}}
  Input: ''sender'', ''encryptedMessage'', ''originAuthSignature'', ''sessionDigest''
+
  Input: <math>sender</math>, <math>encryptedMessage</math>, <math>originAuthSignature</math>, <math>sessionDigest</math>
''v := '' '''Call''' '''ED25519VerifySignature'''(''ephemeralPublicKeyList[Sender]'', ''sessionId || encryptedMessage'', ''originAuthSignature'')
+
  <math>v := </math> <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''ED25519VerifySignature</span>'''(<math>ephemeralPublicKeyList[Sender]</math>, <math>sessionId || encryptedMessage</math>, <math>originAuthSignature</math>)
'''Call''' '''Assert'''(''v'')
+
  <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Assert</span>'''(<math>v</math>) or '''return''' Reject
''message, keyShareMessage :='' '''Call''' '''AES CTR Decrypt'''(''sessionKey'', ''encryptedMessage'')
+
  <math>message, keyShareMessage :=</math> <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''AES CTR Decrypt</span>'''(<math>sessionKey</math>, <math>encryptedMessage</math>){}
''isMetaMessage = '''''Call''' '''UpdateNewKeyStatus'''(''keyShareMessage'')
+
  <math>isMetaMessage = </math><span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''UpdateNewKeyStatus</span>'''(<math>keyShareMessage</math>)
'''Call''' '''Verify Digests'''(''sessionDiges'')
+
  <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Verify Digests</span>'''(<math>sessionDiges</math>)
'''Return'''{''isMetaMessage, message''}
+
  '''return'''{<math>isMetaMessage, message</math>} # isMetaMessage is true if the message is purely meta message and there is nothing to display
 
{{algorithm-end}}
 
{{algorithm-end}}
 
 
\subsection{Common functions}
 
 
 
  
 
====Common functions used by other procedures in different stages====
 
====Common functions used by other procedures in different stages====
 
<!--alg_comm-->
 
<!--alg_comm-->
 
 
 
{{algorithm-begin|name=Generate Initial Paramters}}
 
{{algorithm-begin|name=Generate Initial Paramters}}
  Input: ''myId''
+
  Input: <math>myId</math>
   ''signaturePrivateKey := '' '''Call''' '''RandomBits'''(256)
+
   <math>signaturePrivateKey := </math> <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''RandomBits</span>'''(256)
   ''x_{myId} :='' '''Call''' '''Ed25519 Scalar'''(''signaturePrivateKey''))
+
   <math>x_{myId} :=</math> <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Ed25519 Scalar</span>'''(<math>signaturePrivateKey</math>)) #{This is both Diffie-Hellman secret and ephemeral signature private key}
   ''y_{myId} := x_{myId}P''
+
   <math>y_{myId} := x_{myId}P</math>
  '''Return''' ''x,y''
+
  '''return''' <math>x,y</math>
 
{{algorithm-end}}
 
{{algorithm-end}}
  
  
 
{{algorithm-begin|name=Verify Key Confirmation and Signatures}}
 
{{algorithm-begin|name=Verify Key Confirmation and Signatures}}
  Input: ''signatureList'', ''keyConfirmationList''
+
  Input: <math>signatureList</math>, <math>keyConfirmationList</math>
   '''For each''' ''participant \in participantList''}, '''do'''
+
   '''for each''' <math>participant \in participantList</math>, '''do'''
     \If{''keyConfirmationList[participant][myId] \neq SHA-512(k_{myId,participant}, U_{myId})''}
+
     '''if''' <math>keyConfirmationList[participant][myId] \neq Hash(k_{myId,participant} , U_{myId} )</math>''', then'''
      '''Call''' '''Halt'''()
+
      <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Halt</span>'''()
      ' \If{'''Call''' '''ED25519VerifySignature'''(''ephemeralPublicKeyList[particicpant]'', ''sessionId ||keyShares[myId]'', ''originAuthSignature'')'
+
    '''else''' '''if''' <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''ED25519VerifySignature</span>'''(<math>ephemeralPublicKeyList[particicpant]</math>, <math>sessionId | keyShares[myId]</math>, <math>originAuthSignature</math>) = Fail ''', then'''
      '''Call''' '''Halt'''()
+
      <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Halt</span>'''()
 
{{algorithm-end}}
 
{{algorithm-end}}
  
  
 
{{algorithm-begin|name=Compute Session Id}}
 
{{algorithm-begin|name=Compute Session Id}}
  Input: ''participantList'', ''ephemeralPublicPointList''
+
  Input: <math>participantList</math>, <math>ephemeralPublicPointList</math>
   '''Return''' ''SHA-512(roomeName, zip(participantList, ephemeralPublicPointList))'' # ''zip([a,b],[c,d]):=[(a,c),(b,d)]''
+
   '''return''' <math>Hash(roomeName, zip(participantList, ephemeralPublicPointList))</math>  # <math>zip([a,b],[c,d]):=[(a,c),(b,d)]</math>
 
{{algorithm-end}}
 
{{algorithm-end}}
  
  
 
{{algorithm-begin|name=Verify Signatures}}
 
{{algorithm-begin|name=Verify Signatures}}
  Input: ''longPublicList'',''schnorrRandomPointList'',  
+
  Input: <math>longPublicList</math>,<math>schnorrRandomPointList</math>,  
 +
# standard signature verification
 
{{algorithm-end}}
 
{{algorithm-end}}
  
  
 
{{algorithm-begin|name=Sign and Send Key Confirmation and Share}}
 
{{algorithm-begin|name=Sign and Send Key Confirmation and Share}}
  Input: ''schnorrRandomPointList''
+
  Input: <math>schnorrRandomPointList</math>
'''For each''' ''participant \in participantList'', '''do'''
+
  '''for each''' <math>participant \in participantList</math>, '''do'''
     ''k_{myId, participant} := H(g^{lp_{myId}}LP_{participant}y_{participant}^{x_{myId}})'' # Triple DH
+
     <math>k_{myId, participant} := Hash(x_{myId}LP_{participant} |lp_{myId}y_{participant} | x_{myId}y_{participant})</math>  # Triple DH
     ''kc_{myId} := kc_{myId} | H(k_{myId,participant}, U_{participant})''
+
     <math>kc_{myId} := kc_{myId} | Hash(k_{myId,participant}, U_{participant})</math>
 +
  '''global''' <math>z_{myId -1, myId} := Hash(k_{myId,myId-1}, sessionId)</math>
 +
  '''global''' <math>z_{myId, myId+1} := Hash(k_{myId,myId+1}, sessionId)</math>
 +
  <math>keyShare_{myId} := z_{myId -1, myId} \oplus z_{myId, myId+1}</math>
 +
  <math>originAuthSignature :=</math> <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''ED25519Sign</span>'''(<math>SignatureKey</math>, <math>sessionId</math> || <math>z_{myId}</math>)
 +
  <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Broadcast</span>'''(":3mpCat:3KeyConfirmationAndShare:3", <math>myId</math>, <math>keyShare_{myId}</math>, <math>originAuthSignature</math>, <math>kc_{myId}</math>)
 +
{{algorithm-end}}
  
  
  Global ''z_{myId -1, myId} := SHA-512(k_{myId,myId-1}, sessionId)''
+
{{algorithm-begin|name=Update Session Key}}
  Global ''z_{myId, myId+1} := SHA-512(k_{myId,myId+1}, sessionId)''
+
Input: <math>keyShareList</math>
  ''keyShare_{myId} := z_{myId -1, myId} \oplus z_{myId, myId+1}''
+
  <math>i := myId</math>
 +
  '''for each''' <math>{j \in [i,...,i+n-1]}</math>, '''do'''
 +
      <math>z_{j,j+1} := z_{j-1,j} \oplus keyShareListe[j+1]</math>
 +
    # recovered <math>z_{i-1,i}</math> should be equal to its original value
 +
    '''global''' <math>sessionKey := Hash(z_{j,j+1} | j \in [1...n])</math>
 +
{{algorithm-end}}
  
  
    ''originAuthSignature :='' '''Call''' '''ED25519Sign'''(''SignatureKey'', ''sessionId'' || ''z_{myId'')
+
{{algorithm-begin|name=Sign Params Update Session Key}}
   '''Call''' '''Broadcast'''(``:3mpCat:3KeyConfirmationAndShare:3'', ''myId'', ''keyShare_{myId'')
+
Input: <math>toBeSigned</math>, <math>signatureList</math>,<math>keyShareList</math>
 +
  <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Update Session Key</span>'''()
 +
  <math>toBeSigned := Hash(sessionId, ||Hash(verifierList, ephemeralPublicPointList, keyShareList)))</math>
 +
   <math>signature_{myId} := </math><span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Sign Session and Send</span>'''(<math>toBeSigned</math>)
 +
  <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Broadcast</span>'''(":3mpCat:3SignedSessionParameters:3",<math>signature_{myId}</math>)
 
{{algorithm-end}}
 
{{algorithm-end}}
  
  
{{algorithm-begin|name=Update Session Key}}
+
{{algorithm-begin|name=ComputeSessionDigest}}
  Input: ''keyShareList''
+
  Input: <math>lastMessage</math>
''i := myId''
+
  '''for each''' <math>message</math> in Messages Received from <math>lastDigestedMessage</math>+1 till <math>lastMessage</math>, '''do'''
'''For each''' ''{j \in [i,...,i+n-1]}''}, '''do'''
+
      <math>sesionDigest := Hass(sessionDigest, message)</math>
  ''z_{j,j+1} := z_{j-1,j} \oplus keyShareListe[j+1]''
+
      <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''LRU Cache Store Digest</span>'''(<math>sessionDigest</math>, <math>message</math>)
# recovered ''z_{i-1,i}'' should be equal to its original value
+
  '''return''' <math>sessionDigest</math>,<math>lastMessageId</math>
Global ''sessionKey := SHA-512(z_{j,j+1} | j \in [1...n])''
+
 
{{algorithm-end}}
 
{{algorithm-end}}
  
  
{{algorithm-begin|name=Sign Params Update Session Key}}
+
{{algorithm-begin|name=NewKeyShareMessage}}
  Input: ''toBeSigned'', ''signatureList'', ''keyShareList''
+
  Input: <math>metaMessage</math>
  '''Call''' '''Update Session Key'''()
+
  # Based on metaMessage Determines what type of keyshare needs to be send (Ephemeral point or Group key share) and returen it.
''toBeSigned := SHA-512(sessionId, ||SHA-512(verifierList, ephemeralPublicPointList, keyShareList)))''
+
''signature_{myId} := '''''Call''' '''Sign Session and Send'''(''toBeSigned'')
+
'''Call''' '''Broadcast'''(``:3mpCat:3SignedSessionParameters:3'',''signature_{myId'')
+
 
{{algorithm-end}}
 
{{algorithm-end}}
  
  
{{algorithm-begin|name=ComputeSessionDigest}}
+
{{algorithm-begin|name=UpdateNewKeyStatus}}
  Input: ''lastMessage''
+
  Input: <math>keyShareMessage</math>
'''For each''' ''message'' in Messages Received from ''lastDigestedMessage''+1 till ''lastMessage''}, '''do'''
+
# Update the table of which participant has sent its new ephemeral point or its new group key share
  ''sesionDigest :='' '''Call''' '''SHA-512'''(''sessionDigest'', ''message'')
+
{{algorithm-end}}
'''Call''' '''LRU Cache Store Digest'''(''sessionDigest'', ''message'')
+
 
'''Return''' ''sessionDigest'',''lastMessageId''
+
 
 +
{{algorithm-begin|name=Hash}}
 +
  Input: <math>message</math>
 +
    '''return''' <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''SHA-512</span>'''(<math>message</math>)
 
{{algorithm-end}}
 
{{algorithm-end}}

Latest revision as of 20:40, 28 July 2014

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)