Changes

MpOTR/algorithm dump

944 bytes added, 9 years ago
===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====
<!--alg_chat_setup-->
{{algorithm-begin|name=Chat Initiator Init}}
Input: ''<math>newRoomName''</math>, ''<math>participantNick''</math> Global ''<math>myId := 1''</math> Global ''<math>Nick_{myId} := participantNick''</math> Global ''<math>roomName := newRoomName''</math> Global ''<math>x_{myId}, y_{myId} :='' </math> '''Call''' '''Generate Initial Paramters'''(''<math>myId''</math>) Global ''<math>signatureKey_{myId} := (x_{myId},y_{myId})''</math> ''<math>participantList := [Nick_{myId}]''</math> ''<math>ephemeralPublicPointList := [y_{myId}, y_{other}]''</math>
{{algorithm-end}}
{{algorithm-begin|name=Verify Verifier Generate Init Key}}
Input: ''<math>schnorrRandomPoint_{other''</math>
'''Call''' '''Verify Verifiers'''()
Global ''<math>sessionKey := SHA-512(x_{myId}y_{other}, sessionId)''</math> ''<math>toBeSigned := SHA-512(SHA-512(sessionId||SHA-512(y_1, v_1)||SHA-512(y_2,v_2)))''</math> '''Call''' '''Sign Session and Send'''(''<math>toBeSigned''</math>)
{{algorithm-end}}
<!--alg_join-->
{{algorithm-begin|name=Join}}
Input: ''<math>newRoomName''</math>, ''<math>Nickname_{myId''</math> Global ''<math>myId := participantId''</math> Global ''<math>roomName := newRoomName''</math> ''<math>x_{myId}, y_{myId} := ''</math>'''Call''' '''Generate Initial Paramters'''(Participant ID ''<math>myId''</math>) Global ''<math>signatureKey_{myId} := (x_{myId},y_{myId})''</math> '''Call''' '''Broadcast'''(``:3mpCat:3Join:3'', ''<math>myId''</math>, ''<math>Nickname_{myId''</math>) Global ''<math>participantList, ephemeralPublicPointList :='' </math> '''Call''' '''Receive'''() Global ''<math>sessionId := '' </math> '''Call''' '''Compute Session Id'''(''<math>roomName''</math>, ''<math>participantList''</math>, ''<math>ephemeralPublicPointList''</math>)
'''Call''' '''Sign and Send Key Confirmation and Shares'''()
'''Call''' '''Wait On Receive'''(``:3mpCat:3KeyConfirmationShare:3'')
Global ''<math>keyShareList, keyConfirmationList, signatureList :='' </math> '''Call''' '''Receive'''() '''Call''' '''Verify Key Confirmations and Signatures'''(''<math>keyConfirmationList''</math>, ''<math>signatureList''</math>)
'''Call''' '''Update Session Key'''()
{{algorithm-end}}
{{algorithm-begin|name=Receive Session Digest}}
Input: ''<math>currentSessionHistoryDigest''</math> Global ''<math>sessionDigest := currentSessionHistoryDigest''</math>
{{algorithm-end}}
{{algorithm-begin|name=Accept}}
Input: newParticipant
'''Call''' '''Broadcast'''(``:3mpCat:3Join:3'', ''<math>myId''</math>, ''<math>Nickname_{myId''</math>)
'''Call''' '''Wait On Receive'''(``:3mpCat:3Join:3'')
Global ''<math>nick_{NewParticipant}''</math>, ''<math>ephemeralPublicPoint_{NewParticipant} := '' </math> '''Call''' '''Receive'''() '''Call''' '''Update Lists'''(''<math>nick_{NewParticipant''</math>) Global ''<math>sessionId := '' </math> '''Call''' '''Compute Session Id'''(''<math>roomName''</math>, ''<math>participantList''</math>, ''<math>ephemeralPublicPointList''</math>)
'''Call''' '''Sign and Send Key Confirmation and Shares'''()
'''Call''' '''Wait On Receive'''(``:3mpCat:3KeyConfirmationShare:3'')
Global ''<math>keyShareList, keyConfirmationList, signatureList :='' </math> '''Call''' '''Receive'''() '''Call''' '''Verify Key Confirmations and Signatures'''(''<math>keyConfirmationList''</math>, ''<math>signatureList''</math>)
'''Call''' '''Update Session Key'''()
'''Call''' '''Send'''(''<math>sessionDigest''</math>)
{{algorithm-end}}
<!--alg_farewell-->
{{algorithm-begin|name=Shrink on Leave}}
Input: ''<math>leaverId''</math> Remove ''<math>leaverId'' </math> from ''<math>participantIdList''</math> Global ''<math>sessionId :='' </math> '''Call''' '''Compute Session Id'''() \If{''<math>|participantList| > 1''</math>}
'''Call''' '''Sign and Send Key Shares'''()
'''Call''' '''Wait On Receive'''(``:3mpCat:3KeyShare:3'')
''<math>keyShareList'' </math> := Receive{} '''Call''' '''Update Session Key'''(''<math>keyShareList''</math>)
{{algorithm-end}}
{{algorithm-begin|name=Sign and Send Key Shares}}
Input:
Global ''<math>z_{myId -1, myId} := SHA-512(k_{myId,myId-1}, sessionId)''</math> Global ''<math>z_{myId, myId+1} := SHA-512(k_{myId,myId+1}, sessionId)''</math> ''<math>keyShare_{myId} := z_{myId -1, myId} \oplus z_{myId, myId+1}''</math> ''<math>originAuthSignature :='' </math> '''Call''' '''ED25519Sign'''(''<math>SignatureKey''</math>, ''<math>sessionId'' </math> || ''<math>z_{myId''</math>) '''Call''' '''Broadcast'''(``:3mpCat:3KeyShare:3'', ''<math>myId''</math>, ''<math>keyShare_{myId''</math>)
{{algorithm-end}}
{{algorithm-begin|name=Send}}
Input: Message
''<math>keyShareMessage'' </math> = '''Call''' '''NewKeyShareMessage'''(MetaMessage) ''<math>cryptMessage'' </math> := '''Call''' '''AES CTR Encrypt'''(''<math>sessionKey''</math>,''<math>message | keyShareMessage''</math>) ''<math>originAuthSignature'' </math> := '''Call''' '''ED25519Sign'''(''<math>SignatureKey''</math>, ''<math>sessionId'' </math> || ''<math>cryptMetatMessage''</math>) ''<math>sessionDigest'' </math> := '''Call''' '''Compute Session Digest'''(''<math>lastMessage''</math>) '''Call''' '''Broadcast'''(``:3mpCat:3'', ''<math>sessionId''</math>, ''<math>cryptMessage''</math>, ''<math>sessionDigest''</math>, ''<math>originAuthSignature''</math>,``:3'')
{{algorithm-end}}
<!--alg_recv-->
{{algorithm-begin|name=Receive}}
Input: ''<math>sender''</math>, ''<math>encryptedMessage''</math>, ''<math>originAuthSignature''</math>, ''<math>sessionDigest''</math> ''<math>v := '' </math> '''Call''' '''ED25519VerifySignature'''(''<math>ephemeralPublicKeyList[Sender]''</math>, ''<math>sessionId || encryptedMessage''</math>, ''<math>originAuthSignature''</math>) '''Call''' '''Assert'''(''<math>v''</math>) ''<math>message, keyShareMessage :='' </math> '''Call''' '''AES CTR Decrypt'''(''<math>sessionKey''</math>, ''<math>encryptedMessage''</math>) ''<math>isMetaMessage = ''</math>'''Call''' '''UpdateNewKeyStatus'''(''<math>keyShareMessage''</math>) '''Call''' '''Verify Digests'''(''<math>sessionDiges''</math>) '''Return'''{''<math>isMetaMessage, message''</math>}
{{algorithm-end}}
{{algorithm-begin|name=Generate Initial Paramters}}
Input: ''<math>myId''</math> ''<math>signaturePrivateKey := '' </math> '''Call''' '''RandomBits'''(256) ''<math>x_{myId} :='' </math> '''Call''' '''Ed25519 Scalar'''(''<math>signaturePrivateKey''</math>)) ''<math>y_{myId} := x_{myId}P''</math> '''Return''' ''<math>x,y''</math>
{{algorithm-end}}
{{algorithm-begin|name=Verify Key Confirmation and Signatures}}
Input: ''<math>signatureList''</math>, ''<math>keyConfirmationList''</math> '''For each''' ''<math>participant \in participantList''</math>}, '''do''' \If{''<math>keyConfirmationList[participant][myId] \neq SHA-512(k_{myId,participant}, U_{myId})''</math>}
'''Call''' '''Halt'''()
' \If{'''Call''' '''ED25519VerifySignature'''(''<math>ephemeralPublicKeyList[particicpant]''</math>, ''<math>sessionId ||keyShares[myId]''</math>, ''<math>originAuthSignature''</math>)'
'''Call''' '''Halt'''()
{{algorithm-end}}
{{algorithm-begin|name=Compute Session Id}}
Input: ''<math>participantList''</math>, ''<math>ephemeralPublicPointList''</math> '''Return''' ''<math>SHA-512(roomeName, zip(participantList, ephemeralPublicPointList))'' </math> # ''<math>zip([a,b],[c,d]):=[(a,c),(b,d)]''</math>
{{algorithm-end}}
{{algorithm-begin|name=Verify Signatures}}
Input: ''<math>longPublicList''</math>,''<math>schnorrRandomPointList''</math>,
{{algorithm-end}}
{{algorithm-begin|name=Sign and Send Key Confirmation and Share}}
Input: ''<math>schnorrRandomPointList''</math> '''For each''' ''<math>participant \in participantList''</math>, '''do''' ''<math>k_{myId, participant} := H(g^{lp_{myId}}LP_{participant}y_{participant}^{x_{myId}})'' </math> # Triple DH ''<math>kc_{myId} := kc_{myId} | H(k_{myId,participant}, U_{participant})''</math>
Global ''<math>z_{myId -1, myId} := SHA-512(k_{myId,myId-1}, sessionId)''</math> Global ''<math>z_{myId, myId+1} := SHA-512(k_{myId,myId+1}, sessionId)''</math> ''<math>keyShare_{myId} := z_{myId -1, myId} \oplus z_{myId, myId+1}''</math>
''<math>originAuthSignature :='' </math> '''Call''' '''ED25519Sign'''(''<math>SignatureKey''</math>, ''<math>sessionId'' </math> || ''<math>z_{myId''</math>) '''Call''' '''Broadcast'''(``:3mpCat:3KeyConfirmationAndShare:3'', ''<math>myId''</math>, ''<math>keyShare_{myId''</math>)
{{algorithm-end}}
{{algorithm-begin|name=Update Session Key}}
Input: ''<math>keyShareList''</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> # recovered ''<math>z_{i-1,i}'' </math> should be equal to its original value Global ''<math>sessionKey := SHA-512(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>
'''Call''' '''Update Session Key'''()
''<math>toBeSigned := SHA-512(sessionId, ||SHA-512(verifierList, ephemeralPublicPointList, keyShareList)))''</math> ''<math>signature_{myId} := ''</math>'''Call''' '''Sign Session and Send'''(''<math>toBeSigned''</math>) '''Call''' '''Broadcast'''(``:3mpCat:3SignedSessionParameters:3'',''<math>signature_{myId''</math>)
{{algorithm-end}}
{{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''' ''<math>sesionDigest :='' </math> '''Call''' '''SHA-512'''(''<math>sessionDigest''</math>, ''<math>message''</math>) '''Call''' '''LRU Cache Store Digest'''(''<math>sessionDigest''</math>, ''<math>message''</math>) '''Return''' ''<math>sessionDigest''</math>,''<math>lastMessageId''</math>
{{algorithm-end}}