Encryption in the VM can be done using RPO as was described in this paper.
Encryption
Encryption can be summarized using the following figure
As can be seen from the figure, we need to initialize the state of the hash function with a key (assumed to be a word) and a nonce and call the permutation once.
To encrypt, assuming we have the plaintext we would like to encrypt laid out in a contiguous memory region, we need to:
Load the plaintext in batches of two words and add it to the top 8 stack elements (i.e., the rate portion of the state) element-wise. This results in the ciphertext block corresponding to the plaintext we just loaded.
Store the ciphertext block in some memory region.
Call the permutation.
Repeat until all plaintext blocks have been processed (i.e., encrypted).
The most costly part of the above will be the stack manipulations needed to achieve the first point and to store the ciphertext. It seems that if we want to make the cost of encryption reasonable we would need to introduce an additional VM instruction or potentially more than just one.
Option 1
The new instruction can take a pointer on the stack ptr and it can do:
Fetch the double word referenced by ptr.
Add the double word to the top 8 stack elements element-wise.
Store the top 8 stack elements resulting from the previous point in the memory region referenced by ptr. This amounts to overwriting the double word from point $1$.
Increment the pointer by $2$.
The following figures illustrate this:
Option 2
If we want to avoid overwriting the plaintext in memory, we can use an additional pointer on the stack to reference the memory region we would like to use for storing the resulting ciphertext.
The following figure illustrates this alternative:
Note that in this case we will need to increment the additional pointer as well by $2$.
Decryption
Decryption can be summarized using the following figure
As can be seen from the figure, we need to initialize the state of the hash function with a key (assumed to be a word) and a nonce and call the permutation once.
To decrypt, assuming we have the ciphertext we would like to decrypt laid out in a contiguous memory region, we need to:
Negate (i.e., compute the additive inverse) of each of the top 8 stack elements.
Load the ciphertext in batches of two words and add it to the top 8 stack elements (i.e., the rate portion of the state) element-wise. This is the plaintext block corresponding to the ciphertext we just loaded.
Store the plaintext block in some memory region.
Overwrite the top 8 stack elements with the same ciphertext double word from point $2$ above.
Call the permutation.
Repeat until all ciphertext blocks have been processed (i.e., decrypted).
As can be seen from the previous description, decryption is a more complex operation than encryption. Depending on the use cases, it might be fine to do decryption with the currently available instructions. However, and if we are willing to introduce a new instruction for encryption, we might be able to design a more generic instruction that might be useful for both encryption and decryption.
One possible way to do decryption using a dedicated instruction could be to have, again, two pointers, one to reference the ciphertext and the other to reference the plaintext.
Then, the new instruction could take care of points 1-3, as illustrated in the following two figures
Note that in the above, we have only updated the pointer referencing the plaintext.
At this point, we can use the existing mem_stream instruction to accomplish step 4 as the following figure illustrates
Questions
Could we design an instruction that would be helpful for both encryption and decryption? Maybe a flag to switch between the two and do addition element-wise for encryption and "subtraction" element-wise for decryption?
Should we just forget about decryption and design a specialized instruction to do only encryption?
Can we modify mem_stream to make it more general and avoid needing to add any new instructions?
Encryption in the VM can be done using RPO as was described in this paper.
Encryption
Encryption can be summarized using the following figure
As can be seen from the figure, we need to initialize the state of the hash function with a key (assumed to be a word) and a nonce and call the permutation once.
To encrypt, assuming we have the plaintext we would like to encrypt laid out in a contiguous memory region, we need to:
The most costly part of the above will be the stack manipulations needed to achieve the first point and to store the ciphertext. It seems that if we want to make the cost of encryption reasonable we would need to introduce an additional VM instruction or potentially more than just one.
Option 1
The new instruction can take a pointer on the stack
ptrand it can do:ptr.ptr. This amounts to overwriting the double word from point $1$.The following figures illustrate this:
Option 2
If we want to avoid overwriting the plaintext in memory, we can use an additional pointer on the stack to reference the memory region we would like to use for storing the resulting ciphertext. The following figure illustrates this alternative:
Note that in this case we will need to increment the additional pointer as well by $2$.
Decryption
Decryption can be summarized using the following figure
As can be seen from the figure, we need to initialize the state of the hash function with a key (assumed to be a word) and a nonce and call the permutation once.
To decrypt, assuming we have the ciphertext we would like to decrypt laid out in a contiguous memory region, we need to:
As can be seen from the previous description, decryption is a more complex operation than encryption. Depending on the use cases, it might be fine to do decryption with the currently available instructions. However, and if we are willing to introduce a new instruction for encryption, we might be able to design a more generic instruction that might be useful for both encryption and decryption. One possible way to do decryption using a dedicated instruction could be to have, again, two pointers, one to reference the ciphertext and the other to reference the plaintext. Then, the new instruction could take care of points 1-3, as illustrated in the following two figures
Note that in the above, we have only updated the pointer referencing the plaintext. At this point, we can use the existing
mem_streaminstruction to accomplish step 4 as the following figure illustratesQuestions
mem_streamto make it more general and avoid needing to add any new instructions?