MpOTR/algorithm dump - Revision history

Vmon: /* Common functions used by other procedures in different stages */

2014-07-28T20:40:04Z

‎Common functions used by other procedures in different stages

Vmon: /* Common functions used by other procedures in different stages */

2014-07-28T20:38:08Z

‎Common functions used by other procedures in different stages

Vmon: /* Common functions used by other procedures in different stages */

2014-07-28T20:30:25Z

‎Common functions used by other procedures in different stages

Vmon: /* Farewell */

2014-07-28T20:29:58Z

‎Farewell

Vmon: /* Join */

2014-07-28T20:28:54Z

‎Join

Vmon: /* Chatroom setup */

2014-07-28T20:28:35Z

‎Chatroom setup

Vmon at 20:28, 28 July 2014

2014-07-28T20:28:13Z

Show changes

Vmon at 18:56, 28 July 2014

2014-07-28T18:56:22Z

Show changes

Vmon at 10:33, 27 July 2014

2014-07-27T10:33:05Z

Show changes

Vmon: 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'..."

2014-07-23T21:30:52Z

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'..."

New page

===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====

{{algorithm-begin|name=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}]''
{{algorithm-end}}

{{algorithm-begin|name=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'')
{{algorithm-end}}

====Join====

{{algorithm-begin|name=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'''()
{{algorithm-end}}

{{algorithm-begin|name=Receive Session Digest}}
Input: ''currentSessionHistoryDigest''
Global ''sessionDigest := currentSessionHistoryDigest''
{{algorithm-end}}

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

{{algorithm-begin|name=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'')
{{algorithm-end}}

====Farewell====

{{algorithm-begin|name=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'')
{{algorithm-end}}

{{algorithm-begin|name=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'')
{{algorithm-end}}

====Send====

{{algorithm-begin|name=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'')
{{algorithm-end}}

====Recieve====

{{algorithm-begin|name=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''}
{{algorithm-end}}

\subsection{Common functions}

====Common functions used by other procedures in different stages====


{{algorithm-begin|name=Generate Initial Paramters}}
Input: ''myId''
''signaturePrivateKey := '' '''Call''' '''RandomBits'''(256)
''x_{myId} :='' '''Call''' '''Ed25519 Scalar'''(''signaturePrivateKey''))
''y_{myId} := x_{myId}P''
'''Return''' ''x,y''
{{algorithm-end}}

{{algorithm-begin|name=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'''()
{{algorithm-end}}

{{algorithm-begin|name=Compute Session Id}}
Input: ''participantList'', ''ephemeralPublicPointList''
'''Return''' ''SHA-512(roomeName, zip(participantList, ephemeralPublicPointList))'' # ''zip([a,b],[c,d]):=[(a,c),(b,d)]''
{{algorithm-end}}

{{algorithm-begin|name=Verify Signatures}}
Input: ''longPublicList'',''schnorrRandomPointList'',
{{algorithm-end}}

{{algorithm-begin|name=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'')
{{algorithm-end}}

{{algorithm-begin|name=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])''
{{algorithm-end}}

{{algorithm-begin|name=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'')
{{algorithm-end}}

{{algorithm-begin|name=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''
{{algorithm-end}}

@@ Line 141: / Line 141: @@
   # standard signature verification
 {{algorithm-end}}
 {{algorithm-begin|name=Sign and Send Key Confirmation and Share}}
@@ Line 157: / Line 158: @@
 {{algorithm-begin|name=Update Session Key}}
   Input: <math>keyShareList</math>
-    <math>i := myId</math>
+   <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>

@@ Line 126: / Line 126: @@
       '''if''' <math>keyConfirmationList[participant][myId] \neq Hash(k_{myId,participant} , U_{myId} )</math>''', then'''
         <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Halt</span>'''()
-      ' '''if''' <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''ED25519VerifySignature</span>'''(''', then'''{<math>ephemeralPublicKeyList[particicpant]</math>, <math>sessionId ||keyShares[myId]</math>, <math>originAuthSignature</math>} = Fail}
+      '''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'''
-−
         <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Halt</span>'''()
 {{algorithm-end}}
 {{algorithm-begin|name=Compute Session Id}}
@@ Line 144: / Line 144: @@
 {{algorithm-begin|name=Sign and Send Key Confirmation and Share}}
   Input: <math>schnorrRandomPointList</math>
- '''for each''' <math>participant \in participantList</math>, '''do'''
+   '''for each''' <math>participant \in participantList</math>, '''do'''
       <math>k_{myId, participant} := Hash(x_{myId}LP_{participant} |lp_{myId}y_{participant} | x_{myId}y_{participant})</math>  # Triple DH
       <math>kc_{myId} := kc_{myId} | Hash(k_{myId,participant}, U_{participant})</math>
@@ Line 153: / Line 153: @@
     <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}}
 {{algorithm-begin|name=Update Session Key}}
   Input: <math>keyShareList</math>
- <math>i := myId</math>
+    <math>i := myId</math>
-'''for each''' <math>{j \in [i,...,i+n-1]}</math>, '''do'''
+   '''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>
+      <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
+     # 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>
+    '''global''' <math>sessionKey := Hash(z_{j,j+1} | j \in [1...n])</math>
 {{algorithm-end}}
 {{algorithm-begin|name=Sign Params Update Session Key}}
-  Input: <math>toBeSigned</math>, <math>signatureList</math>, <math>keyShareList</math>
+  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>'''()
+   <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>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>)
+   <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>)
+   <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Broadcast</span>'''(":3mpCat:3SignedSessionParameters:3",<math>signature_{myId}</math>)
 {{algorithm-end}}
@@ Line 175: / Line 176: @@
 {{algorithm-begin|name=ComputeSessionDigest}}
   Input: <math>lastMessage</math>
-'''for each''' <math>message</math> in Messages Received from <math>lastDigestedMessage</math>+1 till <math>lastMessage</math>, '''do'''
+   '''for each''' <math>message</math> in Messages Received from <math>lastDigestedMessage</math>+1 till <math>lastMessage</math>, '''do'''
-   <math>sesionDigest := Hass(sessionDigest, message)</math>
+      <math>sesionDigest := Hass(sessionDigest, message)</math>
-   <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''LRU Cache Store Digest</span>'''(<math>sessionDigest</math>, <math>message</math>)
+      <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''LRU Cache Store Digest</span>'''(<math>sessionDigest</math>, <math>message</math>)
- '''return''' <math>sessionDigest</math>,<math>lastMessageId</math>
+   '''return''' <math>sessionDigest</math>,<math>lastMessageId</math>
 {{algorithm-end}}

@@ Line 117: / Line 117: @@
     <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}
     <math>y_{myId} := x_{myId}P</math>
-  '''return''' <math>x,y</math>
+   '''return''' <math>x,y</math>
 {{algorithm-end}}

@@ Line 74: / Line 74: @@
       <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Wait On Receive</span>'''(":3mpCat:3KeyShare:3")
       <math>keyShareList</math> := <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Receive</span>'''()
-   <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Update Session Key</span>'''(<math>keyShareList</math>)
+     <span style="font-family: serif; font-size: larger; font-variant:small-caps;">'''Update Session Key</span>'''(<math>keyShareList</math>)
 {{algorithm-end}}
 {{algorithm-begin|name=Sign and Send Key Shares}}

@@ Line 11: / Line 11: @@
     <math>ephemeralPublicPointList := [y_{myId}, y_{other}]</math>
 {{algorithm-end}}
 {{algorithm-begin|name=Verify Verifier Generate Init Key}}