SAVA:
Secure, Anonymous, Authenticated

and Verifiable
message sending Algorithm

By

Robert Wensman

Note

This object is shared by google-docs. If you find this topic interesting, have comments or questions, please feel free to contact me by email:

Acknowledgements

SAVA is an original algorithm invented by the author. However, I would like to direct a special thanks to Joakim Sigvald for ideas of how to generate partial identities that greatly simplified the operation and description of the algorithm. I would also thank Jonas Liljegren for general inspiration when it comes to the possibilities of message sending (voting) verification, and to Egil Möller for starting the quest for a secure online voting algorithm a long time ago.

Capabilities Overview

SAVA is a cryptographic distributed algorithm for secure anonymous and authenticated message sending through a network. A SAVA network consists out of a number of internal servers arranged in a specific configuration, each following a specific protocol when executing the SAVA distributed algorithm.

The main feature of the SAVA network is anonymity. When a number of messages has been sent through the network, it is impossible, even for the individual internal servers of the system, to know what message originated from what user.

Another notable feature of SAVA is the possibility of authenticity. The possibility to give certain guarantees in terms of what was the origin is of messages coming out from the network. Given that all users sending encrypted messages into the SAVA network are authenticated, it can be guaranteed that:

  1. The messages going out from the network are not modified.
  2. That new messages has not been added.
  3. That messages has not been removed.

This feature in particular, makes SAVA particularly suitable for online voting systems.

A network using this algorithm is protected from two kinds of attacks, targeted at breaking either anonymity or authentication; internal attacks from within the network itself, and external attacks that originate from outside the network.

The extensive protection from internal attacks is a key feature of SAVA, and one thing that sets it apart from for example the Tor algorithm. The network is setup so that n out of n internal servers has to cooperate to be able to break either anonymity or authentication. This grants an extreme level of protection for this kind of application.

The system is also open to external inspection and verification from outside, and every user can verify that his message has been sent through the system without any tampering, and that the system has not sent any additional messages on the user’s behalf.

External inspection can also verify that the internal servers follows the SAVA protocol. If any internal server attempts to attack the authenticity guarantees given by the network by for example manipulating the message traffic, it can be discovered by external inspection after which measures can be taken to correct the situation, such as replacing the protocol breaking server in the network and re-sending messages through the network.


The system is primarily set up for sending messages in one direction. From a sender of a message, to a multitude of receivers that receive the message without knowing the sender's identity. However, by for example sending public keys as a message through the system, encrypted communication in the reverse direction can be set up. That topic is however not in the scope of this document.

Two modes of operations

The SAVA system can run in two distinct modes. One time mode or continuous mode.

When using one time mode, a batch M1 of of user messages are sent through the SAVA network so that we cannot know what user each message originated from. However, if we send another batch M2 of messages through the network, there is no way of telling what message from the M1 batch originates from the same user as any message from the M2 set. The consecutive batches are completely separate and unrelated. Consecutive batches can be of different sizes, and can contain messages from a different set of users.

The anonymity of all users is upheld as long as at least one internal server does not store information about what encrypted onion routed message fragment correspond to what unencrypted onion routed message fragment in the next routing stage and keeps its onion routing encryption keys a secret.

The purpose of continuous mode is to send multiple message batches through the network, together with information of how the batches relate to each other.

More specifically, for any message of any batch, it should be possible to see what other message out of any other batch that was sent by the same user.

For this purpose, the SAVA network attaches an unique anonymous identity to each message coming out from the network. This unique anonymous identity can not be traced back to the original user however, not by any external inspection or by several internal servers.

The anonymity of all users is upheld as long as at least one internal server does not store information about what encrypted onion routed message fragment correspond to what unencrypted onion routed message fragment in the next routing stage, keeps its onion routing encryption keys a secret and does not disclose the bijective mapping between partial identities used in each stage.

One limitation with continuous mode, is that in order to guarantee maximum security and avoid attacks on anonymity involving user set intersection analysis, it is necessary for all consecutive batches to be of equal size, and that they contain messages from the same set of users for as long as the continuous mode runs.  

Architectural overview

In standard configuration, a SAVA network is made up from a ring of n internal servers (see image at first page depicting 8 servers V1..Vn (wrongly denoted V1 for all in the picture), each using 8 ports for communication).

A message sent by a user is first cryptographically split into n separate fragments that are all needed in order to reconstruct the original message, and where all fragments are non readable without all parts. In addition, the algorithms used to reconstruct the message, are such that it is difficult to replace one of the fragments, in such a way that the reconstructed message is changed into some message desired by a presumed attacker.

 ,

F1 = Nn-1(Nn-2( … N1(Message, Salt) … ))O

F2 = N1,O

Fn = Nn-1,O

In order to create n:fragments out of a message, n-1 symmetric encryption keys are created N1.. Nn-1. These keys will only be used one single time. Because it should be difficult to replace a certain key in order to create a desired new message XOR cannot be used for symmetric cryptography algorithm. All these symmetric encryption keys are applied consecutively to the original message (combined with salt) and then combined with a fragment sequence marker. This is the first fragment. All the encryption keys are also combined with the same fragment sequence marker to form the rest of the fragments.

All fragments are then individually onion-encrypted to take a specific route over the SAVA network.


The system works in certain phases, which involves certain activities:

  1. The collection phase.
  1. authentication.(optional)
  2. partial identity construction. (for continuous mode only)
  1. n-1 distinct routing(n) phases.
  1. temporal message random mixing.
  1. The message fragments combination phase.

When using continuous mode, phases 1-3 are repeated a number of times during the continuous mode runtime. These phases might then overlap somewhat in time, except for the n-1 distinct routing phases that needs to be strictly consecutive.

The first phase is the collection phase, where the onion encrypted fragments are sent to the first port of the internal servers.

At this stage, and optional authentication can take place, where each user is authenticated at each internal server, using his/her real electronic-id. For certain systems however, this might not be necessary.

If continuous mode is to be used, the user’s real identity id(M) is replaced with a partial identity VnPartial(id(M)) at each internal server Vn. This partial identity that is shared by the set VnSharerSet(id(M)) of other users at a particular internal server Vn, such that the following property holds:

 

V1SharerSet(id(M)) V2SharerSet(id(M))  … VnV2SharerSet(id(M)) = {id(M)}

It is also necessary that all |VnSharerSet(id(M)| = k for all servers Vn and for all users M, meaning all sets of users that share the same partial identity at each server should be of equal size. To enforce this, dummy users might need to be added to the system so that the number of users is divisible by the number of internal servers.

This guarantees that when the partial identities are re-mapped at n steps using bijective functions, the combination of the outcoming partial identities will be unique.

Using less mathematical terms and more computational terms, a partial identity, could be certain selected bits out of a binary identifier for each user. For example, if we assume that there are exactly 2^8 users of the system, and a user's identity is a 8 bit integer, then a partial identity could be the first two bits of this identity.

 

The system then enters n-1 routing phases 1..(n-1) that may not overlap in time, where at each step one layer of the onion encrypted fragments is removed. At the start of routing phase p, all encrypted fragments have arrived at port p of all servers s. These encrypted fragments are decrypted one step, and then sent in random order to port p+1 of server mod(s+1, n). This give cause to the spiral shape routing as depicted by the image on the front page.

It is important that some bytes of salt (random data) is added between every onion layer in the onion encrypted fragment. This salt is discarded at every step, making it impossible to backtrace a message by trying to encrypt all outgoing messages with the server/port’s public encryption key, and see what incoming message they match. The onion routed messages have a structure as follows Where Vnp(M) is a message encrypted with Vn’s public encryption key for port p. the encryption

[“To  V1, Partial_Identity, V1p(“To V2, V2p( … Vj-1p(“To Vj, Vjp(F1,Saltj), Saltj-1) … Salt2), Salt1)]

If we use continuous mode, the partial identity of an encrypted fragment is remapped one step using a secret bijective identity map that is only known by the particular server. The new partial identity is sent along at every step.

At the end of the onion routes, all original fragments of a message are available, and they can be combined using the fragment sequence markers in order to reconstruct the original message.

The principle of SAVA security

The purpose of having only partial identities, or no identities at all through each routing chain of the network, is that the breaking of one or several routes will not break the anonymity of a user. The purpose of splitting the message into several fragments sent over different routes, is that breaking one or several routes, cannot compromise the authenticity of messages. In fact, with SAVA, all internal servers has to be successfully taken over first, in order to successfully launch an attack at system and break its anonymity and authentication, and that makes a totally new level of security possible for this kind of system. If the internal servers of a SAVA network ring are located in different countries, run by different organization, the protection of anonymity would be pretty high.

SAVA compared to TOR algorithm

TOR and SAVA has certain similarities, in that it is two algorithms that are used for anonymization and that onion-encryption is used as a base for the systems.

The first difference is that TOR is not intended for
authenticated anonymity that is a key feature of SAVA. This means that the messages coming out of the TOR network could originate from users sending messages into the network, but the messages could just as well have been generated by the network’s internal servers. In contrast, any message coming out of a SAVA network is guaranteed to have originated from some user, under the premise that at least 1 SAVA network servers out of n are not participating in any attack on authentication. If any server breaks the rule of the protocol it can be detected and replaced and/or held accountable.

The other major difference, which has already been hinted at, lies in the strength by which the network is protected from internal attacks in general, either when targeted at breaking anonymity or authentication. In TOR, there is a pool of n servers, from where a random path of k servers is selected when a message is sent.

However, anyone attacking the system could just enter a number of hostile servers in the pool, and depending on luck, if these servers appear in a certain path selected by a user, it could break that users anonymity and/or manipulate the communication. The most simple case would be if the user unluckily selects k hostile servers out of the n servers, then all anonymity would be void, and the chain of hostile servers can take over the communication in either direction.

If the a user picks just two hostile servers, one at the start and one at the end of the onion encryption route, there are possibly other ways to attempt breaking the user’s anonymity, for example by time analysis, or by trying to resend previous messages (if not protected against) or construct new messages that are sent through the same route. If it is possible to resend messages for the two servers, then they can send messages in a predetermined pattern, and by traffic analysis determine the identity of the original user.

We can also note that the history of TOR confirms that it is not a bulletproof solution to anonymity. The notorious Silk Road site of the deep web, was for example exposed by FBI, by injecting hostile servers into the TOR server pool, and waiting for the right opportunity.

In contrast, this kind of attack would not be possible if a SAVA network would have been used. For a SAVA network to be successfully attacked. The attacker would have to take over all internal servers of the entire network before an attack could be attempted. This means the level of anonymity when using SAVA compared to TOR, is strengthened by an order of magnitude.  

However, it needs to be said that the usage of strongly cryptographically secured anonymity is not limited to the kind of website that Silk Road represents. Strong encrypted anonymity and authentication a necessary tool for bringing democracy to the digital world, enable secure online votings and enabling free speech during oppression. Just like with any technology, it can be used for good or bad.

Limitations of continuous mode of operation

When using continuous mode of operation, we noted previously that there is a limitation, in that all the batches of messages sent through the SAVA network needs to contain messages from the same set of users. The reason for this is very simple, and has to do with intersection analysis attacks.

Assume for example that one day the set of A user’s sends a batch to the SAVA network. The next day a set of B users sends a batch. Assume further that it accidentally happens that A∩B = { U } for some user U! This would make it easy for an attacker to figure out the anonymous identity of U by simply comparing what anonymous identity sent a message both days! When the same SAVA networks runs continuously with multiple batches, the possibility of finding such an intersection gets higher!

So, in conclusion, it is important that all users send exactly one message each batch in continuous mode. In certain situations, this requirement could be difficult to maintain, so we will discuss ways to help alleviate this problem.

For example, assume that we use a SAVA network running in continuous mode with a runtime of a year, to implement a national voting system in a nation of 10 million people. Assume also that the voting system process one batch every day, for the entire year, resulting in 356 batches during the total runtime of the system. How could we guarantee that in every batch, a message from all 10 million people are present? Here are two ways to achieve this:

  1. Stored backup messages. At the startup of a SAVA network running in continuous mode with n message batches over it’s intended runtime, every user stores n fragmented backup messages at the entrance of the server. These backup are blank messages that do not contain any actual information, but whenever a particular user does not submit a message during a specific collection phase, a backup message is used.

  1. Redundant message sending hardware. The other way to deal with this session is dependent on a future where network connectivity and computer hardware is a true commodity in the hand of every user. Every user could have 2 or more devices, such as smartphones, computers or dedicated message sending hardware, that send a message into the system at every batch. Redundant hardware means that even if one device loses battery/power or network connectivity, there are still devices that can send a message. If the user does not send a message destined for one particular batch, the redundant hardware creates a blank message that is sent instead.  

It turns out that stored backup messages lessen the risk of detection as all anonymous identities are used in every batch, but depending on the frequency of blank messages, a user relying on a stored backup message would still risk being exposed, as any attacker knows that a person whose stored backup message was used, will correspond to an anonymous identity that sent a blank message a particular batch.

Using redundant hardware could therefore prove the stronger alternative, but since there is always a chance that all devices run out of power or loose connectivity for some reason, it appears that we get the strongest security by combining the both methods.

Closed mode of operation as an alternative (SACA)

The original SAVA is designed to be have an open mode of operation. This means that all information sent between the internal servers of the network is open to the public, although this information might be in different stages of encryption and only meaningful to anyone recognizing the message, or having the right cryptographic key in order to decrypt the information. This enables:

  1. For a certain user to verify that his specific information is being sent through the system as it should, and verify that it is processed correctly at each stage, and that the right message comes out at the end.
  2. For external inspection that verifies that the internal servers follow the rules of the algorithm. That they send as many messages as they receive, and for many parties to inspect the messages that comes out of the system.

An open system also means that any constructed anonymous identity at the end of the is made public (although the association back to the original user remains a secret). This is especially important when running in continuous operation mode.

It also means that any consolidation of the messages that comes out of the system is done in public. For example, if the messages are votes, then all specific votes are displayed in public at the end of the system. Any user of the internet can then download this raw data, and do their own calculation of the outcome of the referendum.

The open architecture has many benefits in terms of strengthened security and verification. However, when SAVA is used for an online voting system, some people will argue that vote buying is a potential threat, and that the verification functionality of the system is the enabler of this threat. The argument is that the ability to verify allows a buyer of votes to verify that the provider of votes in fact delivers the votes.


It is however possible to reconstruct SAVA into a closed system that is not externally verifiable, by simply adding a layer of asymmetric encryption in any communication encryption between the servers, this is called SACA. There would still be the protection that the n internal servers of the but instead of publicly displaying the output messages of the internal servers would reconstruct any voting result, and each present one result to the public.

SACA could be set up so that a optional and directable verification message is sent back through the closed system to a specified destination. This means that the vote message itself optionally contains an optional return address, where the network can send an encrypted verification of the fragment acknowledgement from each server. This could serve two purposes:

  1. The verification could contain some secret information hidden in the original message. By sending this information back to the user, the user has a guarantee that his vote message was sent all the way through the network and decrypted by all the vote servers.
  2. In case of vote buying, a seller of votes can always retract the vote secretly by changing the destination of the vote verification, and vote again in the same referendum (if possible).

However, certain things needs to be said. First, a close system can never give the same guarantees as an open system in terms of verification and security. The closed system relies on that a majority of internal servers gives a correct vote count.

Secondly, even if we assume that vote buying is such a problem in the first place, then even a closed system is not secure against plain identity buying. If the seller simply sells his digital id to the buyer, then the added protection against vote buying that the closed system offer is nullified.

Alternatives to a closed system
It is the belief of this author that SACA is not to prefer over SAVA, and also that even in an open system like SAVA, there are other ways to prevent vote buying, such as first, on a technical level, allow
identity nullification.

Identity nullification in SAVA means that if a user has sold or lost his private voting key to some other person, he can simply revoke that key by signing a document with his electronic-id that nullifies his public key. A message can optionally be sent through the system, that nullifies all votes of the associated anonymous identity. The user can no longer vote, for as long as the system is reusing the same anonymous identities, but it also means that the anonymous identity cannot be used any further by the buyer and his purchase was useless. Sure enough, the buyer can know that he was tricked, but the purchase is still useless.

Another way to prevent vote buying has to do with the politics of society. Vote selling can be made social taboo associated with shame, which could to a large degree prevent it. Also, if a certain degree of equality is maintained in society, with decent living standards for all people, it would also discourage vote selling as an act of desperation. From a libertarian standpoint, it can even be argued that vote selling should be legal and permitted, seeing it as a simple consequence of personal freedom, and the idea that people should not need to be protected from themselves. If people are stupid and sell their democratic influence for money, well it is stupid, but they should have the right to be stupid and do so.

Different use cases for SAVA

SAVA can be used for a number of different applications, ranging from anonymous web fora, to platforms for online democracy. This chapter gives a brief description of how SAVA could be applied.

To support electronic-voting and referendums

Assume that we would run ordinary parliament elections, then it could be done with SAVA running in one time mode. The system simply collects a batch of messages, each corresponding to the vote of one user, authenticated with their electronic-id. The batch is then simply routed through the SAVA network, and the final election result can be assembled. The conditions for this is that the dates of the message collection are predetermined.

In a similar way, referendums could be held using SAVA one time mode.

To support liquid democracy and other new forms of democracy

However, more modern approaches to democracy advocate a mix of voting for representatives and voting directly on certain issues. One such approach is liquid democracy, where a user selects a number of representatives, that represent the user in every referendum where the user does not vote himself/herself. It turns out that this puts additional requirements on the voting system, and there are two ways to do it.

  1. External representation. One way to achieve liquid democracy is to externalize the representation. Essentially, we have a system of individual referendums that could use SAVA one time mode. In external mode, each user’s hardware/software has the responsibility to find out what the opinion of his/her representatives is, and relay that opinion using his own vote. Essentially, the system then uses pure direct democracy internally, with a sophisticated system of voting-clients that follows the advice of representatives.
  2. Internal representation. Another way to achieve liquid democracy is to internalize the representation. This however makes it necessary to use SAVA in continuous mode, allowing each voter to have an anonymous identity that is alive for as long as the continuous runtime. This makes it possible for a user to register into the system that “when I do not vote, I want to vote as representative X”. The user can then remain passive when desired.

However, we can note one very important finding. That is that in either case, liquid democracy demands a high degree of user connectivity, and/or complexity of its voting hardware. It essentially requires that a user has one or several devices that is connected to the Internet every day, either as in the case of external representation, to vote on all referendums currently active, or in the case of internal representation, to send blank messages every day as not to break anonymity.

It is the belief of this author, that if we are to build a system for liquid democracy, internal representation is to be preferred. This is since both alternatives put a lot of requirements on user hardware/connectivity, but the user client has to be more advanced in the case of external representation.

To support an anonymous web forum

A web-forum could be made “anonymous” by simply not storing the ip:address of people who post messages, however, it would be still be possible for Internet mass-surveillance to break such simple anonymity.

A stronger approach to anonymity is for users to use an anonymization service, that mixes up the user’s traffic with other users. However, it is still necessary to place some level of trust into this service. Either that the information about identity mappings is not stored in the anonymity service, and/or that the service itself has not been taken over by hostile software.

An even stronger approach is to use a TOR network as an anonymization service, but as we have seen, if only some of the TOR network servers are hostile and participate in an attack, a user could if unlucky become exposed and lose his/her anonymity.

SAVA could here provide a stronger anonymity, by dividing the trust onto several different SAVA servers. All of these servers would have to cooperate in order to break the anonymity of a user, which is less likely. For this kind of application, SAVA would run in one time mode. It would also use batches of a certain size, in order to guarantee a certain degree of anonymity. For example, the system could be set up to wait for 1000 incoming messages before sending them as a one time batch through the SAVA network. The communication would then be delayed by the collection of a large enough batch, but this might not be an issue with a message board etc or any other non-real time application.

Certain countries might have laws that require all service providers (even providers of anonymity services) to store all information that could identify the communication of a certain user. In such situations, it could be possible to split the SAVA network and have one or more servers reside in a different country with less restrictive laws. In that situation, even if the law required the service provider to hand over the SAVA internal server with all used keys residing in that particular country, it would still not break anonymity, as it would be necessary for the law to also acquire all information stored on the SAVA internal server residing in the other country(ies).

The key is placing the different SAVA internal servers in different countries with different laws. All of these countries would have to cooperate in order to obtain the information about what user sent what message, even if all SAVA servers store all keys used in every batch.

Then of course, there could also be raid protection placed on SAVA servers, such that if one of the servers goes offline, all other servers delete their private cryptographic keys, and wipe away any data that could be used in tracing the communication. This would however not abide to the law, if the law explicitly states that service providers needs to store all information.