What are the benefits of lattice based cryptography? Previously we visited the benefits of elliptic curves for cryptography. Lattice based cryptography is starting to become quite popular in academia. The primary benefit of lattice based crypto is the resistance to quantum algorithms. Are there other benefits to lattice based crypto? For example, speed, ciphertext/key sizes, etc?

Post-quantum security:  As you note, quantum attacks are not known to break lattice-based cryptosystems.  But some other proposals like McEliece, as well as most symmetric primitives are not known to be poly-time breakable on a quantum computer.
Security from worst case assumptions:  In security proofs for cryptosystems we typically assume that some problem is hard on average or more precisely hard to solve for random instances drawn from some particular distribution.  For example, we may assume that factoring a product of two random primes cannot be done by a poly-time algorithm.  While this is usually safe, it is in principle possible that someone will find an efficient factoring algorithm that works often on random instances but not on all instances.  Lattice-based cryptography does not suffer from this drawback:  Those schemes are proven secure assuming that lattice problems are hard in the worst case, meaning they are secure as long as no one can find, say, a poly-time algorithm for approximating shortest vectors in every lattice, not just random ones.  This is a huge theoretical advance, but determining exactly what it will mean in practice is difficult for me to say.
Efficiency improvements:  I'll be a little sheepish on this point, but it's often noted that lattice-based schemes have a parallelizable structure that may make them faster in certain contexts.  This is because the algorithms involved are usually simple matrix multiplication with relatively small modular arithmetic (i.e., not cryptographic-sized numbers).  However, my understanding is that implementations of lattice-based schemes would have larger keys, and I'm also not aware of any studies that definitively compare lattice based schemes to traditional schemes.
New primitives:  We only know how to build fully homomorphic encryption from lattices or from very similar techniques.  There is a ton of potential here, and we have no idea how to build such things from factoring or other traditional assumptions.


if using cbc+hmac dealing with small size of data(less than 128bit) , will it cause any problem? if use AES-cbc,HMAC-SHA256, and there is some txt needed to be enc, and I divide this txt into small packages with variable length, then enc them. some of these package can be less than 128bit. Is this still secure? will it cause any problem?

If the MAC'ing is done right (after the encryption) and if you pad the CBC data correctly there's no security risk. Howver changing to CTR or even better to GCM would be better, as both don't operate on whole blocks and GCM even provides authentication.


How to create a decentralized secret ballot among a small group of people? A small (< 100) group wants to implement an election. For that, each participant must vote in one of N candidates. After everyone has voted, they must be able to determine a winner; yet, nobody must be able to determine the vote of someone else. There is no trusted third party. You can assume there is a public list of public keys.

Is there a cryptographically secure way to solve this problem?

Electronic voting schemes constitute a big area of cryptographic research. The problem is complicated and multifaceted, and there are still no end-to-end secure schemes that provide desirable properties like verifiability and coercion resistance and that have good usability and performance for a large number of voters. See for example this survey from 2017 for the state-of-the-art. One scheme with implementation that's relatively popular is Helios (website)
 (Usenix paper, 2008), which foregoes coercion resistance, and instead mostly focuses on auditability in the case of malicious voting machines.

Ignoring implementation-related security and just focusing on the underlying cryptographic techniques, perhaps the simplest method for such a small election with the number of voters $n < 100$, would be to use a linear secret sharing scheme, e.g. Shamir's. In Shamir's scheme, we may share a secret value $s$ in some large enough finite field $\mathbb F$ among $n$ players by selecting a uniformly random polynomial $f \in \mathbb F[X]$ of degree at most $t$ such that $f(0) = s$, and sending the value of $f(i)$ to player $i$. The parameter $t$ determines how many players are needed to reconstruct a secret from the shares: given $t+1$ players, they may jointly reconstruct $s$ by using Lagrange interpolation on their shares, but at most $t$ players obtain no information about the secret.

Suppose the parties have access to pairwise secure channels, and can be trusted to follow the protocol exactly, and not cheat by for example submitting a faulty vote. Each voter $V_i$ records their vote as a vector $\mathbf x_i = (x_{i1}, \dots, x_{iN}) \in \mathbb F^N$ where $x_{ik} = 1$ if $V_i$ wants to vote for candidate $k$, and $x_{ik}=0$ otherwise. Of course, only one element in $\mathbf x_i$ is allowed to be 1, and the rest should all be 0. $V_i$ then secret-shares their vote with all the other voters (e.g. using packed secret sharing [FY92] if $N$ is small enough, or if need be sharing each coordinate in the vector separately). Let $[\mathbf x_i]_j$ denote the share of voter $V_j$ for the secret vote vector $\mathbf x_i$ of $V_i$.

Every voter $V_j$ now has $n$ shares $[\mathbf x_1]_j, \dots, [\mathbf x_n]_j$. Since Shamir's scheme is linear, the players may add their $n$ shares to obtain a valid share of the total election result $\mathbf x_1 + \dots + \mathbf x_n$. Hence, they may jointly reconstruct this value, and determine the election's winner.

A similar result to this may be obtained using additively homomorphic encryption (which Helios uses), and distributed key generation and threshold encryption. Of course, in this scheme voters can easily cheat without being detected, by for example setting $x_{ik} = 2$ and $x_{ik'} = -1$, and more machinery is needed to make this work in the actively secure case, but I hope it gives a rough idea.


What key length is required to keep simple keyed "hash" secure? In a previous question, I described a particular keyed "hash" that mapped a 5-digit input code into a 5-digit output code. It used a 8-bit key which is very insecure - more than 99% of the time, you can infer the key given a single input/output code pair.

I put "hash" in inverted commas as although it has something in common with a hash, it always has an equal input and output length, and it is certainly not secure in anyway.

The input code to output code mapping is not one-to-one. It is possible for an output code to come from several input codes. A given input code only maps to a single output code.

Let's ignore the specific algorithm in the previous question and assume something secure has been developed.

The two most important security properties are:

The attacker should not be able to predict the output code when only given the input code.
The attacker should not be able to derive the key given multiple pairs of input/output codes.

I suspect this means that there are $100000^{100000}$ potential mappings between the input and output codes - essentially limitless. They key length cannot be limited by this constraint.

Does this mean that the key length should obey the normal "long enough to prevent brute forcing" rules that most current encryption does, and should be 128 bits or longer?

What you want is a pseudo-random function family from the set of 5-digit numbers to itself. As you found out, the total number of such functions is $10000^{10000}$, which is quite a lot.

Contrary to what Thomas said, most of them are not "crap" – a randomly selected function from this space is as secure as we can have. Unfortunately this would mean a key of size 10000 · 5 decimal digits (i.e. around 166096 bits, i.e. 20 KB), which is a bit impractical.

So we need a smaller key, and still a secure selection from the whole space, which just looks like a random selection. That is known as a pseudo-random function family (PRF) ("indexed" by the key). The "looks like random" can be formalized with some indistinguishability criterion, but from that your two criteria follow (each of them allows an easy distinguisher).

The key size should still be big enough to not enable brute-forcing – this nowadays practically means a 128 bit key.

Smaller key sizes might be possible, if you limit the number of queries an adversary can make, but I would not build my security on this – there shouldn't be a problem to store an 128 bit key per device (if one can store secrets there at all).

Of course, the construction of your PRF should be done in a way that doesn't have any inherent weaknesses, like the crap which was used in the example of your previous question.

Using $HMAC(key, input)$ with a secure hash function (like SHA-2), followed by an output transformation which produces five decimal digits, looks like a secure way to build this. As the input has a fixed length and actually fits together with the key in one input block of the hash function (for most crypto hashes), using a simple $H(key || input)$ should work, too.


Why avoid custom HMAC implementations like the following? H (o_pad || H (i_pad || m, static_salt), static_salt)

Where the Hash algorithm used is SHA512-crypt: https://www.akkadia.org/drepper/SHA-crypt.txt

What if an attacker knows the o_pad, i_pad, the static_salt, and the final HASH but not the message... it's potentially possible obtain the message (other than just brute-forcing it) using this custom implementation?

You need to be clear about the interface and security goals of what you're trying to achieve, vs. those of HMAC.  This passage of your question seems to state your security goals:

  What if an attacker knows the o_pad, i_pad, the static_salt, and the final HASH but not the message... it's potentially possible obtain the message (other than just brute-forcing it) using this custom implementation?

But that's neither the interface nor the security goal of HMAC:

Interface: MACs are secret keyed functions; they take a key and a message as argument, where the message may or may not be secret.  You're describing something that takes a message and no key; it's not the same interface!
Security goals: MACs expect the key to be a secret random value, and allow (but not require) the message to be non-secret; the goal is to resist forgery of message/tag pairs.  In your construction, on the other hand, you're assuming that messages are secret, and that an attacker who knows every other value (o_pad, i_pad, the static_salt, and the hash result) must not recover the message.

So you're asking us to do an apples-to-oranges comparison.  And in addition, the goal that you have in mind—inability to recover the message for an attacker who sees all the other values—is already a goal of SHA512-crypt.

I hope this isn't too harsh, but what you're doing basically is adding some extra complexity on top of SHA512-crypt that doesn't do anything to further the goal that you've set for it, and superficially resembles HMAC.


Vigenère cipher: Security when key length and plaintext length are the same I have read the Vigenère cipher is secure as long as the key length is the same as the length of the data to be ciphered.

Is this true when the same key is used multiple times?
In such cases, after how many uses would the key be considered insecure?

Forming my comment into an answer:

If the key has the same length as the message and is used only once, it is basically a One-Time-Pad. This means, that in theory you can match any ciphertext to any plaintext with $a key$. If this key has to match certain criteria (e.g. be a word of a certain language), the information theoretic aspect will be lost. It depends on the actual keyspace if this is a problem.

However, the re-usage is more tricky, because all security is lost in Vigenere once a key is reused. If you have two ciphertexts created by the same key, you can just combine them and have the key eliminated. Then you are left with the combination of the two plaintexts, which is easy to deal with by using frequency analysis.


Crypto-period for keys used in PRF I am wondering about the crypto-period for keys used in pseudo-random functions.

For example, let's say I am using HMAC-SHA256 with a secret key $K$.

After how many computes do I have to update $K$?

You don't need to change the key at all in terms of it being "overused". The only reason to change a key is when you use it beyond the bounds given in proofs of security. You have to look this up, but if you are using HMAC-SHA256 with a 256-bit key then you can go on for about $2^{128}$ computations, which you will never every do.

Having said that, the reason to replace keys is because of the fear that they may be stolen by adversaries breaching your network. This has nothing to do with crypto, but is related to other risks.


EC Schnorr signature: multiple standard? I'm working on some EC-Schnorr signature code.
Reading various papers on that, it seems EC-Schnorr is not standardized as
well as ECDSA.

For example, I found two main differences in two main actors specs (also found other minor variants in other papers);

according to BSI Schnorr signature is computed as:

$k$ a random
$Q$ = $kG$,
$r = Q_x$
$h = H(M \mathbin\Vert Q_x)$
$s = k − h \times d \mod n$
Output $(h, s)$

and according to libsecp256k1:

$k$ a random
$Q = kG$,
$r = Q_x$
$h = H(r \mathbin\Vert m)    = H(Q_x \mathbin\Vert M)$
$s = k - h \times d \mod n$
Output $(r, s)$.

Difference are located in:

step 3 : order of data to hash
step 5 : value to return

Of course, signature verification algorithm differ a bit according to that.

So, I wonder:

if there is specification more standard than another?
in case of several standards how to choose one?
what about interoperability?
what about security (for eg: $H(Q_x \mathbin\Vert M)$ is better than $H(M \mathbin\Vert Q_x)$ in my opinion)?

Adding to other answers, I note that both schemes are related to (but clearly different from) those standardized in ISO/IEC 14888-3:2016 (non-functional preview):

The BSI's EC-Schnorr original specification was similar to ISO/IEC 14888-3's EC-SDSA-opt, standing for Elliptic Curve Schnorr Digital Signature Algorithm optimized version, except that EC-Schnorr outputs $H(M\mathbin\|Q_x)$ but EC-SDSA-opt outputs $H(Q_x\mathbin\|M)$.
ISO/IEC 14888-3 also defines EC-SDSA which outputs $H(Q_x\mathbin\|Q_y\mathbin\|M)$.
The BSI's current specification now matches the definition of EC-SDSA in ISO/IEC 14888-3.
The question's libsecp256k1 (possibly matching this source) is similar to ISO/IEC 14888-3's EC-FSDSA (where the F stands for full), except that libsecp256k1 outputs (and later hashes) $Q_x$ where EC-FSDSA uses $Q_x\mathbin\|Q_y$. It follows that EC-FSDSA has a significantly larger signature than libsecp256k1 does (for $b$-bit security it is $6b$-bit, rather than $4b$-bit).

There are more variants related to libsecp256k1. A comment links to BIP-Schnorr.

Summary of the schemes discussed:
$$
\begin{array}{l|rllr}
\text{scheme}&\text{public}&\,\,\,\text{ first}&\,\,\text{ second}&\text{sign. }\,\\
&\text{key }\,\,&\text{component}&\text{component}&\text{size }\,\,\,\\
\hline
\text{[Sc91]}&-d\,G&H(Q,M)&k+d\;h&b+2b\\
\text{EC-SDSA}&-d\,G&H(Q_x\mathbin\|Q_y\mathbin\|M)&k+d\;h&2b+2b\\
\text{EC-SDSA-opt}&-d\,G&H(Q_x\mathbin\|M)&k+d\;h&2b+2b\\
\text{EC-FSDSA}&-d\,G&Q_x\mathbin\|Q_y&k+d\;H(Q_x\mathbin\|Q_y\mathbin\|M)&4b+2b\\
\text{EC-Schnorr old}&d\,G&H(M\mathbin\|Q_x)&k-d\;h&2b+2b\\
\text{libsecp256k1}&d\,G&Q_x&k-d\;H(Q_x\mathbin\|M)&2b+2b\\
\text{BIP-Schnorr}&d\,G&Q_x&k+d\;H(Q_x\mathbin\|\text{Pub}\mathbin\|M)&2b+2b\\
\end{array}
$$

$M$ is the message to be signed.
$G$ is the group generator.
$k$ is the secret drawn by the signer (randomly or pseudo-randomly) at each signature.
$Q=k\,G=\underbrace{G+\ldots+G}_{k\text{ terms}}$.
$Q_x$ (resp. $Q_y$) is the $x$ (resp. $y$) component of $Q$ as a bytestring.
$b$ is the intended security in bits; the group size $n$, $Q_x$ and $Q_y$ are about $2b$-bit.
$H$ is the hash function, and $h$ is the result of the hash, often also the signature's first component. For $\text{[Sc91]}$, $h$ is $b$-bit wide, and the input of $H$ combines an unspecified fraction of $Q$ with $M$. In other schemes, $h$ is  $2b$-bit wide.
$\text{Pub}$ is the public key. Including it in the hashed data simplifies (perhaps strengthens) security reduction in a multi-users configuration.
An implicit $\bmod n$ is omitted for the signature's second component.
Conversion between integer and bistring is omitted (though essential for interoperability).

$\text{[Sc91]}$ is Claus-Peter Schnorr, Efficient Signature Generation by Smart Cards, in Journal of cryptology, 1991; refer to this for an exposition and more bibliography.

In $\text{EC-Schnorr}$, the signature's first component is an ASN.1 integer rather than a bytestring.

$\text{EC-Schnorr}$ (resp. $\text{EC-SDSA}$, $\text{EC-SDSA-opt}$, $\text{EC-FSDSA}$ ) have registered Object IDentifier 0.4.0.127.0.7.1.1.4.3 (resp. 1.0.14888.3.0.11, 1.0.14888.3.0.13, 1.0.14888.3.0.12).

These 7 schemes are incompatible; Andrew S. Tanenbaum's "The nice thing about standards is that you have so many to choose from" is an understatement!

ETSI's Electronic Signatures and Infrastructures (ESI); Cryptographic Suites TS 119 312 V1.2.1 (2017-05) states:

  For interoperability reasons only one version (EC-SDSA-opt) from the EC-XDSA Schnorr variants defined in ISO/IEC 14888-3 is selected by the present document. EC-SDSA in the optimized version has the small advantage
  of minimal data transfer for smart cards.

but that rationale works only against EC-FSDSA as far as I can tell. If the Smart Card itself computes or verifies the signature, as it should, what's transferred is the signature, which is $4b$-bit in both EC-SDSA-opt and EC-SDSA.

Hashing $M$ first is a specificity of EC-Schnorr; my guess is that it was designed for constrained environments like Smart Cards, where it allows offloading the bulk of the hashing of $M$ externally (also, on a multicore CPU, that allows hashing $M$ in a separate thread). As long as the hash is secure, it should not make any difference in security.


AES, CMAC and "3 pass authentication protocol" Explained I am struggling a bit to understand how authentication systems are properly used in NFC tag environments so I'm posting this thread to clarify some concepts.(In advance, this is not my field, so suppose gaps of knowledge)

AES : Its a ciphering algorithm based on symmetric keys (both sides have same key, being it able to cipher and decipher texts), the message is chunked in 10 parts, then each one will be encrypted (using the master key, and several transformation are made on a matrix), to be all joined together afterwards.

This standard is only for encryption and doesn't apply any authorization feature.
I suppose that only the master key is used to accomplish the ciphering.

(I read some thread talking about "key generations" from the master key, so maybe they are used in the algorithm instead? Is it not related at all? )

Its used to avoid "Passive attacks".

CMAC : Gaps here, I don`t know which of them it is. (or maybe none it is)

-It is an authentication protocol(MAC) where the input is a ciphered text (AES previously used), being able to satisfy the authentication part. (Data integrity covered by AES algorithm).

-It is an authentication protocol(MAC) but the input is a chopped plain text( no AES previously used), then the protocol is used along with some AES blocks to satisfy the authentication and integrity parts.

An explanation of what CMAC is will be truly welcome. ( I starting to think that is related somehow with Encrypt-then-MAC procedure)

It is handy to avoid some "Active attacks".

3-Pass-Mutual-Authentication : I think it is just a procedure when the CMAC it is used on both sides but many times, validating both devices if all of them give an positive response. ( I know that there more steps but I'm trying to figure out the general view of this)

Any sort of information to clarify all of this will be grateful, I know that all of them are related but I cant see the overall view.

AES is a block cipher. It permutes (maps) input blocks to output blocks of 16 bytes. The permutation that is used depends on the key. AES must be used in a mode of operation such as CBC to be able to be offer confidentiality of dynamically sized messages. CBC is commonly used in Smart Card environments. CBC offers confidentiality against (passive) eavesdroppers.

AES-CMAC is a MAC based on AES-CBC. It offers data integrity and authenticity. It is an alteration on CBC-MAC to make it secure for dynamically sized messages. Reusing CBC is of course a good idea for embedded environments (rather than relying on HMAC where the hash is commonly implemented in software).

Sometimes you may only need a MAC when communicating with a Smart Card or tag (e.g. when sending commands without confidential data). In that case you may directly perform MAC over the plaintext (command). If the data needs to be confidential then usually encrypt-than-mac is used instead of mac-then-encrypt. This is especially important when it comes to avoiding CBC padding oracle attacks.

Usually the message protection is performed by session keys, derived from the master key.

3-pass mutual authentication may also use encryption or MAC. There is not a single 3-pass protocol, there are multiple protocols that either use the master key or derived (session) authentication key, encryption or MAC. This protocol is used for entity authentication rather than message security. The (random) values used within this protocol that precedes message exchange may be used to derive the other session key(s).

Per session there may be as much as 6 session keys per pair of entities (e.g. card and reader). One key may be used for entity authentication, one for encryption and one for MAC. These 3 keys can have two sets: one for sending and one for receiving (authentication) messages. These may be generated directly or indirectly from one master key. Quite often the master key is however used directly for entity authentication, removing two keys from the list of session keys.


security of using digital signature as key derivation material I want all keys in my iOS application to rely on the Secure Enclave for security as the iOS keychain becomes insecure on jailbroken devices. Currently, the Secure Enclave currently only supports generation/storage of EC and RSA keys. I'm considering the following design for indirectly using the Secure Enclave to store symmetric encryption keys, but want to validate its security:

On application initialization, generate an asymmetric EC key K in the Secure Enclave.
Use it to sign the device UUID (or some other constant), yielding signature S.
Derive encryption key E = KDF(S)
Use encryption key E to encrypt items in the local database. (E itself is not stored anywhere.)
On any subsequent application start, re-derive S and E and use E to decrypt the local database.

Edit: as @zaph pointed out, the Secure Enclave protects the entire Keychain. The distinction lies in that some keys can be generated in the Secure Enclave (curve p256 EC keys and RSA keys) and some can't. Those that can, enjoy a higher level of security as their private keys cannot be exported from the Secure Enclave. It is those keys that I'm interested in exploiting to indirectly protect other keys/data.

I'm sorry, but chances are this doesn't work.

The reason is of course that ECDSA signatures are usually fully randomized, meaning that there's randomness introduced in between the private key and the final signature. If you're looking at an ECDSA specification, the relevant value usually is called $k$.

What you'd rather need would be an RSA encryption / decryption keypair or an ECDH keypair. In this case you'd just store an encrypted key as a file or something and let the secure enclave decrypt it at each startup and keep the key in RAM. The downside being of course if an attacker can extract it from memory this application's security is screwed. If you have a static ECDH key pair you'd just store a public ECDH share and statically derive the key each time and use it as suggested.

If you have to use signatures though, you need to find a deterministic one that is offered by the enclave and use it as proposed in your question.
This can include ECDSA if it follows any standard for deterministic ECDSA (like RFC 6979) and this can also include deterministic RSA signatures (e.g. usually the older signature standards).

Bottom line: As long as you use some (intermediate) value in the key derivation which directly relies on a hardware-backed key (in a deterministic way), chances are this will be secure.
An example of how not to do such a derivation is given in Android's FDE setup (with the counter-example for a good derivation would be iOS actually)


How do I create an effective salt? Background

I have recently started to get into web development and thus I have been creating databases for users.

After some research, I discovered that password encryption is not password hashing.
My next spell of learning was that I needed to add salts to my passwords to make them harder to crack.
For this I implemented a hard-coded salt to the start of all my passwords; I later learned that actually the salts should all be different, otherwise they are just peppers.

Storing data

I created a table in my database that stores the passwords and the salts (maybe a question for a different day, but I am not sure where to store the salts).

The passwords are hashed using MD5 and then stored. (There is not really a reason as to why I chose MD5 and if it is better to use another one then I will.)

I currently use a PRNG to create the salt upon registration to the site. The salts are not hashed and are simply just stored in a separate field to the password.

Question(s)

What is a good salt?

Assuming someone gains access to the databases. They would see a series of MD5 hashes and then a series of random numbers and letters (8 bytes currently).

I understand that the question may appear open-ended.
Would I need to hash my salts (that sounds weird to me), create longer salts, or do something else?

If you are using random numbers and letters (upper and lower case) for salts, you can make the assumption that each character has 5.9 bits of entropy, assuming they are actually random.

A salt needs to be unique enough never to be used by 2 users that happen to have the same password. Rather than calculate some value on how likely that is, it is better to just assume that every password entry in the database should have a unique salt. It is even better that EVERY salt used for password hashing on every system on earth be unique.

Lets assume that 8 billion people all have a password for something. I have about 100 passwords for various systems, we can round to 33 bits of uniqueness for people, and 7 bits for password count.

Thus you want a bare minimum of 40 bits of uniqueness, which requires an 80-bit salt. The current trend is to simply use a 128-bit random number, making the chance of a salt collision "cryptographically unlikely" for the near term. 80 bits would require random 14 alphanumeric characters. 128 bits requires 22 characters.

There are generally standard methods on combining the salt and hashed password into a single string, I would suggest using that format. And of course, there will be mentions that a cryptographic hash is unsuitable for passwords and you need a memory/compute hard Password Based Key Derivation Function or a Password Hashing Scheme, which is true; read How to securely hash passwords? or one many posts on this site on how to properly choose and utilize one of these. MD5 is not even close to suitable for this, or any secure system.


Is there a zero knowledge proof to show an encrypted blob is the key for a given public key? Let's say I have a private key x  with a corresponding public key y. If I encrypt x as E(x), is there a zero knowledge proof I can use to show that E(x) contains the private key for y?

I am assuming that you are encrypting $x$ under a different public key from potentially a different scheme. The answer is yes, since every language in NP can be proven in zero knowledge. The question, of course, is can this be done efficiently. The answer to that depends on the schemes involved.


Comparable or partially homomorphic public key derivation for signatures? Are there any public key signature schemes that can be compared blindly or partially homomorphically based on the private key without knowing the private key?

Example: let's say I derive a public key from a private key via a secret seed "haha this is a secret 1001" I then derive another public key from another secret seed "haha this is a secret 1002". I then want to be able to compare the public keys lexicographically without knowing these seeds.

Being able to compare the signatures would also work, but only if they can somehow be compared on the basis of the seed used to create the key pair and not on the basis of what is signed.

A little bit of a weird question, but my intuition says this might exist.

Edit:

I thought of one solution but it's not very efficient. You could mandate a mapping from sortable secret keys to integers from say 0 to 2^32-1 (32 bits). Then you could just brute force search by hashing the secret keys until a public key is found whose least significant bits correspond to the ordinal. You'd then store the number of hashes required alongside the public key and compare on the public key's least significant N bits.

A more efficient way would be preferable of course.

Edit #2:

A description of the real world application might be helpful.

I want to be able to secure a distributed decentralized database against naive sorts of denial of service attacks and collision attacks.

It's a system that maps plain text keys to plain text values but uses a hash of the key to encrypt the value and then indexes entries by a hash of the key. This means the plain text key is hidden and the value is unreadable to anyone who doesn't know what key they're looking for. (This is itself not an uncommon technique in e.g. shared deduplicating storage systems.)

BUT... even if someone doesn't know the key they could add bogus entries with what looks like the same key (its hash) and nonsense values. This would pollute the cache with junk, waste space and bandwidth, etc.

So I have this idea. Take the plain text key, hash it, use part of the hash to encrypt the value, and then use another part of the hash to derive a key pair. Then sign the entry with that key pair. Use the public key from this pair as the encrypted key in the key/value store.

This means that you cannot create valid entries for a given plain text key unless you know that key, but you can prove that you know a key without revealing it.

The sortability desire comes from a desire to support ordered iteration queries in this cache. So I want people who know a given plain text key to be able to ask for it and all the keys greater than it or all the keys between two values. This is basically blind/homomorphic querying but with this weird twist as described above.

If I understand you correctly, you want that given $\mathit{pk}, \mathit{pk}'$, one can publicly decide whether or not $\mathit{sk} < \mathit{sk}'$ (lexicographically) for the corresponding secret keys.

Such a signature scheme would inherently be insecure.
This is because given your public key $\mathit{pk}^*$, anyone would be able to run a binary search to find the underlying secret key $\mathit{sk}^*$.

For example, the attacker could choose $\mathit{sk} = 10000000$, compute the corresponding $\mathit{pk}$ and then run the lexicographic comparison on $\mathit{pk}$ and $\mathit{pk}^*$ to find out whether or not your key $\mathit{sk}^*$ starts with a 1. If so, checking whether $\mathit{sk}^*$ is still lexicographically larger than $11000000$ can be done similarly and reveals the next bit, etc.

After $n$ comparisons (assuming n-bit secrets), the secret key is revealed. Of course, this also generalizes to larger alphabets.


Has GMAC mode a future outside GCM? Once gcm has been implemented for providing both encryption & authentication solution , it appears obvious to consider that such implementation can also provide (if required by new user) a Mac based authentication only service via using only Gmac instead of complete Gcm.

So I wondered if GMAC could or not be proposed as a serious / valid standalone Mac mode of operation when compared to well-known  Hmac or Cmac.

I fear the answer is NO for at least the two following reasons but as not being a crypto expert I would be interested to get more pertinent advices:

first GMAC requires use of an iv which is not the case for other Mac modes; this induces additional overhead on the messages to carry associated iv (subset)
then GMAC is known to fail (ghash key disclosure) if iv uniqueness constraint is not strictly respected.Hmac or Cmac do not know that kind of risk as not using any iv

Is it correct or am I too much pessimistic about GMAC in regard with robustness & performances of Hmac or Cmac widely recognised modes ?
.

To answer your question: yes, GMAC does have niche applications where it performs better than either HMAC or CMAC; however it might not make sense for you.

First of all, you are correct in that GMAC requires an IV, and bad things happen if a particular IV value is reused; this rather rules out GMAC for some applications, and is a cost even for applications that can live with it.

So, is there any application for GMAC where makes it worth paying this cost?  Well, yes, there is; in hardware, you can do GMAC considerably faster than either HMAC or CMAC.

Suppose you have a stream of data running at 40,000,000,000 bits per second (that's 40Gbps) at we need to integrity-check.  Even with aggressive hardware, neither HMAC nor CMAC can deal with data at that rate; GMAC can.

Now, that's very much a niche application; I rather suspect you'll never run into that yourself.  I believe you're really asking "does GMAC make sense for what I'm doing"

Well, I can't give you a direct answer to that (partially because I'm not exactly certain what it is you're doing).  However, it would appear to me that the only thing that GMAC buys you in your scenario is simplicity (you have a GCM implementation; GMAC is GCM with everything going into the AAD) and consistency (that way, the encryption and authentication-only cases are handled similarly). I cannot tell whether these advantages are worth the costs of GMAC, or whether you're better off tossing in (for example) an HMAC implementation to handle the authentication-only case.


How can I map arbitrary group elements to unique integers without using Hash functions? Let's say, I have a group $G$ of large prime order $p$. A set $S$ consists of $n$ random elements chosen from $G$. Without using a collision resistant hash function $H$, how can I map elements of $G$ to unique elements in $Z_p$?

I thought about it before posting here. But, finding discrete logarithm for an arbitrary group is hard, right? In theory, it'd satisfy the requirement of collision resistance, but inefficient.

I don't really know the structure of the group beforehand. What I am essentially trying to do is, I am trying to figure out a generic means to map public key ($PK$) of a Public Key Encryption system to $z \in Z_p$, such that a third party can be convinced about the co-relation between the $PK$ and $z$ without revealing $PK$ but $z$ and some form of proof-of-knowledge. Hash functions, due it inherent nature of pre-image resistance, seems unsuitable.

The order of every element $g$ of a group $G$ divides the order of the group ($p$).

Since $p$ is prime, every $g\in G$ has order $1$ or $p$. Only the identity element $e$ satisfies the first case, so every $g\in G\setminus\{e\}$ is a generator of $G$, i.e., $$G = \{g^0,g^1,g^2,\cdots,g^{p-1}\}.$$

This allows defining a bijection $$\begin{array}{cccc}\varphi:&\mathbb Z_p&\rightarrow& G\\&n&\mapsto&g^n\end{array}.$$

If you can find $\varphi^{-1}$, you're done.


Theoretical security of bit rotation for encyption This is a theoretical question.

I have a idea, encryption by bit rotation in byte.
Do not know if something like this already exists.

General concept is:

First n bytes is rotated to left or right by value between 1 and 7.
Next n bytes are rotated to left or right by different value between 1 and 7.
While keeping n between 1 and 10 bytes.
and so on till the end of the of encrypted file.

The value of n and a list of shift values for each block make up the key.

My intent is to use this for a symmetric encryption between computers over the internet.

How breakable/hackable should something like this be?

Let's say the plaintext is English text (or some language that uses the basic latin characters), encoded in Unicode.  That means each byte represents one character, and because of the quirks of Unicode, the basic latin characters and typical punctuation marks all have a zero for the most significant bit.

To attack your scheme, an attacker would look for runs of bytes which all had zeros in the same bit-position.  A run of $x$ bytes all with a zero in the $y$ bit-position would suggest both a length for $n$ (something less than or equal to $x$) and also a rotation amount (the amount required to move the most significant zero bit to position $y$).

Even if the plaintext is not English text, or doesn't use Unicode, in your scheme the ciphertext still trivially leaks the parity of each byte of the plaintext (i.e. how many 1's and 0's are each byte), which is an atrocious amount of information to leak.  For a cipher to be secure, the ciphertext shouldn't leak any information whatsoever about the plaintext, except for its length.


In RSA, what is faster attacking "d" when plaintext is known, or factoring when M is unknown? I'm aware of two methods to attack RSA:

Brute force factoring, where no plain text is available
Brute force (1/e) mod φ where the plain text is available as described here

Question

Given an optimized solution either in a generic CPU, or custom ASIC, what operation is more likely to take longer, and/or consume more resources?
How close to polynomial time will each of these calculations be?

Ideally I'd like to get a perspective on the number of operations on each approach, and the computational cost.  So far it appears that for key length n, option two is 0.5 * n operations.

My goal is to determine if the computational effort per try is less than what was done in this paper, or any other effort to crack RSA.

Brute-forcing the private key is never a good idea with RSA, unless the key was generated with a $d$ of an artificially (very) low size. Indeed, for a 1024-bit modulus, factorization is said to have cost about $2^{77}$ (barely feasible, and estimated, with high memory-related costs, so it has not been actually done yet) while a normal $d$ will have length about 1024 bits, for a completely unrealistic exhaustive search cost.

Moreover:

If you find out $d$, then you can easily compute the factors of $n$, so even your brute-force attack on $d$ is, in fact, a factorization attack.
A brute force attack on the smallest of the factors of $n$ is a poor factorization algorithm (known as "trial division"), but still ludicrously faster than brute-force on $d$ ($2^{512}$ against $2^{1024}$).
This is public-key cryptography. Everybody can encrypt, using the public key. So the attacker can have billions of known pairs plaintext/ciphertext if he wishes so, by simply generating then. Chosen ciphertext attacks are another matter, though.
You missed an exponential. When a key has length $x$ bits, brute-forcing it has cost $2^{x-1}$, not $x/2$.
Polynomial complexity has very little relevance to the subject. Complexity classes are about asymptotic behaviour, when operand sizes grow toward infinity. This tells things about performance on a specific operand size only empirically (usually, polynomial algorithms are reasonably fast with values of "practical size", but there is no theoretical basis for why it should be so).

The usual pointer for estimates on key strength is www.keylength.com which contains nice comparators and a lot of pointers.


Chosen-plaintext attack Let F be a block cipher with 128-bit block length. Consider the following encryption scheme for 256-bit messages: to encrypt message $M=m_1∥m_2$ using key $k$ (where $|m_1|=|m_2|=128$), choose random 128-bit $r$ and compute the ciphertext $r∥F_k(r)\oplus m_1∥F_k(m_1)\oplus m_2$. Is there any strategy that leads to a valid chosen-plaintext attack?

No.
This isn't secure by itself against chosen-plaintext attacks.

This mode is known as plaintext-feedback mode (PFB) and referenced for example in here.
The next point is this mode hasn't received much attention in the cryptographic literature, whereas other modes (CFB, OFB, CBC, CTR) have.

Two notes:

Don't roll your own crypto.
Never use such modes if anyhow possible. Use established authenticated encryption modes like GCM.

Beyond that even CFB would be a better choice as you need to store the plaintext to encrypt the next ciphertext in this case, whereas for CFB you only need to store the (safe?) ciphertext.

The first attack proceeds as follows:

Suppose your want to decipher $m_2$ and are allowed to view $C_2$ and to choose $m_1$ and to learn the corresponding $C_1$. Suppose further you know $r$, which is required for the valid recipient to know for decryption.

Now choose $m_1=r$. Observe that the following relation will hold $E(r)\oplus m_1 = C_1$. Now extract $E(r)$ by calculating $E(r)=m_1 \oplus C_1$ which is possible since you know $m_1$ and $C_1$.

Now observe further that $E(m_1)\oplus m_2 = C_2$ is equivalent to $E(r) \oplus m_2 = C_2$, as $m_1=r$ holds. As you already calculated $E(r)$ above you can now calculate $m_2$ via $m_2 = C_2 \oplus E(r) = C_2 \oplus m_1 \oplus C_1$.

There's a second attack that decrypt a given message $(r_X||C_X||C_Y)$.

Decrypting $C_X$ goes as follows. Choose your message to be encrypted to be $(m_1=r_X||m_2)$ for an arbitrary $m_2$.You'll get the ciphertext (from the oracle): $(r_1||C_1=m_1\oplus E(r_1)||C_2=m_2 \oplus E(m_1))$.Now oberve that the following holds: $E(m_1)=E(r_X)=m_2 \oplus C_2$.Therefore you can construct $m_X = C_X \oplus E(r_X) = C_X \oplus m_2 \oplus C_2$.Ask for encryption of $(m_X||m_3)$ now.You'll get $(r_2||C=m_X \oplus E(r_2)||C_3=m_3\oplus E(m_X))$.Use this to calculate $E(m_X)=m_3 \oplus C_3$ and finally $m_Y = C_Y \oplus E(m_X) = C_Y \oplus m_3 \oplus C_3$.

You now successfully retrieved the message $(m_X||m_Y)$ using a chosen-plaintext attack.

Hence this scheme is broken.


Why is the tweak length 64bit in BPS FPE algorithm? In the algorithm for BPS Format Preserving Encryption

Is this tweak always the same length (64bit)?

Why did they choose the length 64bit for the tweak?

From the paper:

  We denote by $f$ the number of output bits of the internal function $F$

and

  We first divide the 64-bit tweak $T$ into two 32-bit sub-tweaks $T_L$ and $T_R$

plus

  We denote by $L_i$ (resp. $R_i$) the left (resp. right) branch value after application of round $i$.

with the note

  Note that because of our restriction on the number of input $s$-integers, we always ensure that each branch can be coded on a $(f − 32)$-bit word.

Right, so now look at part of the definition of the cipher:

  ...

  $L_{i+1} = L_i \boxplus F_K ((T_R \oplus i) \times 2^{f −32} + R_i) \mod s^l;$

  ...

although multiplication is represented by a dot instead of $\times$. Similarly for the calculation of the state $R_{i+1}$ of course.

Basically, this shifts the tweak to the most significant 32 bits, leaving the rest for the state. Now $F$ can be AES, HMAC-SHA-2 or TDES. TDES has a block size of 64 bit. If the tweak size was 128 bit then there would not be any space left for $R$ or $L$ that make up the internal state.

So the tweak size is such that repetition of the tweak is unlikely and it can still be used efficiently when the encryption uses a 64 bit block cipher. If the tweak would be larger the construction would become less efficient, up to the point that the scheme would not work at all.


Optimal bandwidth cost for Oblivious RAM Goldreich and Ostrovsky show that any ORAM algorithm must have bandwidth cost $\Omega(logN)$, where $N$ is the total number of blocks outsourced. This is in Theorem C of this paper. But they didn't give any proof for this Theorem. Is there other papers that have proved this theorem?

See Theorem 6, page 38-39..

Also, this lower bound ignores any ability of the "RAM" to perform computation. Typically, there are two application scenarios for ORAM:

1) A literal processor communicating along a literal CPU bus to a literal stick of RAM

2) A client communicating over the internet to a cloud server

In the latter case, it makes sense for the cloud server to provide computational resources to 'speed up' the oblivious simulation. Two works have shown how to achieve $O(1)$ bandwidth overhead (pushing the $\Omega(log(N))$ requisite overhead onto the server's computation instead):

1) http://eprint.iacr.org/2014/153.pdf

2) http://eprint.iacr.org/2015/005.pdf

Also, very recent work based on program obfuscation allows you to implement a "one-shot ORAM," i.e. ORAM with a single round of communication and asymptotically succinct space/time for the server:

1) http://eprint.iacr.org/2015/388.pdf

2) http://eprint.iacr.org/2015/406.pdf


Discrete logarithm on Montgomery curve twist So for some context I've been playing with some crypto challenges, and ran into this interesting problem.

There's Montgomery curve C, point A on its twist with small-ish order K (so K*A == 0), and B which is some unknown multiple of A.

We can brute force every value from 0 to K by generating C.ladder(A,i) and checking if it equals B. That's uncomfortably slow even for fairly small K.

I tried to optimize it a bit, generating 0*A, 1*A, 2*A, 3*A, ... by chained differential addition (from A, 6*A, and 7*A we can generate 8*A quite quickly etc.) instead of running ladder for each value, and that's about 10x-ish faster, but still not great and $O(K)$.

So if we worked on something which allowed arbitrary point addition, we could just pick U about sqrt(K) generate a bunch of baby step values 0*A, 1*A, 2*A, ..., (U-1)*A, a bunch of giant step values B+0*(-U*A),B+1*(-U*A), B+2*(-U*A) etc., and then when we find a collision between those two series by hashing then we know that k*A == B-j*U*A, so B=(k+j*U)*A, solving it in $O(\sqrt K)$.

Now awkwardly Montgomery curves don't allow arbitrary addition or subtractions, so what's the options?

convert to some other kind of curve (like Weierstrass) for sake of the attack, then convert result back? The obvious formulas are for points on the curve, not on its twist, but there could be some way to convert it?.
is there's some clever way to use differential addition to get those series I want?
is there some other algorithm which doesn't suffer from this problem?

So I guess I'll answer myself as I finally figured it out:

twist of a curve is a curve - all possible curves with same A are isomorphic to either $B=1$ (your base curve if you use usual curve) or $B=-1$ (your twist curve) curve, so just pick whichever and be consistent.
every Montgomery curve has Weierstrass curve. Your choice of B matters which one you get exactly, but end result will be same.
(not every Weierstrass curve has Montgomery curve, but you already have equivalent curve - your original twist curve)
so map points to Weierstrass form, get logarithms by baby step giant step (or other fast algorithm), map points back, for each prime on the twist you'll get two answers ($k$ and $-k$).
if there are z primes, then $2^z$ answers can be reduced to just $4$ in $O(z)$ steps with Chinese Reminder Theorem and filter.
that doesn't give you unique answer, but very small number ($4x4$ in my case), so you can just test them all.

I didn't completely follow the math for factors of $2$ and duplicate primes. Twist order has factor of $2^2$ and then only unique primes, that's presumably why it's been $4$ not $2$.

I'm sure there's some way to optimize higher powers of same prime, I just didn't need it.


Calculating the average key search time of DES I am trying to understand how to calculate the average key search time given a specific scenario:

Suppose we have a program that uses standard DES with 56 key bits, and we can test 10^6 keys per second.

The key consists of 8 characters, a simple concatenation of the 8 ASCII characters yielding 64 = 8*8 key bits. With the permutation PC-1 in the key schedule, the least sig. bit of each 8-bit character is ignored, giving us 56 key bits.

What is the size of the key space if all 8 characters are randomly chosen 8-bit ASCII characters?

My thought is the key space is 2^56.

How long does an average key search take?

We can test 10^6 keys per second, and 2^56 is roughly 7.2058 x 10^16. I don't know if this is proper way to do it, I estimated ~3 seconds.

I am assuming there is much more accurate mathematical approach but I'm not familiar with it, could anyone shed some light on this for me?

At $10^6$ keys per second, going through the full $2^{56}$ keys would take $2^{56}/10^{6}$ seconds, or about 2200 years; the average time would be half that (or a bit more than 1000 years).

Obviously, this is longer than anyone would be willing to wait.  So, why is DES considered brute-forcible?  Well, we can throw considerably more resources at the problem than a single laptop...


X9.62 Multiplying an elliptic curve point by a number I'm currently trying to implement ecdsa and the first problem i met --  multiply an elliptic curve point by a number.

As far as i understand X9.62 gives some recommendation for doing it but i haven't managed to find anything.
It would be great to see some program like algorithm.

P.S.
Any help is appreciated. Sorry for my English and thanks.

Well, you understand that Elliptic Curves define an operation on points we denote as +; that is, if $A$ and $B$ are two (not necessarily distinct) points, then $A+B$ is a third point (which will be distinct unless either $A$ or $B$ are the 'point-at-infinity'). If $A$ and $B$ are the same, the operation is usually called doubling instead of addition.

Now, by "multiplying an elliptic curve point by a number" (or point multiplication), what we mean is adding the point to itself the specified number of times.  That is:

$\displaylines{kG =}{\underbrace{G + G + G + ... + G}}$

where exactly k $G$'s are added together.

Now, the naive implementation is just to perform $k-1$ point additions; however, because the integers we're multiplying by are huge, this is not practical.

However, point addition is associative (that is, $(A+B)+C = A+(B+C)$, that means that we can use less than $k-1$ additions; for example, to compute $8G$, we can note that:

$2G = G + G$

$4G = G + G + G + G = (G + G) + (G + G) = 2G + 2G$

$8G = 4G + 4G$

and hence we've computed $8G$ using only three additions.

One straight-forward (decent, but nonoptimal) method to do this (assuming, of course, that you have already implemented the Elliptic Curve addition function) is to use the binary addition method; just note that the Wiki article talks about 'multiplication', while you're doing addition; that is merely a difference in syntax.


What is the most secure way to let Alice "input" her private key, transfer it to the server and decrypt the message? What is the most secure way to let Alice "input" her private key, transfer it to the server and decrypt the message? (Then destroy the private key on the server)

Every connection is using SSL.

Exmeple:

Alice log on the website. She have a new "email" from Bob. (Everything is stored in a database, it's not an actual email)

To read it, she needs her private key. How can she do that ? Upload it? Copy the key in a textbox and click submit? (May not be pratical for Alice) Store it on the server (Hugh security issue) ?

(And is it possible to suggest me some keywords please? I'm not used to Crypto.Stackexchange Thank you)

What you really want to do is never have any unencrypted data leave the server in the first place. What should be happening is that the server is sending the encrypted message to Alice, who then decrypts it locally.


Prepending random data to encrypted file If random data is prepended to a file encrypted with GNUPG's symmetric encryption, how may an attacker find out if the input file is deliberately corrupted or the passphrase is wrong?

If it is not easily ascertainable from which offset the actual encrypted data starts, is there any added security in always prepending a few  kilobytes to an encrypted file in order to slow down an attacker?

In order to brute force the file, the attacker must start at offset 0 and  continue incrementally with all likely passphrases until he gets a match.

Here I am assuming perhaps incorrectly that there is no magic number easily identifying the file as encrypted with GNUPG or there is no validation of the contents without trying the passphrase.

But if this assumption does not hold for GNUPG, what about Truecrypt's file based containers?

So far I know Truecrypt file based containers are indistinguishable from random noise, but the size gives away that the file may be a Truecrypt container.

If my TC container's actual size is 5 GB, and I prepend it with 5 GB random data, will brute forcing by an attacker who doesn't know the real offset be too costly?

Is there any design reason why crypto software do not let the user select the start offset for decryption in addition to the passphrase?

It's much easier to add a cost factor to the key derivation from the password than to add a lot of data to an encrypted container. See the PBKDF's PBKDF2, bcrypt and scrypt for more information, or see this Q/A for GPG. In general, an iteration to derive the key is of course much more efficient than adding overhead at the start of the file.

If a key with an entropy over 100 bits and if there are no vulnerabilities in the encryption routine (this is likely true for GPG / CAST5) then brute forcing the key is already not possible, and the measly amount of time required to  decrypt a small amount of data is not much of an additional deterrent.

Note that CBC mode encryption can be decrypted from any location in the ciphertext, as long as the previous ciphertext block is available. As for the trick with the truecrypt volumes (wasn't that software deprecated?), how would you know as a legit user where to start reading/writing?


Homomorphic Encryption with Addition and Exponentiation Is there any homomorphic encryption scheme which supports addition and power over cipher text ? Paillier is close but it supports addition and multiplication with a constant.

I am getting an output like this:

1 0 1 0 -1 1

My goal is to make -1 positive by any means. As it will encrypted so I cannot know if it is -1 or 1. This (similar) output is being generated by subtracting binary streams.

For example:

101101 -- A1
111001 --- A2
----------------------------
2 1 2 1 1 0 2 --- A+A2=A3
----------------------------
1 0 1 0 -1 1 ---- A3-1

A1 and A2 bits can be replaced to any other integers.
Also, can I perform AND operation in additive mode ?
Please note that this question is link to my previous question

Primary Objective:
To be able to check any of following

How many same bits occurs that is 1ns in A1 and A2 in the same position
How many zero bits on the same positions in A1 and A2
How many different bit locations in A1 and A2

(In most generality..) you're looking for fully homomorphic encryption (FHE), which supports homomorphic addition and homomorphic multiplication. To compute a plaintext's exponentiation, you would run the repeating squaring algorithm (using homomorphic multiplication), to generate an (evaluated) homomorphic ciphertext containing the input-plaintext's exponentiation.

Craig Gentry gave the breakthrough construction of FHE in 2009. Since then, there's been a titanic volume of work improving the techniques, and multiple surveys are available by searching online.

An open-source implementation of modern FHE -- the library HElib by Shai Halevi and Victor Shoup -- can be found here: https://github.com/shaih/HElib


How can I find the order of the group that an elliptic curve is defined over? I have a Weierstrass elliptic curve ($y^2=x^3+a \times x+b \mod p $)

How can I find the order of the group itself? I have seen Mathematica has a GroupOrder[] command and WolframAlpha will do it for me, but how can I do it myself, mathematically?

The modulus, $p$, will be a large prime number, say 256 bits or more.

The number of points on the curve $|E({\mathbb F}_p)|$ is defined as $|E({\mathbb F}_p)|=p+1-t$ where $t$ is the so called trace of Frobenius. Using Hasse's theorem one can bound $t$ as $|t| \leq 2\sqrt p$, which gives you an estimation for the number of points for $E({\mathbb F}_p)$.

Now you could use a naive algorithm and simply run through all elements of ${\mathbb F}_p$ and determine whether they satisfy the curve equation to count the points, which however requires exponential time.

Luckily, you can use polynomial time point counting algorithms, such as Schoof or SEA, which allows you to efficiently determine the number of points on the curve.

For cryptographic use you will typically require a prime order subgroup $G$ of $|E({\mathbb F}_p)|$ such that the value $h = \frac{|E({\mathbb F}_p)|}{ord(G)}$, the so called cofactor, is a small integer (typically $\leq 4$).


Does the Paillier system remain secure if it is used to encrypt only binary values, i.e. {0, 1}? Is there any security compromises if the Paillier system was used to encrypt only binary message in {0, 1}? i.e., plaintexts are either 0 or 1.

No, there are no security compromises; the Pallier system remains secure.  Both messages are in the supported message space and as Paillier encryption provides IND-CPA security you are safe when doing this.


Problem with LLL reduction on truncated LCG schemes I am struggling to apply Freize et al. paper to break a truncated LCG.

A truncated LCG is a pseudo random generator that outputs the $n$ leading bits $y_i$ of $x_i$, where $(x_i)$ is such that $x_{i+1} = \alpha \cdot x_i + \beta\mod M$, and $\alpha$ is an integer, coprime with $M$. The first state $x_1$ is unknown.

The objective is to break the LCG, ie, from one or several consecutive outputs, find the current state $x_i$. We suppose that $\alpha$ and $M$ are known, and $\beta = 0$ (and is known too).

The theory

The paper states (pages 5 and 6) that their method solves systems of modular equations of the form $\displaystyle\sum_{j=1}^k a_{ij}x_j \equiv c_i \mod M$, for all $i \in \{1, \dots, k\}$.

Deriving a lattice from the vectors $a_i$, the authors apply LLL to find a small basis, of vectors $w_1, \dots, w_k$.
By multiplying the matrix $\begin{pmatrix} w_1\\ \vdots\\ w_k \end{pmatrix}$ on the right by $x$, they derive a new set of equations: $\displaystyle\sum_{j=1}^k w_{ij}x_j \equiv c_i' \mod M$, for all $i \in \{1, \dots, k\}$.

Here, i guess that the $c_i'$ are just obtained from the $c_i$ by multiplying (on the left) by the same matrix that allowed us to go from our original basis to our reduced basis.

Now, if the $c_i'$ are small enough, the equalities actually hold on $\mathbb{Z}$ and we can solve them: we have effectively solved the system.

In practice

Now, the authors talk a bit more about their method for a LCG, part 3 (pages 11 and 12).

We have the relations $\alpha^{k-1} x_{1} - x_k = 0$ (edit: fixed typo), so I guess that it implies that all my $c_i$ are $0$.

Now, if I want to obtain my $c_i'$, I should multiply $c$ on the left by the same matrix as the one used to change the basis of the lattice. But, given that I have $c = 0$, I should have $c' = 0$ as well, so we don't need to compute this matrix.

Furthermore, my lattice is, as descibed by the paper,
$$L = \begin{pmatrix}
M & 0 && \dots & 0\\
\alpha & -1 &0& \dots & 0\\
\alpha^2 & 0 & -1 & \dots & 0\\
\vdots &&&\ddots & \vdots\\
\alpha^{k-1} & 0 & 0 & \dots & -1\\
\end{pmatrix}$$
which is trivially nonsingular, and as such, the only solution to $Lx = 0$ is $x = 0$, which is obviously wrong.

Even worse, this method does not use the $y_i$, but it obviously should at some point, so I guess I'm missing something.

My questions

(Most probably related)

In my case, what are the $c_i$, and do I really obtain the $c_i'$ from them by the basis change?
How are the $y_i$ supposed to take part in this method?

The lattice basis $L$ generates every point that is a solution to the congruence $a^{i-1} x_1 - x_i \equiv 0 \pmod{m}$. By definition, the reduced basis $B = \mathsf{LLL}(L)$ also generates the same solutions; it just has shorter vectors.

Now suppose we have a set of outputs $\mathbf{y} = y_i$ of the generator, which correspond to the most significant bits of the LCG multiplied by $2^s$, and we want to find $\mathbf{z} = z_i$ such that $\mathbf{y} + \mathbf{z} = \mathbf{x}$, where $\mathbf{x} = x_i$ is the reconstructed state. The key insight here is
$$
\begin{align}
& L \cdot \mathbf{x} \equiv 0 \pmod{m} \\
& B \cdot \mathbf{x} \equiv 0 \pmod{m} \\
& B \cdot \mathbf{x} = m \cdot \mathbf{k} \quad \mbox{(for some unknown $\mathbf{k}$)}  \\
& B \cdot (\mathbf{y} + \mathbf{z}) = m \cdot \mathbf{k}  \\
& B \cdot \mathbf{z} = m \cdot \mathbf{k} - B \cdot \mathbf{y}
\end{align}
$$

Now, because the coefficients in the reduced basis $B$ are small, we know that all the elements of $\mathbf{k} = k_i$ are small, and we can further deduce $k_i = \lfloor (B \cdot \mathbf{y})_i / m \rceil$, or in other words, $m \cdot k_i$ is the closest multiple of $m$ in relation to each element of $B \cdot \mathbf{y}$. Once we know $k_i$, this is a simple matter of linear algebra. Here's an example with Sage:

p = previous_prime(2^32)
a = randint(2, p)
s = randint(0, p)
X = [ a^(i+1) * s % p for i in range(4) ]
Y = [ x - x % 2^16 for x in X ] # high 16 bits
Z = [ x % 2^16 for x in X ] # low 16 bits (secret)

L = matrix([
    [  p,  0,  0,  0 ],
    [a^1, -1,  0,  0 ],
    [a^2,  0, -1,  0 ],
    [a^3,  0,  0, -1 ]
])

B = L.LLL()

W1 = B * vector(Y)
W2 = vector([ round(RR(w) / p) * p - w for w in W1 ])

Z_ = list(B.solve_right(W2))
print Z_
print Z


What's the proper way of fitting hash digest to encryption scheme? I would like to know what is the proper way of fitting the hash digest to the prime in which the encryption scheme operates. regardless if the bits of the hash digest is larger or smaller than the prime.

I've read that the Cramer-Shoup uses a universal one-way hash function, but didn't state what it is. Wikipedia says its just a property, and  with that I plan on using SHA256. My simulator uses smaller bits for presentation purposes and the larger bits digest of SHA256, I have a problem on how to fit it in. I've read in some forums to use mod on in, is this the proper way ?

A universal one-way hash function (or UOWHF), also known as a target-collision-resistant (or TCR) hash function, is a randomized hash function $H_r(m)$ with the following security: If an adversary commits to a message $m$, then upon being challenged with a random $r$, the adversary cannot find a distinct message $m' \ne m$ such that $H_r(m) = H_r(m')$.  (More details, background, history, and references on UOWHF/TCR, particularly in signature applications.)

Any collision-resistant hash function is obviously also TCR, but TCR is a much weaker security property—much all major ‘cryptographic hash functions’ like SHA-256 including broken ones like MD5 are generally conjectured to exhibit TCR in prefix-hash form $H(r \mathbin\| m)$ and in HMAC form $\operatorname{HMAC-\!}H_r(m)$, but in the off chance that they don't (the Merkle–Damgård construction does not necessarily preserve TCR), there's a generic construction called RMX from Halevi and Krawczyk's research program on randomized signatures, which was standardized by NIST in SP 800-106.  If you like more modern flavors, you could use keyed BLAKE2 or KMAC128 too, since TCR—and the slightly stronger eTCR—was an explicit design goal for SHA-3.

If you want a smaller digest, just truncate the hash function; if you want a larger digest, the easiest way is to use an XOF like the SHA-3 function SHAKE128 or like BLAKE2x.  You could also use SHA-256 in ‘CTR mode’, yielding $H(r \mathbin\| m \mathbin\| 0) \mathbin\| H(r \mathbin\| m \mathbin\| 1) \mathbin\| H(r \mathbin\| m \mathbin\| 2) \mathbin\| \dotsb$, provided you make sure to pad it unambiguously, or use a standard (if somewhat more complicated) construction like HKDF-SHA256 or MGF1 of PKCS#1.


reconstructing data on a noisy channel? I have an interesting situation where I have a block cipher and a noisy channel.  The interesting thing is that I happen to know much about the data.  The cipher is a balanced Feistel network, and for the sake of this question, let's just assume that the block size is 32-bits.

What I know:

The key.
The original data has the format of xx000000, where xx is 8 bits of data.

It then gets encrypted.

The issue is that after encryption, I'm losing 2 bits of the 32-bit stream.  I have plenty of computer power, so I guess that I could just do a comparison because I know that xx will be 0-255 and run some sort of algorithm for flipped bits.

My question is: does anyone know if someone has looked into this before?  I feel that something like this would be a nice math project.

Use a Hadamard code via the fast Walsh Hadamard transform, it can correct up to $2^{n-2}$ errors for block length $2^n$ and is also locally decidable so you may not need too many code word coordinates.


Classification of a stream cipher How would one classify a stream cipher that is neither synchronous, nor self synchronizing?  I would have thought asynchronous, but from all the sources I can find, asynchronous is synonymous with self synchronizing.

The internal state of the cipher is initialized by a key and initialization vector.  The internal state is modified depending on the current internal state, and the previous byte of plain text.  The cipher does not synchronize after a fixed number of bytes.  Error propagation is unlimited, so corruption of one byte of cipher text makes the rest of the message undecipherable.

I would like to know the correct classification of the cipher.

Thanks to @otis and @kodlu, who suggested the terms synchronous and additive.  Searching those terms has led me to this article, describing nearly exactly what I am after.  On page 244, I paraphrase, where W [...] is the running key sequence and where we allow W, to depend both on the secret key (as is customary) and on [all prior bytes of] the plaintext.  This article is heavy on the maths and terms, so many of which I need to look up to understand their meaning.  I am still working through the terms used in the article, which is why I have not proposed an answer to my own question.  I am posting this source, because it might be helpful to someone with a stronger background to answer the question.

Logically I think that should also be a synchronous stream cipher. The word refers to the fact that the keystreams must be synchronized between the encrypter and the decrypter to allow decoding. With anything other than a self-synchronizing cipher that is the case.

However, that does not mesh with existing usage. You will find many texts (example) saying that with synchronous stream ciphers the keystream is independent of the plaintext and ciphertext. So you should definitely not use that term.

Asynchronous is not very good either, for the reason you mention, but you will find it used to describe such ciphers (e.g. Helix here, pdf). So that is probably more understandable than calling them synchronous, even if it too can be confusing.

If you need to write about it, I would avoid the issue and just call it a stream cipher with a plaintext-dependent keystream. You can say that it is not self-synchronous if you need to make that distinction.


Are there any valid, and person readable, checksums possible? We've been trying to produce a valid, and pretty, MD5. Something that has repeating digits, or spells a word, or something. It's probably more difficult than spelling out the dictionary on a calculator whilst standing on your head on top of a washing machine on ship in the arctic but it's always made me curious.

Are there any valid, and person readable, checksums possible? Or would the checksum itself typically prevent this?

I'm preparing for some massive flames to blow my way.

You could use a concept similar to the PGP Word List, which attempts to make a binary-representative equivalent of the NATO Phonetic Alphabet, so that fingerprints (bytes) can be expressed vocally in a relatively unambiguous way.

Of course, using per-byte words in the case of MD5 means you need 16 words to produce a readable checksum, which may be potentially excessive for your purposes. If this is the case, your options are to either truncate the hash (which is potentially not ideal from a security perspective) or to invent additional words codepoints to shorten the total string length. Unfortunately the required dictionary size raises geometrically ($2^n$) whereas the length only reduces linearly, which means you need much larger dictionaries to get slightly shorter strings. You'll have to work out a balance point.


Where did Martin Hellman acknowledge Ralph Merkle's contribution to public-key cryptography? I am trying to find the article to reference when discussing the Diffie-Hellman key exchange.

According to Wikipedia Hellman said that

  The system...has since become known as Diffie–Hellman key exchange. While that system was first described in a paper by Diffie and me, it is a public key distribution system, a concept developed by Merkle, and hence should be called 'Diffie–Hellman–Merkle key exchange' if names are to be associated with it. I hope this small pulpit might help in that endeavor to recognize Merkle's equal contribution to the invention of public key cryptography.

Any ideas where I can find the original article? The wikipedia link itself is dead.

The source of that quote is:

Hellman, M. E. (2002). An overview of public key cryptography. IEEE Communications Magazine, 40(5), 42-49.

That paper is currently available here:

http://professor.unisinos.br/linds/teoinfo/hellman.pdf

Here's the complete quote:

  The system I called the ax1x2 system in this paper has since become
  known as Diffie-Hellman key exchange. While that system was first
  described in a paper by Diffie and me, it is a public key distribution
  system, a concept developed by Merkle, and hence should be called
  "Diffie-Hellman-Merkle key exchange" if names are to be associated
  with it. I hope this small pulpit might help in that endeavor to
  recognize Merkle's equal contribution to the invention of public key
  cryptography. Space does not permit an explanation of the quirk of
  fate that seems to have deprived Merkle of the credit he deserves, but
  a quirk it is.


Benefit of using random key in Shamir's Secret Sharing I am implementing Shamir's Secret Sharing, and I find that in (t,n)-threshold scheme, the shares are just using 1,2,3...,n as the key to form the shares (i,f(i)).

For example, I want share "Hello", and the shares look like this:

01-AAAA1,AAAA2,AAAA3,AAAA4,AAAA5
02-BBBB1,BBBB2,BBBB3,BBBB4,BBBB5
03-CCCC1,CCCC2,CCCC3,CCCC4,CCCC5
04-DDDD1,DDDD2,DDDD3,DDDD4,DDDD5

where 01,02,03,04 are the keys and XXXX are the values.

But I find in some place, people are using random numbers as the key. And I want to further extend it by using different key for each character.

For example, the secret is still "Hello", but the share are become:

x1-AAAA1, x2-AAAA2, x3-AAAA3, x4-AAAA4, x5-AAAA5
y1-BBBB1, y2-BBBB2, y3-BBBB3, y4-BBBB4, y5-BBBB5
z1-CCCC1, z2-CCCC2, z3-CCCC3, z4-CCCC4, z5-CCCC5
u1-DDDD1, u2-DDDD2, u3-DDDD3, u4-DDDD4, u5-DDDD5

where x1,x2,x3,x4,x5 are random and distinct.

In this way the only disadvantage is that we need more store space for keys, and it may takes more time to generate random number.

But I wonder whether there is some advantages? Say, Safety issue?

I am new with computer security, hope to get answer. Thanks!

There are no security advantages to evaluating the polynomial at random places instead of sequential. The information theoretic security proof of Shamir secret sharing does not depend on the evaluation points being chosen in any specific manner.


Is there an asymmetric One-Time-Pad? Is there something like a perfect asymmetric crypto-algo? Is there proof that there must be one or not. From a logical point of view it seems to be possible to design such algorithm if your keysize is high enough.

And please a mathematical solution and not some quantum-cryptography.

Thanks in advance

No there isn't. First, OTP is private-key encryption scheme. Second, Asymmetric key is public-key encryption and No public-key encryption scheme can ever be perfectly secret. This is because the public-key (used for encryption) is available to everyone and is related to the secret-key in some way. Thus, a certain negligible amount of information is leaked. However, this leakage implies it isn't perfectly secure. So, No such thing as asymmetric OTP.


Are EdDSA algorithms encoded by ASN.1 DER standards? Is it required, or widely practiced to encode a EdDSA signature as a ASN.1 Sequence? Why or why not? How should you encode a EdDSA signature? I cannot find mention of DER or ASN in the EdDSA RFC.

However, there is mention in the ECDSA RFC (as expected)

  An ECDSA signature is a pair of integers.  In many protocols that
     require a signature to be a sequence of bits (or octets), it is
     customary to encode the signature as an ASN.1 SEQUENCE of two INTEGER
     values, with DER rules.

An EdDSA signature is a sequence of bytes encoded according to the EdDSA paper or its extension to more curves, or according to RFC 8032, which should be treated as opaque by callers.

In particular, for an instance of EdDSA on a curve $E$ over a field $\mathbb F_p$ of order $p < 2^{b-1}$:

A public key is a $b$-bit bit string $n \mathbin\| \underline y$ encoding a point $(x, y) \in E$, where $n$ is 1 if $x$ is ‘negative’ and 0 if not, and $\underline y$ is the little-endian encoding of the least nonnegative integer residue of $y \in \mathbb F_p$.  Here ‘negative’ means $\underline x$ is lexicographically larger than $\underline{-x}$.
A signature is a $2b$-bit string $\underline R \mathbin\| \underline s$ encoding a point $R \in E$ like a public key, and a $b$-bit integer $s$ in little-endian encoding $\underline s$.

There is no ASN.1 formatting involved here.  Forget ASN.1, and forget ECDSA.  They are evil things.


Is forward secrecy overhyped or necessary? Forward Secrecy, also perfect forward secrecy, gives assurance about session keys even the private key is compromised. This is achieved by generating a random key per session without using a deterministic generation algorithm.

In this answer's quote Thomas Pornin says

  Reusing encryption keys goes contrary to forward secrecy, and forward secrecy has become a selling point (though it's a bit overhyped, in my opinion).

While almost everywhere forward secrecy is recommended why it should be a bit overhyped?

Since I am at the source of the original quote, I might as well respond...

Technically, forward secrecy is overhyped because it is recommended almost everywhere. In some contexts it makes sense and is a valuable property. In many other contexts it makes less sense and, while harmless from a security point of view, it may induce performance-related issues.

Suppose that you have two systems that want to exchange confidential data over an insecure network. This is the context of the TLS protocol. At some point, the data is encrypted with a secret key derived from the key exchange protocol used in the TLS handshake. Forward secrecy is a property that says, basically, that once the exchange is over, the involved parties do not keep around all the secret information that allows decryption: the data has been encrypted on the sender side, and decrypted by the recipient, and nobody (except the attacker, of course!) needs to decrypt it again, so the encryption key can be dropped. If the TLS client and server use the RSA key exchange, then the protocol is not forward secure, because the RSA decryption key is the server's long-term key, the one corresponding to the public key in its certificate, and these will live for as long as the certificate itself, usually months or years.

In that kind of situation, a non-forward secure key exchange can be exploited by an attacker if that attacker records the encrypted session, then later on manages to compromise the server to obtain the decryption key. This assumes that the attacker can somehow predict that he will be able to compromise the server at a later date, making it worthwhile to record encrypted sessions. This is not plausible in many situations involving for instance Web browsers talking to Web servers: the attacker simply does not know when or if he will get access to the server, and if the goal is to obtain (for instance) credit card numbers, the attacker won't bother to record previous sessions; he will simply plunder the server-side database, to which he will have good access once the server itself is compromised.

Notwithstanding, there are real-life contexts where forward secrecy is very useful; one of them is typically end-to-end encrypted messaging systems. A number of characteristics make forward secrecy highly desirable for such systems:

The total amount of encrypted data is much smaller than typical Web-browsing sessions (let's face it, today's Web is fat). Moreover, in some messaging systems, encrypted messages are already recording by servers that manage the transport, for asynchronous delivery.
Past conversations are interesting to attackers, and not necessarily made available to them by virtue of compromising one device (it depends on the system's strategy with regards to caching).
Group conversations imply group management, and, in particular, ability to exclude a former group member from subsequent discussions; this inherently calls for some sort of forward secrecy ("ratcheting", in modern parlance).

My point, though, is that the blanket recommendation for forward secrecy everywhere is "a bit overhyped", because it is, indeed, a blanket, universal recommendation, marketed as an unavoidable requirement in all cases, while many situations don't need it.

On the negative side, here is a performance issue that arises from the universal forward secrecy requirement. In TLS 1.3, forward secrecy is systematically enforced. Suppose that some small embedded device must talk to a server with mutual, certificate-based authentication. Suppose also that elliptic curve cryptography is used. The following will happen:

The client generates a new ECDH key pair, i.e. a random integer a, and the curve point aG (for the conventional generator G).
The server also generates a new ECDH key pair (b, bG).
The server signs its public part bG; the signature will use ECDSA or EdDSA, and involves computing a multiplication of the generator G with a new scalar.
The client verifies the signature. This requires performing two point multiplications, one of these points being the generator G, the other one being the server's public key. There are tricks to somehow mutualize some operations in these two point multiplications, but they need extra RAM, always a scarce resource in embedded systems.
The client terminates the ECDH key exchange by multiplying the received bG with a.
The server also terminates the ECDH key exchange by multiplying the received aG with b.
The client must itself compute a signature with its own long-term key, so that the server knows that it talks to the right client.

In total, the client will need to compute five point multiplications, three of which being on the conventional generator G (since that generator is known in advance, this allows some optimizations, so multiplications of G are a bit less expensive than multiplications by a freshly received point). The cost on the server is similar.

Now, compare that with TLS 1.2. With TLS 1.2, all of the above can be done in about the same way (encoding of messages differs, but the cryptographic result will be the same); this would use an "ECDHE_ECDSA" cipher suite (ECDHE key exchange, signed by the server with its ECDSA private key). However, TLS 1.2 also offers "ECDH_ECDSA" cipher suites, without the final "E" of ECDHE (the one that means "ephemeral"). In the ideal case, what happens is the following:

The server has a long-term EC key pair (b, bG). The public part (bG) is in its certificate, i.e. has been computed at key generation time.
The client also has a long-term EC key pair (a, aG), with aG encoded in its certificate, again a key generation time.
The client and the server send to each other their certificates.
The client computes a(bG) as the premaster secret for the TLS connection (the actual encryption keys will be derived from the premaster secret with some HMAC-based function that also includes the random values exchanged during the handshake).
The server computes b(aG) as the premaster secret for the TLS connection.

And that's it. The client and server now have to compute a single point multiplication each. This is called the "static-static Diffie-Hellman".

The static-static Diffie-Hellman key exchange is not allowed in TLS 1.3, because it is not forward secure. Modern implementations of elliptic curve cryptography are fast, and any decent server can certainly compute five point multiplications for each client without breaking a sweat; a decent x86 CPU can do 30000 point multiplications per second with a single core! However, on the client side, things may differ: a very small embedded system, e.g. an ARM Cortex M0+ clocked at 5 MHz or less (to save power), would need close to one second for each point multiplication. For such a client, a multiplication of the cost by five is certainly not negligible, and can be the difference between "a non-forward secure connection" and "no encryption at all because the forward-secure exchange is too expensive". Regardless of how much indispensable you think forward security is, lack of encryption is certainly not an improvement over non-forward-secure encryption.

In that sense, TLS 1.3 is more hostile to small embedded systems than TLS 1.2, and this is for the sake of mandatory forward security, even in cases where it does not bring any actual advantage. This is what I call "a bit overhyped".


Are there other digital certificate formats than X.509? Hi I am a little new to security, but in researching digital certificates it seems the only format people describe is X.509.

Are there other formats? If so what are they and where can I find information on them?

Although x.509 is the standard for PKIs with CAs, different certificate formats have been defined for the other 2 major PKI approaches:

SPKI has defined its own certificate
format , still (forever?) in
draft status.
Web-of-Trust models usually use the OpenPGP certificate format defined in RFC2440

RFC4212 "Alternative Certificate Formats for the Public-Key Infrastructure Using X.509 (PKIX) Certificate Management Protocols" may also be of interest.


How to detect if a protocol is vulnerable to a replay attack trying to impersonate? I'm having a hard to finding out how I can detect if protocols are vulnerable to impersonation of Alice/Bob by Eves' replay attack! I have an example here:
$$\begin{array}{lclcl}
\mathsf A & \to & \mathsf B & : & \mathtt{Hello}  \\
\mathsf B & \to & \mathsf A & : & B, K_{ab}\{B\}  \\
\mathsf A & \to & \mathsf B & : & A, K_{ab}\{A\}  \\
\end{array}$$
I would think that this is vulnerable to Eve impersonating Bob by adding these steps:
$$\begin{array}{lclcl}
\mathsf A & \to & \mathsf B            & : & \mathtt{Hello}  \\
\mathsf B & \to & \mathsf E(\mathsf A) & : & B, K_{ab}\{B\}  \\
\end{array}$$
Now that Eve has the plaintext of $B$ and the ciphertext of $B$ ($K_{ab}\{B\}$ ), depending on which cipher used she now has $K_{ab}$ with which she can impersonate as Bob to Alice.
$$\begin{array}{lclcl}
\mathsf E(\mathsf B) & \to & \mathsf A & : & A, K_{ab}\{A\}  \\
\end{array}$$

But when I look at protocols such as:
$$\begin{array}{lclcl}
\mathsf A & \to & \mathsf B & : & A, K_{ab}\{N_a\}                    \\
\mathsf B & \to & \mathsf A & : & B, N_a, K_{ab}\{N_b\}               \\
\mathsf A & \to & \mathsf B & : & A, B, N_a, N_b, K_{ab}\{N_a, N_b\}  \\
\end{array}$$
I'm totally lost. Is there some sort of characteristic vulnerability in protocols to which Eve could take advantage which I'm not seeing? I'm sorry if this is a stupid question but I'm new to this.

Notes of the editor:

$\mathsf A$ (resp. $\mathsf B$) is entity Alice (resp. Bob), $A$ and $B$ are their respective identity.
$\mathsf E(\mathsf A)$ means entity Eve impersonating Alice.
$K_{ab}\{A\}$ means encryption of $A$ with a symmetric cipher under key $K_{ab}$ shared by Alice and Bob but initially unknown to Eve.
$N_a$ means a nonce chosen by Alice.
$X, Y\dots$ denotes a reversible concatenation of two or more messages; perhaps plain concatenation if the length of messages is fixed, or concatenation with , as separator after replacing every \ by \\ then every , by \, in the messages concatenated.

In a pure replay attack, Eve acts as a genuine participant to the protocol with respect to the other. Therefore, having passively eavesdropped the protocol:
$$\begin{array}{lclcll}
\mathsf A&\to&\mathsf B&:&\mathtt{Hello}&\ \ \mathsf{[1]}\\
\mathsf B&\to&\mathsf A&:&B,K_{ab}\{B\}&\ \ \mathsf{[2]}\\
\mathsf A&\to&\mathsf B&:&A,K_{ab}\{A\}&\ \ \mathsf{[3]}\\
\end{array}$$
Eve impersonating Alice to Bob can be:
$$\begin{array}{lclcll}
\mathsf E(\mathsf A)&\to&\mathsf B&:&\mathtt{Hello}&\ \ \mathsf{[1a]}\\
\mathsf B&\to&\mathsf E(\mathsf A)&:&B,K_{ab}\{B\}&\ \ \mathsf{[2a]}\\
\mathsf E(\mathsf A)&\to&\mathsf B&:&A,K_{ab}\{A\}&\ \ \mathsf{[3a]}\\
\end{array}$$
where at $\mathsf{[3a]}$ Eve simply replays the value she captured from $\mathsf{[3]}$, and thus passes the implicit test by Bob at step $\mathsf{[3a]}$ that the received $K_{ab}\{A\}$ in the second part of the message deciphers to the $A$ in the first part, that Bob (wrongly) assumes is the identity of the other party.

And Eve impersonating Bob to Alice can be:
$$\begin{array}{lclcll}
\mathsf A&\to&\mathsf E(\mathsf B)&:&\mathtt{Hello}&\ \ \mathsf{[1b]}\\
\mathsf E(\mathsf B)&\to&\mathsf A&:&B,K_{ab}\{B\}&\ \ \mathsf{[2b]}\\
\mathsf A&\to&\mathsf E(\mathsf B)&:&A,K_{ab}\{A\}&\ \ \mathsf{[3b]}\\
\end{array}$$
where at $\mathsf{[2b]}$ Eve simply replays the value she captured from $\mathsf{[2]}$, and thus passes the implicit test by Alice at step $\mathsf{[2b]}$ that the received $K_{ab}\{B\}$ in the second part of the message deciphers to the $B$ in the first part, that Alice (wrongly) assumes is the identity of the other party.

This does not involve finding key $K_{ab}$ from plaintext $B$ and ciphertext $K_{ab}\{B\}$, which would be breaking the cipher, something assumed impossible in a replay attack.

One way to prevent pure replay attack is to make use of nonce, so that just replayed messages won't be accepted. That's the case in this protocol (the question's second one without $K_{ab}\{N_a,N_b\}$ in the last step)
$$\begin{array}{lclcll}
\mathsf A&\to&\mathsf B&:&A,K_{ab}\{N_a\}&\ \ \mathsf{[1]}\\
\mathsf B&\to&\mathsf A&:&B,N_a,K_{ab}\{N_b\}&\ \ \mathsf{[2]}\\
\mathsf A&\to&\mathsf B&:&A,B,N_a,N_b&\ \ \mathsf{[3]}\\
\end{array}$$

Alice choses a nonce $N_a$, sends it enciphered as $K_{ab}\{N_a\}$ as part of $\mathsf{[1]}$, that Bob extracts, deciphers yielding $N_a$ that he sends as part of $\mathsf{[2]}$, allowing Alice to extract and check it against the nonce she has chosen; this proves to Alice that some entity able to use $K_{ab}$ was involved in the exchange; and if Alice can rule out that this entity is herself (say, by not running more than one instance of the protocol at a given time), then that involved entity must be Bob (because there is no other entity sharing $K_{ab}$ and it is used only as the key of a cipher), thus the protocol is immune to impersonation of Bob to Alice running the protocol with Alice's role.

Also, Bob chose $N_b$ in $\mathsf{[2]}$, sends it enciphered as $K_{ab}\{N_n\}$ as part of $\mathsf{[2]}$, that Alice extracts, deciphers yielding $N_b$ that she sends as part of $\mathsf{[3]}$, allowing Bob to extract and check it against the nonce he has chosen; this proves to Bob that some entity able to use $K_{ab}$ was involved in the exchange; and if Bob can rule out that this entity is himself, then that must be Alice, thus the protocol is immune to impersonation of Alice to Bob running the protocol with Bob's role.

Notice that when Bob is a server allowing multiple concurrent connections, Eve can impersonate Alice to Bob. An attack goes as follows:
$$\begin{array}{lclcll}
\mathsf E(\mathsf A)&\to&\mathsf B&:&A,K_{ab}\{N_a\}&\ \ \mathsf{[1a]}\\
\mathsf B&\to&\mathsf E(\mathsf A)&:&B,N_a,K_{ab}\{N_b\}&\ \ \mathsf{[2a]}\\
\mathsf E(\mathsf A)&\to&\mathsf B&:&A,K_{ab}\{N_b\}&\ \ \mathsf{[1a']}\\
\mathsf B&\to&\mathsf E(\mathsf A)&:&B,N_b,K_{ab}\{N'_b\}&\ \ \mathsf{[2a']}\\
\mathsf E(\mathsf A)&\to&\mathsf B&:&A,B,N_a,N_b&\ \ \mathsf{[3a]}\\
\end{array}$$
where

In $\mathsf{[1a]}$, Eve gives any plausible $K_{ab}\{N_a\}$ even though she does not actually know the matching $\{N_a\}$; that can for example be an $\{N_a\}$ captured from a previous session, or (for many ciphers) any random bit string of the same size).
In $\mathsf{[2a]}$, Bob just does its job; Eve does not make the check Alice would have made about $N_a$.
In $\mathsf{[1a']}$, Eve mimics starting another simultaneous connection attempt, but sneakingly supplies $K_{ab}\{N_b\}$ of $\mathsf{[2a]}$ where the convention would be to supply $K_{ab}\{N'_a\}$
In $\mathsf{[2a']}$, Bob just does its job, and correspondingly returns $N_b$ that he has chosen and sent enciphered in $\mathsf{[2a]}$; again Eve makes no check.
In $\mathsf{[3a]}$, Eve uses the $N_b$ conveniently supplied by Bob in step $\mathsf{[2a']}$, and the check Bob makes of that $N_b$ passes.

The above proves the protocol is vulnerable, by exhibiting an explicit attack. Whether it is a replay attack is a matter of taste. Assuming yes: the question asks how this is detected. An answer is: because $\mathsf{[1]}$ and $\mathsf{[2]}$ can be abused to make Bob a decryption oracle under key $K_{ab}$ (that is, something that allows decryption of any message), and in the protocol considered in this section of the answer, the ability to decipher a message is what authenticates Alice to Bob.

As an attempt to prevent the above attack (likely: made for pedagogical reasons), the question's protocol
$$\begin{array}{lclcll}
\mathsf A&\to&\mathsf B&:&A,K_{ab}\{N_a\}&\ \ \mathsf{[1]}\\
\mathsf B&\to&\mathsf A&:&B,N_a,K_{ab}\{N_b\}&\ \ \mathsf{[2]}\\
\mathsf A&\to&\mathsf B&:&A,B,N_a,N_b,K_{ab}\{N_a,N_b\}&\ \ \mathsf{[3]}\\
\end{array}$$
has as a step $\mathsf{[3]}$ such that Alice forms $N_a,N_b$ and encipher it into $K_{ab}\{N_a,N_b\}$, that Bob deciphers and checks against $N_a$ he deduced from $K_{ab}\{N_a\}$ received as part of step $\mathsf{[1]}$, and against $N_b$ he has chosen. That's not a good idea: since Alice makes no extra check, and makes an extra use of $K_{ab}$, it can only make her more vulnerable to impersonation of Bob. And the protocol remains vulnerable to impersonation of Alice to Bob. Proving this is left as an exercise to the reader, but the following might help detect that:

It is not forbidden for a cipher that some public function $F$ is such that $F(X,Y,K\{X\},K\{Y\})$ always deciphers the same as $K\{X,Y\}$, and from a secure block cipher it is easy to construct a CPA-secure cipher with that property, with matching $F$ (including, that ignores its inputs $X$ and $Y$).
Even if we restrict to CPA-secure ciphers without that property, some are malleable (e.g. a block cipher in CTR mode), and that allows Eve to make good use of a passively eavesdropped step $\mathsf{[3]}$.


Advantages/disadvantages of using symmetric encryption function as hash function? Next to the traditional MD5 and SHA-1, other hashing algorithms exist based on symmetric encryption algorithms. An example is the Matyas–Meyer–Oseas construction.

What are the advantages/disadvantages of this approach instead of using traditional hash functions, such as MD5 and SHA-1?

The disadvantage of this approach is that block ciphers are not necessarily designed with this goal in mind. Specifically, AES has related-key problems, and DES completely breaks in Davies-Meyer. In general, block ciphers are not necessarily ideal ciphers and should be used as intended which is as pseudorandom permutations. In contrast, SHA256 and the like were constructed specifically with the collision resistance goal in mind. It doesn't mean that they achieve this goal, but they have a far better chance.


GSW Homomorphic Encryption In GSW homomorphic encryption scheme proposed here. The integers are over $Z_q$ where $q$ is a modulus parameter of the scheme. It is not clearly mentioned in paper if the ordinary representation of $Z_q$ (that is $\{0,1,..., q-1\}$) is used or balanced representation ($\{\lceil - q / 2 \rceil, ..., \lfloor(q - 1) / 2 \rfloor\}$). However, usually in lattice based cryptography a balanced representation is used since random numbers are sampled from truncated discrete Gaussian distribution. My question is, if negative numbers are used (which is the case in the balanced representation) how to perform the Bitdecompose procedure which performs the following:
Let $a \in Z_q$ and $l=\lfloor \log_2^q \rfloor+1$, $Bitdecompose(a)=(a_0, a_1, ..., a_{l-1})$, where $a_i$ is the $i$-th bit of the binary representation of $a$.

However, usually in lattice based cryptography a balanced
  representation is used [...]

Is this true? I'd be interested in seeing some instances in the literature (or implementations) which actually use this representation. In my experience, the literature (such as the paper you linked) assume the ordinary representation of $\mathbb{Z}_q$.

I don't see a practical benefit to using the balanced representation. Random numbers are indeed sampled from a truncated discrete Gaussian centered around 0, and a negative number can easily be added to the value in $\mathbb{Z}_q$. Sometimes this result may be negative, so a $\mod q$ operation needs to be done. But this operation is necessary for whichever representation you use. In the balanced representation, if you add a positive error to $(q-1)/2$ you will need a $\mod q$ operation as well to keep the result in $\mathbb{Z}_q$.

To answer your question, the Bitdecompose procedure can be done by simply adding $\lceil-q/2\rceil$ to $a$ first, which shifts the representation back to normal. Then Bitdecompose is nearly free in practice.


Why have hashes when you have MACs? It would seem to a naive eye that if you have a MAC, you have a hash function: use a key that all the parties know (such as all-bits-zero).

A potential application would be a resource-constrained platform where code size is at a premium, and which needs to implement AES for confidentiality: instead of also implementing SHA-2 for integrity verifications, it could use e.g. AES-CMAC.

Is there a reason not to do this? Is the existence of hash functions alongside MAC due to security? Performance? History?

In general, a MAC with a known fixed "key" is not a secure hash.  That is, you can have a secure MAC (that is, someone without the key, but with a large number of message/MAC pairs, cannot come up with another valid message/MAC pair) that is not collision resistant, or even preimage resistant, if the attacker does know the key.

In addition, you don't have to come up with an artificial example to demonstrate it; AES-CMAC is not even preimage resistant if you know the key.  This is easy to demonstrate; pick an arbitrary message that is a multiple of 16 bytes; then it is straight-forward to find the specific 16 bytes you need to append to make the CMAC come out to the 16 byte value you picked.

In addition, this isn't specifc to AES-CMAC; MACs based on univeral hashes also have this property.  In fact, the only MACs (in common use) that I can think of which is actually secure as a hash with a public key would be HMAC (which, of course, is designed around a secure hash function).

Now, you mention the use of a hash as an "integrity verification"; if you're checking the integrity of a transmitted message (and use a secret key), a MAC is a perfect choice for this operation (and, in fact, a hash function might not work as well).  However, if you need something which is actually collision resistant (e.g. as a part of a signature scheme), then a MAC with a fixed key may have serious problems.


How many messages before Sphincs(+) becomes insecure? How many messages would it take until the success probability of a forger becomes $1/2$? $1/4$?

For all SPHINCS-like constructions, security is slightly more complicated to analyze than for say a hash function. For SPHINCS we do not only have two dimensions as for hash functions where we got the effort an attacker spends and the corresponding probability. For SPHINCS there is a third dimension, namely an 'attack effort' - 'probability' pair occurs only with a certain probability. This latter probability slowly increases with every signature an adversary sees. However, parameters are selected such that the probability that an 'attack effort' - 'probability' pair occurs times the inverse of the effort needed to achieve probability 1/2 under this pair is below a targeted value (this is what is considered the full attack complexity). E.g., for SPHINCS-256 this target value is $2^{128}$ considering quantum adversaries. This is not entirely true, as I said that the probability of occurrence increases with each signature. Hence, for every target value, there is a threshold for which it will be passed. Therefore one has to decide for how many signatures that target must not be passed. For SPHINCS-256 the target holds for $q = 2^{50}$ signatures. For SPHINCS+ the target holds for $q = 2^{64}$ signatures. If a user does more than $q$ signatures the attack complexity starts to decrease. Actually, the SPHINCS and SPHINCS+ specification/paper give formulas for the bit-security. You can answer your question yourself as follows:

In the case of SPHINCS-like constructions, a bit security of $b$ bits corresponds approximately to a success probability of $2^{-b}$. Just fix $b$ accordingly and solve for the number of signatures $q_{sign}$ in the formula.