Verifying signature of plaintext using encrypted message only I'm looking for an algorithm which allows verifying a signature of a plaintext message but while only having the encrypted message.

The requirement is for Alice to send Bob a plaintext message (M) which is signed (S) by central authority (CA), the message should be encrypted (E) to Bob.

Anyone should be able to verify (V) that each of the encrypted messages (E) matches its signature (S).

CA = Central authority signing plaintext messages

M = Plaintext message

S = Signature of M by CA

E = Encryption of M

V = Function validating S against E. V(E,S) is in {true,false}

What you want is a "signature-friendly" encryption scheme, where one can verify a signature on an encrypted message. We can define it as follows:

KeyGen: generate keys $(\mathsf{pk},\mathsf{sk})$
Encrypt: given $\mathsf{pk}$, a message $m$, and a signature $s$, output a ciphertext $c$
Decrypt: given $\mathsf{sk}$, and a ciphertext $c$, output a plaintext $m$
Verify: given $\mathsf{pk}$, a ciphertext $c$, and a signature $s$, output a bit $b$

With the following (informal) guarantees: (KeyGen,Encrypt,Decrypt) is one-way (as pointed out by SEJPM in the comments to the question, the scheme cannot be IND-CPA secure), encryption/decryption work correctly, and Verify($\mathsf{pk},c,s$) outputs 1 if and only if Check(Decrypt($c,\mathsf{sk}$),$s)=1$, where Check is the signature verification algorithm.

We can build such an encryption scheme in a natural way, starting from any encryption scheme, any signature scheme, and a non-interactive zero-knowledge (NIZK) proof system. A NIZK proof system for a language $L$ works as follows:

Setup: generate a common reference string crs
Prove: given a word $x$ and a witness $w$ for $x\in L$ (and the crs), output a proof $\pi$ of $x\in L$
Verify: given a word $x$ and a proof $\pi$ (and the crs), output a bit

with the following guarantees: if the prover is honest (and $x\in L$), Verify outputs 1, if $x\notin L$, no prover can construct a proof $\pi$ accepted by Verify, and the proof leaks no information about $w$ (slightly more formally, the proof can be simulated without $w$).

Let $E$ denote some arbitrary encryption scheme, and $S$ denote some arbitrary signature scheme. Consider a NIZK proof system for the language $L$ of triples $(\mathsf{pk},c,s)$ such that $c$ is an encryption with $\mathsf{pk}$ (under $E$) of a message $m$ satisfying Check$(m,s)=1$ (where Check is the signature verification algorithm of $S$). The witness for $(\mathsf{pk},c,s)\in L$ is the pair $(m,r)$ such that $c=$Encrypt$(\mathsf{pk},m;r)$ and Check$(m,s)=1$.

KeyGen: generates keys $(\mathsf{pk},\mathsf{sk})$ for $E$, and a common reference string crs for the NIZK proof system. The public key is $(\mathsf{pk},$crs$)$ an the secret key is $\mathsf{sk}$.
Encrypt: given $(\mathsf{pk}$,crs$)$, a message $m$, and a signature $s$, check that Check$(m,s)=1$; output $\bot$ if this is not the case. Else, compute an encryption $c$ of $m$ under $E$ with $\mathsf{pk}$ (with a random coin $r$), and a proof $\pi$ of $(\mathsf{pk},c,s)\in L$, using witness $(m,r)$. Output the ciphertext $(c,\pi)$.
Decrypt: given a ciphertext $(c,\pi)$ and $\mathsf{sk}$, output the decryption of $c$ under $E$ with $\mathsf{sk}$.
Verify: given the public key $(\mathsf{pk}$,crs$)$, a ciphertext $(c,\pi)$, and a signature $s$, output NIZK.Verify(crs,$(\mathsf{pk},c,s), \pi$).

The security properties of the above scheme follow immediately from those of $E$ and from the zero-knowledge property of the NIZK proof system, and the signature verification property follows from the soundness of the NIZK proof system.

The above scheme is a somewhat generic template; to get an efficient construction, one must carefully choose the underlying primitives, with proof-friendly encryption scheme and signature scheme. To obtain better efficiency, it would probably be wise to use an interactive zero-knowledge proof, and to make it non-interactive in the random oracle model using the Fiat-Shamir transform. It requires some work, but it should be feasible to make this quite efficient with appropriate choice of the underlying primitives.


Is there a partially homomorphic quantum secure public key cryptosystem with IND-CCA1 security? I recentely asked "IND-CCA1 RSA padding?" about whether there is a IND-CCA1 secure variant of RSA. The original version of the question also allowed usage of ECC which would allow usage of ElGamal, providing IND-CPA and somewhat IND-CCA1.

Now I have the same setting as in the above question, meaning I need a cryptosystem with some homomorphic property and maximal security notion (IND-CCA1 would be optimal, but IND-CPA would also be OK). But this time I'm asking for a post-quantum scheme having a homomorphic property and being IND-CCA1 secure.

So finally the question:
Is there any post-quantum public key encryption algorithm providing IND-CCA1/CPA security and a partial homomorphic property?

Please exclude fully homomorphic encryption schemes from the answers. I know most of them are PQ safe, but they're too slow. And of course please also exclude schemes being even slower than FHE schemes.

Essentially any IND-CPA-secure lattice-based cryptosystem offers additive homomorphism, up to a predetermined number of operations.

I don't know of any IND-CCA1-secure post-quantum candidate that offers any homomorphic property, except Loftus-May-Smart-Vercauteren SAC'11, which is based on a nonstandard "knowledge of error" lattice assumption.


In RSA encryption, why does the public exponent (usually, 'e') have to be coprime with $\varphi(n)$? I have seen that there is a similar question here but none that really answers the question. I understand that if I choose the encryption exponent $e$ not coprime with $\varphi(n)$ then there is not a unique way to decrypt a message.

What I am wondering is what is the mathematical reason behind this? It seems to me that since $m^{(k \varphi(n)+1)} = m \bmod N$ and $d$ is defined as $(k\varphi(n)+1)/e$ then $d\cdot e$ is always going to be $k\varphi(n) +1$. What am I missing?

Textbook RSA encryption goes $c\gets m^e\bmod n$ with $n=p\,q$, and $p$ and $q$ primes (all quantities non-negative integers throughout). The question states

  $d$ is defined as $(k\,\varphi(n)+1)/e$

Yes¹, for some integer $k$ such that this division yields an integer. And that can only be the case if $\gcd(e,\varphi(n))=1$. Proof: Let $r=\gcd(e,\varphi(n))$. This $r$ divides $e$ and $\varphi(n)$. Let $f=e/r$, and $z=\varphi(n)/e$, both integers. We have $d=(k\,\varphi(n)+1)/e$, thus $e\,d=k\,\varphi(n)+1$, thus $r\,f\,d-k\,r\,z=1$, thus $r\,(f\,d-r\,z)=1$. When the product of two integers is $1$, both are $\pm1$; thus $r=1$. Thus by construction of $r$, we must have $\gcd(e,\varphi(n))=1$.

The definition of $d$ in the question implies $\gcd(e,\varphi(n))=1$. But the question also asks:

  If I choose the encryption exponent $e$ not coprime with $\varphi(n)$ then there is not a unique way to decrypt a message. What (..) is the mathematical reason behind this?

That's asking for a seldom given proof of: if a decryption of textbook RSA encryption can be consistently made, then $\gcd(e,\varphi(n))=1$ must hold. Here we go.

We want RSA decryption to be uniquely possible, the encryption transformation $m\mapsto m^e\bmod n$ must thus be injective over $[0,n)$, which we assume in the following. This implies three facts:

$e\ne0$. Proof: otherwise, all messages $m$ in $[1,n)$ would encrypt to $c=1$. There are more than one such $m$, contradicting injectivity.
$p\ne q$ or $e<2$. Proof: if otherwise, that is if $p=q$ and $e\ge2$, then all $m$ multiple of $p$ encrypt to $0$, since for all $i$ it holds $(i\,p)^e=i^e\,p^{e-2}\,p^2$, hence $(i\,p)^e$ is a multiple of $p^2$, hence $(i\,p)^e\bmod n=0$. There are more than one such $m$, contradicting injectivity.
$\gcd(e,\varphi(n))=1$, which the question asks to prove.

If $e=1$, then $\gcd(e,\varphi(n))=1$ holds. Given fact (1.), we can restrict the proof of (3.) to $e\ge2$, and we do so in the following.

Given fact (2.), $\varphi(n)=(p-1)(q-1)$. Thus
$$\begin{align}
\gcd(e,\varphi(n))=1&\iff\gcd(e,(p-1)(q-1))=1\\
&\iff\gcd(e,p-1)=1\text{ and }\gcd(e,q-1)=1
\end{align}$$
Thus for the proof of (3.) it is enough that we prove $\gcd(e,p-1)=1$ (the same proof applies for $q$, giving the desired result). We do so in the following.

Given that $p$ is prime, the multiplicative group $\Bbb Z_p^*$ (that is the integers $[1,p)$ under multiplication modulo $p$) has $p-1$ elements. It is known to be a cyclic group, thus there exists a generator $g$ with $x\mapsto g^x\bmod p$ a bijection on $[1,p)$, with $p-1\mapsto 1$.

Let $r=\gcd(e,p-1)$. This $r$ divides $e$ and $p-1$. Let $f=e/r$, $s=(p-1)/r$, and $h=g^s\bmod n$. It holds $h^e={(g^s)}^e=g^{s\,e}=g^{f\,r\,s}=g^{(p-1)\,f}={(g^{p-1})}^f$. Hence $h^e\bmod p=1$.

Given fact (2.) and $p$ and $q$ prime, $p$ and $q$ are coprime. Thus by the Chineese Remainder Theorem there exists² $t\in[0,p\,q)$ with $t\bmod p=h$ and $t\bmod q=1$.

It follows that $t^e\bmod p=h^e\bmod p=1$, and $t^e\bmod q=1^e\bmod q=1$. Again by the CRT, it follows that $t^e\bmod n=1$.

It also holds $1^e\bmod n=1$. For RSA encryption $m\mapsto m^e\bmod n$ to be injective, we must thus have $t=1$, therefore $h=1$. Since $x\mapsto g^x\bmod p$ is a bijection on $[1,p)$, and transforms $x=p-1$ into $1$, and $s$ into $h=1$, it must hold $s=p-1$.

By construction $s=(p-1)/r$ and $r=\gcd(e,p-1)$, thus $\gcd(e,p-1)=1$, Q.E.D.

Note: for proper generation of $N$ the condition $p=q$ is extremely improbable, and even if it occurs it leads to vanishingly few $m$ which encryption could not be uniquely deciphered, which is why $p\ne q$ is sometime omitted in the definition of textbook RSA. However when $\gcd(e,\varphi(n))\ne1$, the proportion of $m$ which encryption could not be uniquely deciphered becomes sizable, which is why condition (3.) on $e$ or an equivalent is always required. An argument for this sizable proportion is that there are many generators $g$ leading to distinct $h$, and for each $h$ that we exhibited there are $q$ messages $t$ encrypting to the same $c$.

¹ A standard proof is that if $e\,d\equiv 1\pmod{\varphi(n)}$, then decryption per $m\gets c^d\bmod n$ works for most messages in $[0,m)$, and for all such messages when $n$ is squarefree. The converse does not hold.

² That $t$ is unique and could be computed as $\left((p^{-1}\bmod q)(h-1)\bmod q\right)\,p+1$.


Risk of appending secret salt to plaintext prior to RSA encryption? TL;DR

Will appending session id to a password prior an RSA encryption introduce vulnerability where an eavesdropper can collect multiple encrypted password ciphertext and perform cryptanalysis to obtain the password? (Session id is known to the server only and unique for each visitor)

Background story

I have a login form that encrypts passwords using client-side (Javascript) RSA encryption and sends the encrypted passwords to backend server (PHP) to be decrypted and then sent to be authenticated by an LDAP server. This is to prevent any eavesdroppers from snatching the passwords should they be sent in plaintexts.

However, I have a feeling that if there was indeed an eavesdropper, he/she does not even have to know the passwords as he/she can just forge a request using the encrypted passwords (i.e. replay attack).

So I'm planning to improve the scheme by prepending/appending users' session id to plain passwords before encrypting them on the client-side. That way, even if an eavesdropper forges a request using an encrypted password, the backend server can check if the session id in the decrypted string does not match with the attacker's session id and hence reject the login request.

However, I have a feeling that an eavesdropper that monitors a particular user's login requests can take multiple versions of the encrypted passwords and perform cryptanalysis to obtain the plain password, something that would not be possible if the encrypted passwords remain the same in all the requests (which in turn is susceptible to a replay attack).

Is my worry a valid concern?

N.B.: Assume that HTTPS/SSL is not an option for my case.

You are absolutely correct. If you hash or encrypt the password on the client, then pass the resulting digest over an un-encrypted channel, then any man in the middle can simply replay the digest value and log in. The original password is irrelevant now.

What you have effectively done is to turn the digest itself into the password.

The real issue is that you are not using HTTPS to protect your session. The underlying issue is a trustworthy exchange of encryption keys between the client and the server (an offline component of the encryption). This is the exact issue that HTTPS (SSL/TLS) addresses. I'm afraid that by doing your password encryption/hashing on the client and passing the resulting values over a plaintext channel, you're doomed to create a system that is either vulnerable to replay attacks, or too expensive to implement and maintain as a secure system into the future.

Why is HTTPS not an option? If security is the goal, I think HTTPS is probably your only reasonable option.

Your general approach was immortalized in an official Internet RFC 20 years ago, and has been known to be kind of broken for a very long time. Just read about HTTP digest authentication: https://tools.ietf.org/html/rfc2617

Regarding appending a session id... First, what does that matter if the channel is unencrypted and the attacker can just replay the digest (unless you are changing the session id on every call)? Also, there is is no magical session id--if the id is known to the server, then either the server or the client created it and passed it across the wire. So the session id isn't a secret.

To protect this kind of scheme at all, you need to use a nonce. You need to send your encrypted authentication package with every request, and you need to increment the nonce and re-encrypt for every call. That way, the server can see that the nonce is larger than it was on the last request, and thus reject a replay. So now the server has to track that nonce value, per user, in addition to the session id. That becomes more complicated if you have a web garden or server farm, because you have to update that shared state centrally, and that can become a scalability and concurreny issue for your system. And there are still more issues with a scheme like this, which is why one of the factors in the Kerberos authentication schema (for example), is that the server and the client must have their clocks synchronized within 5 minutes of eachother. Among other things, a simple incrementing nonce can leave you vulnerable to attackers with a lot of resources.

You're also doing this in JavaScript in your client, communicating over an unencrypted channel, thus making your system even more susceptible to things like script injection, meaning that some rogue JavaScript in the page could read out values of variables in your security script, including the value of the original password, and phone that information back home to whoever is listening. Do you completely trust every analytics script you include in your pages? Do you completely trust that some new XSS attack can't put a bad guy's JavaScript in your page?

And so on. If you want actual security, you need to implement something more in the league of Kerberos (which is heady stuff), and you probably need to implement it as a browser plugin to provide a bit of a wall between it and other scripts and plugins.

Or you just need to implement HTTPS, and send the password through the encrypted channel to the server, where the server will salt it, hash it (hopefully using an algorithm like scrypt, bcrypt or pbkdf2) and compare it to the digest you have stored on the server.

Otherwise, I'm afraid you're not accomplishing real security.


Is this toy RSA demonstration flawed? I want to present the basics of how RSA works to an audience of beginners in cryptography. The problem is that I am lightyears from being an expert.

After reading about how RSA works in wikipedia, this is the "toy" demonstration I created:

We shall assume that Bob has a secret natural number that he wants to tell Alice.
We shall assume that they will be speaking to each other, and there are lots of people around (including cryptographers!) that can hear them.
This is how the talk will proceed:

Bob says out loud: "Hey Alice, I want to tell you a secret natural number!"
Alice replies out loud: "Ok, wait a second, let me create the encryption keys."

Now Alice secretly chooses two distinct prime numbers, $p$ and $q$, and calculates two things: $n = pq$ and $\lambda = \text{lcm}(p-1, q-1)$.
Then Alice secretly chooses any number $e$ which satisfies $e < n$ and $\text{gcd}(e,λ) = 1$
Then Alice says out loud the values of $n$ and $e$.

Alice says out loud: "Very well, the public key is $(n=391, e=75)$!"
Bob replies out loud: "Understood, give me a second!"

Then bob takes his secret number $m$ and calculates $c = m^e \text{ mod } n$ and says it out loud

Bob says out loud: "Okay, after encrypting my secret number I got 240"
Alice replies: "Great! I've got your secret number!"

She did it by first calculating $d = e^{-1} \text{ mod } \lambda$ and then calculating $m = c^d \text{ mod } n$.

Then I will choose two people in the audience and let them do it, with everyone else listening, and claim that this is basically what happens with RSA encryption. The rest of the audience will not be able to find out the message efficiently, even though they heard absolutely everything.

The above is what I plan on presenting.

QUESTION: I don't want to be a Dave. I think I'm not a Dave because I am following RSA. Are there any big problems with the above? Does it present the idea of RSA correctly? What gotchas should I mention, if any?

Bonus points for anyone who figures out Bob's secret number above. Of course I know it can be done by brute force because  I chose ridiculously small prime numbers...

You wouldn't be a Dave for presenting RSA, but you would be a Dave for following this description to implement anything, and you risk creating Daves with this presentation. I'm not saying you shouldn't do it, but you should emphasize that this is only the mathematical basis of RSA and a lot more is involved in making it do something useful.

Your description is mostly correct, with just one minor error: in any remotely modern use of RSA, key generation is done a bit differently: first you choose either $e=3$ or $e=65537$, and then you choose $p$ and $q$. It's done that way for performance, but it also highlights an important thing: $e$ and $d$ are not symmetric. You cannot swap them. You cannot “encrypt with the private key”: that's just a bit of popular nonsense that stems from an incomplete understanding of RSA.

There are also few inaccuracies that don't really matter. Alice calculates $d$ at step 2, not each time she receives an encrypted message. Or Alice might not calculate $d$ at all, because rather than calculate $m = c^d \bmod n$ to decrypt a message, she might perform an equivalent calculation nicknamed “CRT” which is a bit faster. But at this level of detail, these are  unimportant.

This is a nice application of mathematics that's generally understandable by people with just a bit more than high school math. But it is of no direct use to anyone using RSA: your cryptography library hides the details for you. In fact, ideally, when you're writing code that uses cryptography, you shouldn't have the letters "RSA" in your code any more than you should have the letters "AES". But in the real world, programmers often need to care about more details. And as a point of interest for non-programmers, this does not give an accurate insight in the kinds of problems that cryptographers and cryptography implementers work on.

As a cryptography implementer, here's the kind of things I've worried about that are related to RSA:

Am I using the right tool for the job? RSA is more popularly known for encryption, but signature is at least as important an application. Signature is not quite dual to encryption: there are symmetries, but there are also many differences.
Is my implementation of computation on large integers (bignums) vulnerable to timing attack and other side channel attacks?
Is my use of RSA properly padded? Plain RSA has more holes in it than Swiss cheese. The reverse side of the coin of RSA's mathematical simplicity is that it's easy to construct relations involving plaintexts or ciphertexts. For example, $c_1^d c_2^d = (c_1 c_2)^e \bmod n$, so if I happen to know what $c_1$ and $c_2$ decrypt to, I can decrypt $c_1 c_2$. And that's just the simplest example.
There are two ways to solve this problem. One is to restrict what gets encrypted. This is the approach in RSA-KEM, where RSA is used solely to encrypt a freshly generated random number. Not a number within a certain range or anything fancy like that: it would defeat the point. And then you have to use that random number in a very specific way. The other solution is to add padding, which restricts which ciphertexts are valid, in order to break mathematical relationships between ciphertexts.
Oh, but if we restrict which ciphertexts are valid, then we open a whole class of attacks: padding oracle attacks. The basic principle is that Eve sends a message $c$ and gets Alice to try to decrypt it. So Alice calculates $c^d \bmod n$ and finds that $c$ is invalid. She might reply to Eve, or she might keep silent but Eve still finds out that the message is invalid because Alice doesn't do what she would do with a valid message. Maybe the difference is even just in the timing of Alice's response. Whatever it is, if Alice is not careful, merely probing with a few thousand ciphertexts, just to know whether each ciphertext is valid or not, can let Eve reconstruct the key. This type of attack is known as an adaptative chosen ciphertext attack.
Historically, the first padding mode for RSA was the one known as PKCS#1 v1.5, and it is prone to this kind of oracle-based adpatative chosen ciphertext attack, mainly Bleichenbacher's attack (one of them) and Manger's attack. The math behind this attack is a little heavier than the basics of RSA, but it doesn't need anything advanced, it just requires somewhat more equations.
Historically? Not just historically. Bleichenbacher's original paper was published in 1998. The latest variant of his attack, with practical impact on many TLS implementations, was The Nine Lives of Bleichenbacher's CAT, published in 2018. Another year, another Bleichenbacher variant.
PKCS#1 v.5 is deprecated, but still in real-world use. For encryption, OAEP should be used instead. For signature, PSS should be used instead. They aren't panacea, but they're considerably easier to get right. They're more complex functionally than PKCS#1 v1.5, but they leave less room for subtle implementation mistakes that break the security.
Decryption is the hardest operation to implement, because it combines the secret key with an input (the ciphertext) that's potentially chosen by an adversary. After calculating $m^d$, you need to decode the padding, and this is where mistakes are very easily made. The slightest timing difference in reacting to invalid padding can allow an adversary to reconstruct the key via Manger's attack or Bleichenbacher's attack.
Signature is usually easier than decryption because the input is more constrained. Encryption and verification are easier because they don't involve the secret key. But that's not to say that they're easy. For example, even in the past few years, implementations of RSA signature verification have been caught forgetting to verify some parts of the input, allowing forged signatures to go through — another type of attack due to Bleichenbacher.
RSA key generation must obviously involve a random generator, and getting random generation right is a hard problem. (Fortunately your operating system often solves it for you. I'm not so lucky: I often work on the part of the operating system whose job it is to solve it for you! But if your operating system solves it for you and you don't hook directly onto that, you're definitely being a Dave.)
RSA encryption must also involve a random generator, because it must not be deterministic. If encrypting the same message twice lead to the same ciphertext, it would be very easy to guess mostly-predictable ciphertexts. For example, if I know that a ciphertext is the encryption of either "Yes" or "No", with a deterministic public-key encryption scheme, I would just need to encrypt those two plaintexts, and to compare the results with the ciphertext. Thus all public-key encryption schemes are non-deterministic. PKCS#1 v1.5 and OAEP both do it by concatenating the message with some random bytes, as part of the padding. PSS also uses random padding, although for signature the randomness is not an absolute necessity.
Of course there's the usual risk of implementation mistakes. What if someone claims their public key has $n=0$? or $e=1$? or $e=n$? or $n$ is a 1210463558412104635584-bit number? or $n$ is a 2049-bit number?

Twenty years of Attacks on the RSA Cryptosystem by Dan Boneh is good reading. 20 years later, a lot of it is still relevant. RSA is so difficult to get right that there's a push to stop using it. Of course, it helps that elliptic-curve cryptography can do pretty much everything that RSA can do, and for the most part does it faster and with smaller ciphertexts and signatures. ECC math is considerably harder, but it's easier to translate to secure implementations (perhaps not so much for intrinsic reasons than because people have learned from RSA and ECC is standardized with formats and protocols that leave less room for mistakes).


Why is adaptive security stronger than CCA1 security, and weaker than CCA2 security? We know in CCA1 security, after seeing the challenge ciphertext,

no more decryption oracles are allowed to the adversary.

But in adaptive security, what should the adversary do?  Please help me solve the puzzle.

The word adaptive security could possibly refer to:

security with respect to the definitions of IND-CCA2, possibly emphaizing that is the adaptive case of IND-CCA (IND-CCA1 is called non-adaptive)
Real-time adaptive security, but that's not really in the field of cryptography but network security.
Gartner published a paper Designing an Adaptive Security Architecture for Protection From Advanced Attacks (behind a paywall), and is referred to in various blogs. It seemed to have stirred some interest, but google mostly gives you results for "what is adaptive security", and after a quick glance none of those articles seem to be about cryptography. It seems to be mostly about network security and business management (including things like risk management, incident response, continuous monitoring etc. )

I don't think there is any (commonly used) security definition stricly between IND-CCA1 and IND-CCA2.


Can non-repudiation be ensured without public-key cryptography? Message authentication is ensured by using HMAC, which can be thought of as a symmetric-key construction.

Source authentication in multicast communications can be guaranteed using TESLA, which is again based on symmetric-key principles (although it basically works because of asymmetries in time).

However, neither HMAC nor TESLA ensure non-repudiation.

Is this a structural limitation of symmetric-key cryptography? Or is there some construct that ensures non-repudiation without using public/private keys?

Is this a structural limitation of symmetric-key cryptography? Or is there some construct that ensures non-repudiation without using public/private keys?

Non-repudiation implies that nobody other than the private key holder* could have produced the signature, which rules out symmetric constructions such as HMAC.

With a symmetric MAC (from a construction like HMAC), anyone who has the ability to verify a MAC also has the ability to construct one, so such constructions cannot be used to provide non-repudiation.

So in that sense yes, it is a limitation of symmetric-key cryptography.

While Hash-based signatures do exist, those are still an asymmetric cryptosystem with public/private keys, despite the fact that they use traditional hash functions.

Note

It is arguable whether or not signatures provide non-repudiation, which is a legal concept. It is arguable that cryptography itself is limited in the capacity to provide non-repudiation.


Group description in pairing based cryptography Suppose we have a public key encryption scheme, in which public parameter contains
$(p, G, G_t, e, g)$, where $p$ is prime number, $G$ is a (cyclic) group of prime order, $e:G \times G \mapsto G_t$. Now my question is, what is the meaning of $G$ which occur in the public parameter? Does it represent the group order (here $p$) and the operation (say $*$ multiplication)?

Thanks in advance.

DrLecter's comment should really be an answer, but one point which bears emphasis is that it is not sufficient for crypto purposes to say "a (cyclic) group of prime order $p$", because even though mathematically all groups of order $p$ are essentially the same group (i.e., they are isomorphic), we can't really say the same thing in crypto.

When doing crypto in cyclic groups, we generally make the assumption that the discrete logarithm problem is difficult to solve in the groups in question (most often implicitly through a stronger assumption like those in the DH family). But the choice of a particular cyclic group makes a dramatic difference in the difficulty of solving the discrete logarithm problem, at least in the current state of our knowledge: we know cyclic groups of prime order in which the discrete logarithm problem is easy (which ones?), and others in which it seems to be difficult. And even among the groups in which the discrete logarithm problem is considered difficult, it seems to be more difficult in some than in others.

Hence, any discrete log-based cryptosystem needs to specify explicitly which group it operates in if we want to have any idea of its security. This is what $G$ and $G_t$ represent in the definition of a pairing: they are simply the groups in question (e.g., $G$ is the group of points of the elliptic curve with equation [...] generated by the point [...]).

EDIT: Of course, in abstract discussions we can simply say that $G$ is a cyclic group of prime order in which such-and-such assumption holds, but still we would need to be more specific than just saying we operate in cyclic groups of prime order. It is also very helpful in discussions and proofs to have a name for the groups we are working in, especially in pairing settings where there are two (sometimes three) groups involved.


why do files downloaded with http and https have the same size? while working with Encryption mostly cipher text is always larger the plain text, why isn't that the case when downloading a file using https ? even that compression isn't much used anymore because if the CRIME and BREACH exploits the file still has the exact same size as a http download.

UPDATE : something i may be thinking of is that the browser or whatever tool only tells you about the size after decryption ?

[After your edit I can confirm that the browser does the whole encryption in the background - you only get the "normal" HTTP connection to see and the downloaded files appear as big as the unencrypted files - even if the encrypted files are only marginally bigger. You don't ever see the encrypted version without some addition work. You can use a secure connection like a normal one.]

Here a explanation why the exchanged data is slightly bigger than with unsecured connections: Ciphertext is mostly only slightly larger than the plaintext, not a significant part if the plaintext is already pretty large. At first (with for example TLS) we create a session which exchanges some data to authenticates the connection and generate a secure session key. This takes not much bytes, maybe a kilobyte. After that only a IV (ca. 16 bytes) and the padding (ca. 1 to 16 bytes) needs to be exchanged - only below ca. 4 percent size increase with 1 kilobyte exchanged plaintext. With bigger file sizes this will be even lower.


NIST temporarily closed — will that have a negative impact on the future of cryptography? For those who didn't notice yet, in the USA, the National Institute of Standards and Technology(NIST) has been shut down temporarily because of the poor fiscal situation of the USA.

The text at their site reads:

  NIST Closed, NIST and Affiliated Web Sites Not Available

  Due to a lapse in government funding, the National Institute of Standards and Technology (NIST) is closed and most NIST and affiliated web sites are unavailable until further notice. We sincerely regret the inconvenience.

  The National Vulnerability Database and the NIST Internet Time Service web sites will continue to be available. A limited number of other web sites may also be available.

  Notice will be posted here (www.nist.gov) once operations resume. You may also get updates on NIST's operating status by calling (301) 975-8000.

  Conferences and other events scheduled during the shutdown are postponed or cancelled. Even after NIST reopens, some NIST events may need to be rescheduled. Once access to NIST Web sites resumes, please see the Conferences and Events (http://www.nist.gov/allevents.cfm) list for updated information on specific events.

Here's a screenshot of the NIST website (2013-10-02T12:00:00Z):

On the positive side, I could imagine more people coming to Crypto.SE as a result of that.

Anyway… even though it was tempting, I want to avoid "asking for opinions" so I am not going to ask how reliable and trustworthy NIST is, when looking at the fact that government funding obviously has a huge impact on them. Still, a question remains:

What impact will the closure have on the future of cryptography? (think: "crypto-development")

This closure is a rather stupid thing, because the Web site is not closed: indeed, there still is a machine, somewhere, which responds to HTTP requests and returns the "we are closed" page. It would have cost zero effort, and zero extra money, to simply let the Web site run and keep on serving PDF files.

For crypto development, this means that until the US Republicans and Democrats finally agree on who is the Alpha Male, developers will need to find the relevant standards and test vectors elsewhere. A lot of the information is duplicated elsewhere; e.g. FIPS 180-4, which defines the SHA-* functions, has also been copied as RFC 6234, which is still available. Also, many people already have copies of the documents they are working on (I know that my "Downloads" directory must have a lot of NIST pdf files in it).

In any case, crypto development, by necessity, works at the pace of research, with a lot of thinking. Thinking has not stopped. Publication of documents, writing of standards, organization of meetings... operates on a time scale counted in weeks or months, not days. A few days of bureaucratic-induced closure is not enough to show up on the big picture of cryptographic advances.


Can Diffie-Hellman be scaled up or force-multiplied? I'm not too familiar with the math involved with the exchange of keys, I've read it over several times, but math isn't my strong point. My understanding is that smart people are hard at work to overcome the difficulty of factoring the shared secret.

So assuming that quantum processors overcome the current implementations and 'brute-factor' the keys involved, can the exchange be scaled up similarly to other forms of encryption?

Is there a way to scale up the effort of required to brute-factor the shared key so that not even a Quantum Computer could efficiently compute it, while still maintaining acceptable performance for the good-guys with consumer-grade non-quantum computers?

Sorry if this has already been asked, but like I said math isn't my strong point, I'm not even sure how to identify if its been asked.

Short Answer: Yes

Long Answer:
From what I understand about quantum computing, they are only more efficient as long as the bit-depth of the problem falls within the bit-processing capabilities of the quantum processor. Example: a 64-bit quantum processor could solve 64-bit traditional encryption keys in a near-zero real time. 128-bit keys would still take a very long time, as would 256-bit. 512-bit, 1024-bit and higher bit-depth encryption schemes. Even if quantum computers get much much much more powerful, it is fairly easy to scale the key size to an arbitrarily high number of bits to defeat quantum computing methods.

Diffie-Hellman keys can be generated for very-high bit lengths, as it is not difficult to generate the numbers required for it. It IS, however, difficult so solve, and that hasn't changed, and likely won't change for a very long while.


Encryption technique performance evaluation I've come up with a light weight bit wise encryption algorithm and seems good. Ive tried it with text and image input. But I've the following questions I would like to ask

What do you think of bit wise encryption schemes. Pros and cons (performance and security wise)
How could I compare the security level and the performance of my encryption with well known encryption methods.

I mean visually the text and the image look encrypted. Totally unrecognized. But is there any way that I can mathematically or analytically measure the security level. And also the performance how can I say this encryption has a better performance than the other.

Looking at encrypted pictures is not a good test. I mean, if you can visually see non-random looking parts in an encrypted picture or text, then this implies that the encryption system is abysmally bad. But seeing nothing from a visual inspection does not prove that the system is secure; it just suggests that it will not be easily broken by a chimpanzee.

The same can be said, to some degree, about statistical tests like the Diehard suite. Successfully passing the tests is no proof of security, only proof that you did not make a mistake so obvious that even a brainless generic statistical test would detect it.

To know whether a given encryption system is secure, cryptographers use the following recipe:

They publish the system: complete algorithm description and sample implementation with test vectors (the code is not the description; the description should make no assumption on the involved programming language, and yet be sufficient to reimplement it perfectly in any language).
They lure other cryptographers into gnawing at it and try to break it. The "luring" is about making the algorithm interesting, either through a some kind of mathematical novelty in the structure (e.g. a reduction proof with regards to a well-known hard problem) or impressive performance (see below).
After enough time and work, if the cryptographers found nothing bad to say about the algorithm, we can begin to say that it may be worthwhile to consider in future protocol designs.

Let me stress that "enough time" means "at least five years and one hundred cryptographers". Yes, it is very expensive unless you can convince cryptographers to work for free. NIST did it quite well back in 1998, for the AES competition: they just promised glory (but not a single dollar !) to the winner, and they all came. But the real source of AES strength is not the three years of competition, it is the ten years of subsequent widespread usage and thorough continuous investigation. We have come up with a few interesting attack ways, not on the algorithm itself but on its implementations (side channel attacks); the existence of some results on AES shows that research on AES has kept on, and found nothing fatal. That's the good thing: whatever weakness AES may have is certainly not obvious and we can begin to build trust on that.

Note that there are guaranteed ways to ensure that a given algorithm will not be studied, and thus may never be declared "safe enough":

do not publish the algorithm;
publish the algorithm only as code (especially in an ill-suited language such as any dialect of Basic);
patent the algorithm;
make it considerably slower than the AES.

If you do any of the following, you totally forfeit your chances of seeing your algorithm being independently investigated, and therefore it will never be considered "secure".

Performance is quite easier to evaluate than security. For a symmetric encryption system, the following characteristics are absolute requirements for the system to be considered a non-joke, performance-wise:

The input data shall be any arbitrary sequence of bytes (no restriction like "printable characters only").
For an input message of size $n$ bytes, the encrypted message should have length at most $n+r$ bytes where $r$ is a small overhead, no more than twenty bytes or so, independently of $n$. Proportional size increase, even by a small amount (such as encrypting 1 GB of data into 1.01 GB), is a total no-go.
The encryption process shall use only small amounts of RAM and code; apart from the data itself, the code and RAM for state and constants shall fit in the level 1 caches of the CPU. On a modern, "big" CPU like the one in a desktop PC, there is typically 32 kB of level 1 cache for code, and about as much for data. Some smaller architectures have smaller caches (e.g. 8 kB for code and 8 kB for data on a MiPS-based home routeur). The encryption shall be amenable to streaming, i.e. encrypting gigabytes by small successive chunks, while keeping only a few hundreds of bytes of state in RAM.
The processing time to encrypt $n$ bytes shall be, asymptotically, proportional to $n$ (time to encrypt 2 gigabytes shall be twice the time to encrypt 1 gigabyte).

Given these characteristics, you can define encryption performance with the following formula:

$$ T = k*n + i + f$$

where:

$T$ is the encryption time;
$n$ is the input data size, in bytes;
$i$ is the processing time needed to begin the processing (initialization which can be done before seeing the first byte of data; the "key schedule" fits there);
$f$ is the processing time needed for finalization (after all data bytes have been seen, the time needed to close up things appropriately and output the last encrypted byte);
$k$ is the asymptotic encryption speed.

If you express all these values in "clock cycles", then $k$ is the encryption speed in "clocks per byte". The smaller the better. To measure $k$, have your code repeatedly encrypt an 8 kB data buffer so that the total processing time takes at least a few second (see this answer for a more detailed treatment).

With OpenSSL on a basic desktop machine, I get AES speed close to 17 cycles per byte (the processor is an Intel i7; it can do much better, below 2 cycles per byte, using the special AES opcodes, but OpenSSL does not use them). Some stream ciphers achieve much better performance (e.g. less than 4 cycles per byte with Sosemanuk). That's your competition.

Bottom-line: If your system cannot go below 20 cycles per byte on a PC, don't even bother with publishing it: it will not be "interesting enough". Harsh but true: symmetric encryption has gone quite far and is considered to be a "mostly solved" problem. It takes quite a lot of effort to design something which has the slightest chance of being an improvement over already known algorithms.


Alternatives to Mersenne Twister We have Mersenne Twister pseudorandom number generator. It has several variants, CryptMT among them, that is of cryptographic grade.

There are alternatives to Mersenne Twister, like Xorshift or Xoroshiro.

Question: Do those algorithms have cryptographic variants, or are they secure per se, or are there other simple pseudorandom number generators that are good for cryptography?

I need a generator that has good random properties as it will be used to generate random matrices (not keys). At the same time it has to be unpredictable enough so the attacker has little control what matrices are generated when messing with the seed.

CLARIFICATION:

The setup is as follows: a random seed is chosen and used to generate pseudorandom square matrices over Boolean ring. Those matrices, when chosen randomly, have certain probability of being singular or not. The PRNG must generate such a sequence so the probability of a matrix being singular is the same as if they were chosen randomly.

The matrices are not secret, they are presented to the user and forward secrecy is not needed. Based on initial state the user might be able to predict all next matrices in a sequence, as long as they admit the right probability distribution.

ATTACK SCENARIO:

An attacker might be able to alter some bits of the random seed. Not all bits, as he might be restricted to altering only a subset of bits of the seed, or flipping several bits at once. Even when the attacked has such ability, the probability of a matrix being singular should be the same as if it was chosen randomly.

HARDER PROBLEM:

We want not only (non)singularity of a matrix to be close to random distribution, but also its rank.

Forget the Mersenne Twister and xorshift; maybe CryptMT is secure but it has received very little scrutiny since it was rejected from the eSTREAM portfolio a decade ago.  Cryptography is rife with good pseudorandom number generators, like ChaCha: if you pick the seed uniformly at random, the attacker has no hope of distinguishing the output from uniform random, and the world has high confidence in this state of affairs because it has been subjected to heavy scrutiny and there are trillions of euros of economic value protected by ChaCha in HTTPS around the world.

If you have measured performance, and you have profiled, and you have confirmed that a lot of time is spent in ChaCha, and you are confident that this will never be security-relevant—in particular, if you can quantify the statistical tests you need to defeat and argue that smarter statistical tests will never be relevant—then maybe you will have a reason to look elsewhere.  But the first thing you can do with ChaCha is tune down the number of rounds from the default ChaCha20 to the cheaper ChaCha12 or even cheaper ChaCha8.

Update, for question's addendum:

If the adversary can control the seed, then even if you used a random oracle for the PRNG (which is the strongest possible model—not attained by ChaCha but a reasonable model for, say, SHAKE128), the adversary can spend an expected $t$ trials finding a seed with a property that occurs only $1/t$ of the time, like $t = 2^n$ trials to find a seed under which the first $n$ bits of output are all zero.  No amount of cryptography can help you against this.

But if the adversary can't control the seed, the property you want—nonsingular matrices with high probability—is essentially guaranteed with any cryptographic PRNG.  If it weren't, then the putative cryptographic PRNG would be astonishingly bad, because a very simple test—generate a matrix and test whether it's nonsingular—would serve as an attack against the PRNG that breaks it without even knowing how the PRNG is designed!


Scrypt's maximum strength to increase entropy of lame passwords The developers claim that a 6 letter long password hashed with 3.8 second's of scrypt would cost $900 to brute-force.

If we use more cycles, how quickly will the brute force cost increase?
What are the minimum system requirements to compute such a huge KDF on a desktop or mobile?
Is there any formula to estimate its entropy based on CPU cycle time?
Does Scrypt survive from Grover's algorithm?

Please consider that bad passwords can be very long.

You have to test it on the hardware you'll be using. I tried CryptSharp's implementation with a cost of 262144 and it took about 7 seconds.
The reason it costs more is cause of the memory it uses, and my process that was running the Scrypt was eating up 340ish MB.

How much of that was from the KDF? Don't know.

How would my box handle 100 people authenticating at the same time? Very good question.

This is something you need to performance tune to specific hardware.


During padding oracle attack (CBC), how is first byte of plaintext block is obtained? Imagine conducting a padding oracle attack against CBC mode with 16-byte length blocks, and PKCS#5 used for padding.

You start, as always, revealing the last byte of plaintext. Then you iteratively move backward and reach the first byte of last plaintext block. At this stage, you already spoofed the padding with 15 bytes, which values are 0x0f.

So, how do you reveal the first byte of a block, since you’re out of padding length?
Does PKCS#5 allow you to pad 16 bytes with 0x10 value?
Or, these things are up to the implementation of padding used in a specific application?

Does PKCS#5 allow you to pad 16 bytes with 0x10 value?

No, but that's because PKCS#5 only specifies padding for DES, and that has an 8 byte block size. Even PKCS#5 itself refers to PKCS#7 when it comes to padding AES. More information about the differences here.

Now for the real answer. PKCS#7 padding, which is identical to PKCS#5 but allows any block size, requires 16 times the 0x10 byte value as padding:

  For such algorithms, the method shall be to pad the input at the
  trailing end with $k - (l \bmod k)$ octets all having value
  $k - (l \bmod k)$, where $l$ is the length of the input.

Here $k$ is the block size of the block cipher in bytes, for instance AES with a block size of 16 bytes. Now obviously if $l$ is a multiple of 16 then then a full block of padding is added (as $l \bmod k$ would evalulate to zero and therefore only $k$, i.e. 16 would be left).

The reason for this is simple: imagine that a plaintext message that is a multiple of the block size ends with a valid padding pattern. Then the unpadding would remove that part of the message. By always performing padding the unpadding can be performed regardless of the contents and size of the message (i.e. allowing any message to be decrypted correctly).


Pseudorandom generator and AE-secure encryption How would you answer the following question (I have to translate it from German):

The existence of a pseudorandom generator implies the existence of a AE-Secure encryption scheme (AE = authenticated encryption)
YES or NO

I would say "NO" because (as far as I understand) AE-secure schemes should use two keys (one for encryption and one for authentication).
But maybe I'm wrong because of missing background knowledge.

Yes.  The existence of a secure pseudorandom generator (PRG) implies the existence of all sorts of other symmetric-key primitives, including a secure PRF, a secure block cipher,  a secure MAC, etc.  That is enough to build secure authenticated encryption.


Applications of GF(p) polynomials A Galois field of the type $GF(p)$, where $p$ is prime, is normally expressed as the ring of integers modulo $p$.

If my understanding is correct, it is also possible to represent its elements as a ring $\mathbb Z_2[X]$ of polynomials defined over $GF(p)$, i.e. for $GF(2)$, we'd have polynomials of the form similar to $x^8+x^5+x^3+1$ or $x^9+x^6+x^2$, etc, and for $GF(5)$, we'd have polynomials of the form similar to $4*x^7+2*x^3+3*x+1$ or $2*x^5+3*x^3+x^2$, etc. All arithmetic operations are like with normal polynomials, but with a difference: all arithmetic operations on coefficients which occur in the calculations are done modulo $p$.

The question is: do polynomials defined over $GF(p)$ have any real application in cryptography where they are a better fit than their integers-modulo-$p$ counterparts?

Please correct me if I mixed something up in the theoretical part!

In my knowlegde, XTR is a cryptosystem build over $GF(p^6)$. We however use the subfield $GF(p^2)$ to have a compact representation.
I don't know if there are other cryptosystems defined directly on Galois field extention, but using some tools are common. For that, take a look on the operative environment of Weil or Tate pairing.


Sane implementations of Bitcoin cryptography routines w.r.t. side-channel attacks Bitcoin uses SHA-256, Base58Check, ECDSA (Sep256k1) and RIPEMD-160 as the basis of its encryption (see this article for a short guide on how addresses are created).

I would like to create an iOS-based wallet app that offers reasonable security.

OpenSSL is not available on iOS, and is quite a large dependency. What I'm looking for are specialized libraries that mainly focus on the Bitcoin algorithms. The OpenSSL code also is very hard to understand, making me wonder if there is really no better way.

libbitcoin and the official Bitcoin-Qt client both use OpenSSL.
OpenSSL generally has a mixed reception.
OpenSSL also added to the transaction malleability problem that recently made its round in the news, as OpenSSL has more relaxed criteria to accept a signature than strictly necessary.

bitcoinj uses Spongy Castle, also a large collection of algorithms.
Another option of an algorithm collection is Crypto++ which I haven't seen in existing Bitcoin clients so far.
Apple's Security framework only supports RSA on iOS.
Chromium includes Go-sources for ECDSA.
There is sipa's implementation for Sep256k1 that has a reputation of being very efficient. It is also listed under gh/bitcoin.

Many recent attacks in publications used side-channel attacks, making it necessary to have algorithms with constant-time execution (to avoid timing-related attacks) and additional protections against cache-based attacks and recently even audio-related attacks where noise that the hardware itself produces can be used to gain knowledge of the private key.

Even though many attacks require gathering of multiple signatures, one cannot know how the app will be used by the end-user. I do not want to rely on the assumption that the users doing transactions only a few times per day in different shops and exchange their Bitcoin addresses frequently.

My questions are:

Is there a "sane" implementation of the algorithms used by bitcoin? e.g. are there high-quality implementations available that incorporate defenses against side channel attacks?
Does OpenSSL already protects against side-channel attacks?

A mobile app is more open to side-channel attacks than the desktop PC standing at home, so what's reasonably secure on a desktop machine may not be secure enough for a mobile app.
As OpenSSL is probably the most used cryptographic library, it's probably also the most attacked one, and therefore, ahead when looking at general security. However, specialized libraries may have a higher quality for the few algorithms they implement, as the code base is much smaller and easier to understand.

How can I train myself to evaluate whether an existing implementation is vulnerable to certain types of attacks?

Cryptographic algorithm implementations are often only poorly documented and optimized to a point where the code consists of magic numbers chained together with arbitrarily seeming operators.
One aspect I already mentioned is the concept of constant execution time, which counters timing-related attacks.

Are there good resources that explain how to implement those algorithms myself? I do not intend to use my own implementation for the app, but I am interested in understanding how the stuff works I'm using. Entry-bar seems quite high. Can the "Guide to Elliptic Curve Cryptography" book be recommended?

PS: I know that Apple doesn't favorably treat Bitcoin-related apps in their store. However, this discussion is out of scope of this question.

PS2: Base58Check is only used as a special encoding to make Bitcoin addresses and keys more readable to the enduser. There is no cryptography involved there, and it's easy to implement - I only included it here for completeness.

Is there a "sane" implementation of the algorithms used by bitcoin? e.g. are there high-quality implementations available that incorporate defenses against side channel attacks?

libsecp256k1

  Does OpenSSL already protects against side-channel attacks?

haha*

  How can I train myself to evaluate whether an existing implementation is vulnerable to certain types of attacks?

Review the claims.  If it doesn't even claim side channel resistance, worry.
Review the track record.  If it's been subjected to side channel attacks repeatedly and it doesn't claim to have taken a serious comprehensive approach to fixing them, worry.
Identify the physical observables of interest.  If you're talking over the internet, you probably don't need to worry about power analysis.  But if you're making a smart card that a hapless luser will put into a malicious ATM, you may need to worry about it.
For timing side channels:

Identify a set of primitive computations that you take as constant-time.  Typical set: copying data, $w$-bit addition and subtraction, bitwise operations, constant shifts and rotates.  Multiplication can be questionable.
Follow the data flow of secrets.  If you can find any primitive computations that depend on the values of secrets, like the conditions of branches or the addresses of memory references, *bzzzzzrt*.  If you can prove they flow only into the safe operations, you might be OK.

Try not to handle individual bits at a time, and keep up with the state of the art because technology moves fast.
Pay attention to tools like gfverif.

  Are there good resources that explain how to implement those algorithms myself? I do not intend to use my own implementation for the app, but I am interested in understanding how the stuff works I'm using. Entry-bar seems quite high. Can the "Guide to Elliptic Curve Cryptography" book be recommended?

Our friendly neighborhood bear has some good references.  Reading existing implementations is indispensible, and the abysmal code quality of a lot of otherwise good cryptographers can provide good motivation to get into implementation yourself.  For references on elliptic curve cryptography, we have lots on this site!

* In fairness to the modern OpenSSL team, they inherited a gigantic legacy code base and they are doing their best to clean it up and plug side channels without severely damaging performance.  Unfortunately, these goals—maintain legacy code base, preserve performance of bad cryptosystems—often come into conflict with side channel security.


How do Hash functions work under the hood? Using and benefiting from hash functions on a daily basis, I keep wondering how hash functions actually work down in their core.
Most of the available resources I found, only explained hash functions on a very high level, usually referring to their awesome properties and some of them mentioning something like reducing inputs.
But HOW do functions like SHA actually work on a very concrete level?
How do they actually implement something like collision resistance?

There are a variety of ways to construct a hash function. The two you will probably hear about the most are the Merkle–Damgård construction and the sponge function. The former is an older construction(dated 1979), and suffers from length extension attacks. New hashes might opt for the sponge construction, as it is immune to that particular attack.
As for how they work, they both contain an internal state and operate on that state using a function that is actually invertible.
The Merkle–Damgård construction
In the case of the Merkle–Damgård construction, the function used is usually a block cipher. Normally, the go-to example of a block cipher is AES, but because of a related key attack, you would not want to use it to make a hash with this particular construction.
Basically, in the Merkle–Damgård construction, successive blocks of the hash input are used along with the internal state as the inputs to a block cipher; This is also how the construction compresses large inputs into a finite state. This is another requirement of hash functions: the ability to operate on (effectively) arbitrarily sized inputs and produce a finite-sized output.
As for collision resistance, the MD construction has a proof: "... that if the one-way compression function f is collision-resistant, then so is the hash function constructed using it.".
However, according to wikipedia,  the MD construction itself, has generic vulnerabilities that are not the result of an unsatisfactory compression function:

Unfortunately, this construction also has several undesirable
properties:

Second preimage attacks against long messages are always much more efficient than brute force.
Multicollisions (many messages with the same hash) can be found with only a little more work than collisions.
"Herding attacks" (first committing to an output h, then mapping messages with arbitrary starting values to h) are possible for more
work than finding a collision, but much less than would be expected to
do this for a random oracle.
Length extension: Given the hash H(X) of an unknown input X, it is easy to find the value of H(pad(X) || Y), where pad is the padding
function of the hash. That is, it is possible to find hashes of inputs
related to X even though X remains unknown. Length extension attack
was actually used to attack a number of commercial web message
authentication schemes such as one used by Flickr.

It is possible to use the MD construction with a sort of capacity, similar to a sponge, by not outputting the entire state. This is where the ideas of SHA-224 and SHA-384 fit in, for example. They are simply truncated outputs of SHA-256 and SHA-512 (with other small modifications). By not revealing the entire state, length extension attacks may be foiled, depending again on the "capacity", or number of bytes dropped this way. However, usage of a capacity/truncating the state does come at the price of a reduced output rate.
The sponge construction
The sponge construction operates in a different manner. The sponge has an internal state, too, and it uses an invertible permutation to mix the state. Basically, the sponge "absorbs" a message block into its internal state, then applies the mixing permutation, and repeats this until all message blocks have been consumed into the state. This is how the sponge compresses data. The absorption of data either happens by XOR'ing the message block into the state or simply replacing a section of the state with the message block.
The sponge construction being uninvertible, resistant to length extension attacks, and preimage resistance is related to the use of a "capacity" section of the state. Basically, there is an imaginary line dividing the internal state into two sections, a "rate" section, and the capacity section. The output stage of the function only "squeezes" bytes from the rate section of the internal state. Since the capacity is never output directly, length extension attacks are resisted. The security of the sponge against attacks is related to the capacity size of the state, along with how well the mixing function resists things like differential cryptanalysis.
Padding
There is a little bit more to hashing then a confusing/diffusing primitive that compresses data. Since we require that it be infeasible to generate any preimage for a given output, and prevent anyone from finding collisions, things like padding of the input become very important, in order to prevent trivial collisions from being created. This is a contributor as to why the construction of a hash is more complicated and oftentimes requires more applications (rounds) then simply encrypting some data.
Other compression functions
There is actually an entire Wikipedia article about one-way compression functions, and there a few constructions one could use:

Some methods to turn any normal block cipher into a one-way
compression function are Davies–Meyer, Matyas–Meyer–Oseas,
Miyaguchi–Preneel (single-block-length compression functions) and
MDC-2, MDC-4, Hirose (double-block-length compressions functions)


Is it possible to brute-force a hash algorithm of 32 bits I have a 30000 user passwords and usernames stored in a table on a database in which the passwords are stored as hash where ,I need to guess the passwords for all users and I have the hash function which its output is 32 bit in length.

My questions is:
How much time do I need to guess that if I use collision attack?

I am confused which is better pre-image attack or collision attack ? if the input to the hash function is 80 bits.

if collision is better, is this mean to look at 32 bits?

You'd still need to iterate over all the possible passwords to do this, using a brute force or dictionary attack (i.e. a pre-image attack with regards to the hash). That is, unless the hash algorithm used isn't one way; i.e. you can retrieve more information about the passwords. A 32 bit hash is not common, so this could be possible.

Fortunately most passwords do not have a very high entropy, especially if they are limited to 80 bits (information taken from the comments). However, I don't think they are just limited to 80 bits (which would take too much time to crack). Usually passwords aren't made up of control characters and such; you'd need to know how the 80 bits are encoded - i.e. which character encoding was employed. Probably you can at least bring it back to 70 bits by always keeping the highest bit to 0 (keeping just to ASCII, in other words).

One advantage of 32 bit hashes is that it isn't likely that a strong password hash was used. That means that testing the passwords could be pretty fast. A disadvantage would be that there may be multiple passwords that match a specific hash.

That's useful information to an attacker, who's just interested in gaining access instead of the actual password. If you need to know the exact password though you might have some trouble for some passwords. That said, 32 bit could be just enough to have relatively few of those.

From the information you've given this may just be feasible. It depends on too many other parameters such as the strength of the hash function and the restrictions on the password to calculate the time precisely. Given a strong hash function it's however still directly (and probably linearly) related to amount of possible passwords.


Is it possible to retrive the Hash from an encrypted folder? So first of all I've a software which basically locks/encrypts a folder with a given password. Afterwards it's almost impossible to open the folder without entering the password through the software.

I locked some of my much needed files and accidently forgot the password.

So my question is, is it possible to retrive the hash from the encrypted folder? I'm planning to brute-force if it's possible.

If it's not, then should I reverse engineer the software to open the encrypted folder without entering the password?

What other possible options do I have?

Brute forcing a password is always possible - at least in theory. If it is computationally feasible to derive the password hash is a different matter; it obviously depends on the complexity of the password, the work factor used by the password hash (or rather, password based key derivation function) and how the software operates. You need to find the password as brute forcing the resulting key is not likely to be feasible. Depending on the encryption software the result can be directly validated or you may need to try to (partly) decrypt a file.

Reverse engineering the encryption software cannot be used to decrypt the files; the encryption depends on the key, not on the algorithm. You may need to reverse engineer the encryption software to facilitate the brute force or dictionary attack though. Then you could integrate it with password cracking software.

If the encryption is performed correctly then finding the password is the only real option available.


Can an AES-256 key be generated for a large number of cribs? I have a question in regards to Ransomware type viruses. I know that a number of these viruses use the AES-256 algorithm to encrypt user's files using a randomly generated key. I work in IT support and I had one client the other week who had lost a large number of important files this way but one thing which struck me was that we were able to recover a large number of files via DropBox - about 500 files (~2gb worth of data) and because the virus only changed the extension it was clear which unencrypted file corresponded to which encrypted file.

What I was wondering is; with a large dataset like this where you have both the encrypted and unencrypted data would it be possible to calculate the encryption key for an AES-256 algorithm in a reasonable time? I don't know how these algorithms work but presumably you would have so much data available to compare that it should at least make the task considerably easier should it not?

I'm not intending to rid the world of ransomware but it just interested me!

Cheers,

Olly

Just the most basic research on this site would have told you, the answer is NO.

From all known cryptanalysis on AES, the answer is simply there are no useful plain-text attacks. (Which is essentially what your "cribs" are.

It's not going to be possible to break AES-256 in your clients scenario. Full key recovery is out the picture even with a terrible implementation, unless there's a weak way that key is stored. Finding the AES key on the computer itself (encrypted using more vulnerable techniques) is your only shot in hell.


How to calculate RSA CRT parameters from public key and private exponent Given the public key (n, e) and private exponent (d), how to calculate CRT parameters (p, q, dP, dQ, and qInv) of this RSA key pair?

The first (and hardest) step is to factor $n$; the easiest way to do this (given $e$ and $d$) is with this randomized procedure:

Select a random value $z$ from the range $(2, n-2)$
Compute the value $\lambda = (ed-1)/2^k$, where $k$ is that integer that makes $\lambda$ an odd integer.
Compute $t = z^\lambda \bmod n$.  If $t = 1$ or $t = n-1$, we fail on this selection of $z$.
Do this repeatedly, at most $k$ times:

Compute $u = t^2 \bmod n$.
If $u = -1$, we fail on this selection of $z$.
If $u = 1$, we have success (and we have the factorization $p = gcd(n,t-1)$, $q = gcd(n, t+1)$)
Otherwise, set $t = u$, and continue with the next loop

If we run through the above loop $k$ times without hitting either success or failure, then either we happened to have selected a $z$ that's not relatively prime to $n$, or $d, e$ are not a valid RSA exponent pair.

A random value of $z$ will fail at most half the time; so we run this procedure (selecting different random $z$ values) until it succeeds, and gives us the factorization.

Once we have the factorization of $n$, computing the rest of the CRT parameters is straight-forward.


Tracking the noise growth of Homomorphic encryption So I'm a bit of a cryptography/HE noob, and I was wondering if it is possible to keep track of the noise growth that happens when you do some kind of mathematical operation on your encrypted data, and by keeping track of such growth, would it be possible to clip off the noise once it reaches a threshold (If I've understood correctly, after certain point your decryption process will be useless, because of noise?).

Now by learning that noise growth what else can I gain?
Is it even possible to clip off the unwanted noise and continue with your operation?

You can't know exactly how much noise your ciphertext has because when you encrypt a message, you sample random values that are combined to the message and they also make part of the noise (so, the noise is also random). But you can have good estimations for the magnitude of the noise because all the distributions from where we sample the values are known.

That said, the better you can do to keep track of the noise growth is to use the estimative provided (generally) by the authors of the scheme: in general, for the scheme we are using, we know upper bounds to the noise of a ciphertext that is the result of an operation, that is, we know functions $f$ and $g$ such that

if $noise(c_1) \le n_1$ and $noise(c_2) \le n_2$, then

$noise(c_1 + c_2) \le f(n_1, n_2)$ and $noise(c_1 \cdot c_2) \le g(n_1, n_2)$

(For instance, we could have $f(n_1, n_2) = n_1 + n_2 + 128$ and $g(n_1, n_2) = 128 \cdot n_1 \cdot n_2$).

It is worth noting that those estimations are quite pessimist: for instance, on the paper A Comparison of the Homomorphic Encryption Schemes FV and YASHE, authors say that they could select parameters with size about 30% smaller than expected because the noise growth was always below the theoretical upper bound, as they show in the following figure (which is on the 12th page):

That difference occurs because the theoretical upper bound uses a kind of "worst-case analysis", considering the biggest noise that can occur, but in practice, that biggest values of noise will occur only with small probability (remember that, in general, we sample those values following a Gaussian, therefore values close to the mean are more likely to occur...)

  Is it even possible to clip off the unwanted noise and continue with your operation?

Yes. This is called bootstrapping and it consists in running a "refresh" procedure to remove the noise of the ciphertext. But that is not a simple procedure and can be quite expensive computational-wise.

  Now by learning that noise growth what else can I gain?

You can try to reduce the number of times you use the "refresh" procedure removing the noise only when it is needed instead of doing that after each operation.


How does blocksize affect security? I have recently read about how blockciphers and how stream ciphers work, and although I think I finally got everything right, I'm still wondering how increasing blocksize increases security.

Block ciphers are usually used in modes of operation. The security of a mode of operation depends on two things: the security of the underlying block cipher, and the security of the mode itself when you replace the block cipher with an "ideal" permutation.

Say you're using a block cipher with block size $n$ bits, so with AES-256, $n = 128$ (the 256 refers to the key size). A good block cipher should be a pseudorandom permutation, meaning when you give it a uniformly distributed key, it should be difficult to distinguish it from an ideal permutation. An ideal permutation is a uniformly randomly generated permutation over all permutations from $n$ bits to $n$ bits, basically a mathematical object.

Determining whether a given block cipher is secure means cryptanalyzing it to make sure there are no obvious attacks. Such attacks make use of the structure of the block cipher, so for example, this would mean looking at the S-boxes in AES-256 and seeing how they interact with each other, and performing differential, linear, and other types of cryptanalysis. None of these techniques make explicit use of the block size, hence having a smaller block size does not mean you will be able to distinguish a block cipher from an ideal permutation more easily. So when it comes down to block cipher security, the block size does not play an important role.

In contrast, mode security depends strongly on the block size. I mentioned earlier that you also need to look at mode security when the block cipher is replaced with an ideal permutation. Once you do this, you can theoretically analyze the modes and even explicitly compute how its security degrades as you use it. To give an example, GCM has a security degradation of roughly $\sigma^2/2^n$, which represents adversary success probability, with $\sigma$ the number of permutation calls. This means that the more data you process with GCM, the more exposed the mode becomes. The reason this happens is because GCM's security relies on the ideal permutation being "hidden" from the adversary, and as you use GCM you increasingly expose the hidden permutation.

So putting everything together, even if you know that your block cipher on $n$ bits is indistinguishable from an ideal permutation on $n$ bits, your security will still degrade when you use the block cipher in a mode. Hence if you have the option of using a block cipher with small block size, or a block cipher with large block size, then it is better to use the block cipher with larger block size since you'll be able to use it in a mode much longer (assuming all else equal, meaning the cipher is secure for both block sizes).


Is this an effective obfuscation technique? Long ago I created a simple program which obfuscated a file by taking the first byte, then XORing it with the second, taking the (original) 2nd byte and X-ORing with the 3rd, etc, down the line. The file size is unchanged, and I could invoke the same program to undo the obfuscation. No key or password was required. It was just a simple way to hide the contents of a file from casual view.

My Question Is: Does this result in a uniform distribution of byte values such that it appears to be encrypted, and the usual analysis would not turn up anything?

I know that this is not encryption. Also that the first byte is plaintext, but one could simply stick a random value in the source file, use a space or some other harmless byte there.

It sound like you're using something like an XOR cipher to obfuscate your code.  It will appear to be encrypted, but this can still be broken by frequency analysis since the use of a constant shift means that the encryption effectively has no key.  An example of how to break a similar XOR cipher can be found here.  As @iismathwizard mentioned, decryption requires no more knowledge than the fact that XOR is in use, in the same way as as ROT13 cipher might be broken


How to forge signatures in the Schnorr scheme if $r=g^k$ is eliminated? I need some help to demonstrate how to forge signatures in the Schnorr scheme if I eliminate the random string $r=g^k$ used in the hash – using $H(M)$ instead of $H(M||r)$.

How would one be able to forge signatures in the Schnorr scheme if $r=g^k$ is eliminated?

I suppose that you address the question to a signature scheme, in which the signature is  still the pair $(r,s)$ with $r=g^k \bmod p$ as the exponentiated nonce and
$$s = H(m)\cdot x + k \mod q,$$
where $h = H(m)$ depends solely on the message $m$ being signed.
Here $x$ denotes the secret signing key and $q$ the order of the generator $g$ of a prime subgroup of $\mathbb Z_p^*$.
Creating a valid pair $(r,s)$ for an arbitrary message is done follows:

choose any value for $s$,
determine $r$ directly by the verification equation $$g^s = y^h \cdot r \mod p,$$ where $y=g^x$ is the public verification key, and not via its logarithm $k$. This yields $r = g^s\cdot y^{-h}\bmod p$.

This attack is the same as for Schnorr's identification protocol once one knows the verifier's challenge in advance, and shows (at least to me) how careful one has to be with cryptographic protocols: naivly, one is led to think it is impossible to forge a signature without knowing the components of the linear functional, i.e. the coefficients $x$ and $k$.


XORing to detect decrypted value? So I am doing a CTF and I have found a text that is full with hexadecimal encrypted value with XOR (that was a given hint from the previous flag). I don't have the key but I know the length of the key is $8$. I also know that the word Congratulations is in the file somewhere. So, I guessed that if I XORed Congratu with the first 16 hex bytes assuming that I'll recover the key as a result to fully decrypt the message but that didn't seem to give me a correct result. I'm guessing that Congratulations may not be the first, which is why I'm having this issue. Is there anything that you guys recommend to solve this quickly?

It sounds like a basic Vigenere cipher. From what you wrote, you even have some knowledge about the plaintext, but don't know the position.

You only tried out the first position, maybe just try this with shifting the worst to another position? Or just break the Vigenere cipher as if you knew only the keylength.


HMAC and assumptions on the cryptographic hash According to Wikipedia, a cryptographic hash function has the following properties:

Pre-image resistance: Given $h$, it's difficult to find any message $m$ such that $h = H(m)$.
Second pre-image resistance: Given $m_1$, it's difficult to find another $m_2$ such that $m_1 \ne m_2$ and $H(m_1) = H(m_2)$
Collision Resistance: It's difficult to find two distinct messages $m_1$ and $m_2$ such that $H(m_1) = H(m_2)$

Assuming $H$ is a hash function, the following function $H'$ should — to my understanding — also be a hash function:

$$H'(m) = m_0 || H(m_1||m_2||\dots||m_k)$$

where $m_i$ is the $i$th byte of $m$.

$H'$ leaks the first byte of $m$, but even just leaking one byte, you still can't find a pre-image or any collisions.

When looking at HMAC, Wikipedia says that it takes a hash function (without maker further assumptions on the hash function). Taking my hash function $H'$ (just let it leak $\operatorname{len}(key)$ bytes, but not the long message) for HMAC, HMAC would be insecure, since everybody now sees the key.

So maybe my $H'$ is not a cryptographic hash function after all — in which case my question is: Why not?

Or $H'$ is a cryptographic hash function, but building an HMAC requires additional assumptions. What additional assumptions must be fulfilled by the hash function to be secure in HMAC? Do the three properties above imply some other properties I don't see?

Also PBKDF2 takes a PRF, where HMAC-SHA256 should be secure, but HMAC just given a hash function which has the three properties, won't be a PRF to my understanding. Again the same questions: Are there more assumptions? Even more than on HMAC?

Before we jump into this question, you first need to know a bit about the internals of hash functions with the Merkle-Dåmgard construction. Here's a pretty picture from Wikipedia:

In this diagram, you see the compression function $f$ being fed the message blocks along with the output of the state of the previous compression block (or the IV). The final output is the result of the last compression function. (You can ignore the finalization step for our purposes.)

Now, let's focus on the original NMAC/HMAC paper. In it, the authors state:

  In the rest of this paper we will concentrate on iterated hash
  functions, except if stated otherwise.

This should be the first clue that your scheme is not one that will work with NMAC/HMAC: it's not iterated! Not all of it, at least. The fact that the first $n$ bytes are concatenated (leaked, what have you) means that your hash function's output is no longer solely the result from the compression function evaluated on the last block. This changes the construction of the scheme drastically.

In regular circumstances, the (almost implicit) assumption that the underlying hash function is iterated is not an unreasonable one at all: all of the popular hash functions of today are. (SHA3/Keccak is a bit of a special case. It's not clear one even needs the HMAC construction for it. But that's a topic for another question.)

For example, what do you do with the IV (initialization vector, or as Bellare et al call it, "initial variable")? Do you simply pass it along to the $H$ in $H'$? If so, then your scheme doesn't actually leak the key with NMAC, although it does leak $k \oplus \mathtt{opad}$ in HMAC. In case you're unfamiliar with NMAC, the basic idea of the scheme is replace the IVs of the regular hash functions with the keys $k = (k_1, k_2)$. In the case of HMAC, the "new IVs" are (where $f$ is the compression function for the hash in question) $k_1 = f(k \oplus \mathtt{opad})$ and $k_2 = f(k \oplus \mathtt{ipad})$. But note that this, too, carries with it the implicit assumption that the starting state of the next $f$ in the chain is the previous evaluation of $f$.

Trying to discuss $H'$ in the context of HMAC is difficult, though. The primary issue is that your $H'$ doesn't have a clearly available compression function. Sure, $H$ (probably) has a compression function, but for $H'$, things are much less certain. Even if you attempted to define a compression function for $H'$, in order to be an iterated hash function, it would somehow have to leak the first $n$ bytes of the original message while simultaneously evaluating $H$ for the rest of the message.

Here is the problem, though: even if you created such a compression function, it would be insecure, naturally. Namely, it no longer would act as a pseudorandom function (PRF) (or for Wikipedia's less thorough, but perhaps easier, explanation, see here). In this relatively new paper, Bellare proves that HMAC is a PRF itself if the compression function of the underlying hash is a PRF. If $H'$ had a compression function, then it definitely would not be a PRF, since it (quite literally) leaks part of the input.

The prerequisite that the compression function is a PRF is quite a weak requirement, too. Given that $H'$ (even if you did somehow come up with a compression function for it) simply fails this requirement, the security proofs for HMAC do not cover it. Further, pretty much all of the security proofs given in favor of HMAC assume that the attacker doesn't know the key. Those proofs are possibly invalid if this assumption is invalid.

So, to answer your question directly, HMAC requires an iterated hash scheme whose compression function is, as best as we can tell, a PRF. A generic cryptographic hash function, at least using the definition Wikipedia gives, is not strong enough to guarantee a solid MAC. But the PRF requirement is relatively weak, as even MD5 (which is completely broken as far as collisions go) still appears to satisfy it.


Is generating public key inevitably slow in classic Diffie-Hellman if the private key is large? Let's say I pick a 3000+ bit prime $p$ for which I also know that $q = (p - 1) / 2$ is a prime. If I've understood correct, then I can pick pretty much any $g$.

Is generating $g^x$ now inevitably slow for any large $x$ regardless of choice of $g$?

Do I still only select some $2n$ bit value for $x$ - where $n$ is the number of desired bits of security - in order to keep the calculation fast?

If $g$ is not in the order-$q$ subgroup, then one can easily calculate the last bit of $x$ from $g^{\hspace{.01 in}x}$.
-
If $\: g=2 \:$ or $\: g=4 \:$ then you can very easily compute small powers of $g$.

You could have a large lookup table for powers of $g$.

For example, you could store $\:g^{\hspace{.01 in}2^{\hspace{.01 in}2\cdot m}}\hspace{-0.02 in},g^{\hspace{.01 in}2^{\hspace{.01 in}(2\cdot m)+1}}\hspace{-0.02 in},g^{\hspace{.01 in}2^{\hspace{.01 in}2\cdot m}+2^{\hspace{.01 in}(2\cdot m)+1}}\:$ for each relevant value of $m$.

However, such a lookup table would make the benefit from

three sentences before this sentence mostly redundant.

You could choose $x$ so that there is a relatively short addition chain from $1$

(and any powers you have stored in a lookup table) to $x$, although this idea may well be vulnerable

to attacks that are similar to attacks on RSA private exponents with low Hamming weight.
-
You do that as long as $g$ is in the order-$q$ subgroup. $\:$ If, for whatever reason, you choose a

$g$ that is not in the order-$q$ subgroup, then you select some $\:(2\hspace{-0.03 in}\cdot\hspace{-0.03 in}n)\hspace{-0.02 in}+\hspace{-0.03 in}1\:$ bit value for $x$ instead.


How to define the statistical distance between two probabilistic algorithms? Let
$$
\begin{aligned}
F_{i} \colon \{\, 0,1 \,\}^* \times \{\, 0,1 \,\}^* &\to \{\, 0,1 \,\}^* \\
(k, x) &\mapsto y \\
\end{aligned}
$$
for $i \in \{\, 1,2 \,\}$.
As we known, for every oracle algorithm $\mathcal{D}$ the distance between $F_{1}$ and $F_{2}$ with respect to $\mathcal{A}$ is defined as

$$\mathrm{Dist}_{\mathcal{D}}^{F_{1}, F_{2}}(l) = \left\vert \Pr \left[ k \gets \{\, 0,1 \,\}^l, \mathcal{D}^{F_{1}(k, \cdot)}(1^l) = 1 \right] - \Pr \left[ k \gets \{\, 0,1 \,\}^l, \mathcal{D}^{F_{2}(k, \cdot)}(1^l) = 1 \right] \right\vert$$

I think it is meaningful to consider the computational indistinguishability of two probabilistic algorithms. Let $A_{1}$ and $A_{2}$ be two probabilistic algorithms. Formally, for $i \in \{\, 1,2 \,\}$,
$$
\begin{aligned}
A_{i} \colon S_{l} \times \{\, 0,1 \,\}^* &\to \{\, 0,1 \,\}^* \\
(\alpha, x) &\mapsto y \\
\end{aligned}
$$
Thus, $A_{i}(x) = A_{i}(\alpha, x)$ where $\alpha$ is uniformly chosen in $S_{l}$. We can still define the computational distance between $A_{1}$ and $A_{2}$,
$$\mathrm{Dist}_{\mathcal{D}}^{A_{1}, A_{2}}(l) = \left\vert \Pr \left[ \mathcal{D}^{A_{1}(\cdot)}(1^l) = 1 \right] - \Pr \left[ \mathcal{D}^{A_{2}(\cdot)}(1^l) = 1 \right] \right\vert$$

We know that the statistical distance between two functions is
$$2\mathrm{Dist}^{F_{1}, F_{2}}(l) = \sum_{f}\left\vert \Pr\left[ k \gets \{\, 0,1 \,\}^l, F_{1}(k, \cdot) = f(\cdot) \right] - \Pr \left[ k \gets \{\, 0,1 \,\}^l, F_{2}(k, \cdot) = f(\cdot) \right] \right\vert$$
However, I have no ideal how to define the statistical distance between two probabilistic algorithms.

In general, total variation distance—which is the specific metric you're talking about, one of many that might be called ‘statistical distance’—of two random variables $P$ and $Q$ is defined by $$\sup_A |\Pr[A(P)] - \Pr[A(Q)]|,$$ taken over all random decision algorithms $A$.  For the computational version, we simply restrict $A$ to be, say, a cost-limited algorithm that examines only $q$ parts of the variable—if it is a bit string, examines only $q$ bits; if it is a function, queries it at only $q$ points.

If the support is finite, the total variation distance coincides with $$\frac 1 2 \sum_x |\Pr[P = x] - \Pr[Q = x]|,$$ taken over the common support of $P$ and $Q$.

This notion is the same whether $P$ and $Q$ are supported on coin flips, integers, functions, perfectly normal beasts, sets, Riemannian manifolds, probabilistic algorithms, or bit strings (for some of these, to be meaningful, you may have to replace ‘random decision algorithm’ by ‘measurable function’).

Once you set down what a decision algorithm can do with a probabilistic algorithm, the answer will fall out.  The usual notion formalizing probabilistic algorithms, as you observe, is just a deterministic function with parameters for all the coin flips it needs—of course, on some inputs and coin flips the algorithm may diverge, which we formally represent by ‘returning’ $\bot$.  As such, it's not substantively different from your keyed functions.


Aes encryption -The relevance of static matrix in mixcolumns operation Can someone explain to me the relevance of the static matrix used for the mixcolumns operation in aes encryption.i.e the relevance of why the byte is multiplied by 2 + next byte multiplied by 3 + next byte +next byte

Well, how that matrix works is important for the security properties of AES.  To see why it is important, we need to consider state differences, that is, if we consider two different inputs to AES and how they both flow through the cipher, how does those two differ in the internal state of the cipher at various places.

The important property of the mixcolumn operation is that it is a Maximum Distance Separable (or MDS) operation.  That is, if we consider two distinct inputs to a single column of the mixcolumn operation, and the two inputs differ in $A$ bytes, and if the two corresponding outputs differ in $B$ bytes, then $A+B \ge 5$.

This implies that if two consider two inputs to a single column of the mixcolumn, if those two inputs differ in a single byte (that is, $A=1$), then the two outputs will always have different values for each byte (that is, $B=4$).

If you go through how this applies to AES, that means that if round $I$, two encryptions has an internal state that differs in a single byte, then at round $I+2$, the two encryptions will have states that differs in all 16 bytes (and hence AES has wonderful avalanche).

More generally, this behavior allows us to prove strength against differential and linear attacks; in that any differential or linear characteristic will necessarily go through a large number of sboxes; the resulting probability that the differential/linear characteristic will survive all those sboxes is negligible.

All this may not be true (or, at least, would be considerably harder to prove), if we replace the mixcolumn operation with an operation that is not MDS.


How to verify a trusted Issuer in U-Prove I work with U-Prove. In U-Prove they talk about a trusted Issuer, but I never saw how the trust is verified. The trust is essential, because the Verifier wants to know if the token was created with a trusted Issuer or not.

The U-Prove Cryptographic Specification V1.1 describes how to verify the signature of the Issuer. But there is no direct link if the signature is from a trusted Issuer or mayby from the Prover itself. The Issuer-Parameter could not be used, they are variable and created everytime a Prover wants to get a token.

Does someone has an idea or link where the trust establishment is described?

Updated question 24.02.2017

Maybe my first question was a bit unclear. Lets imagine that the Prover wants to create a token by himself. He creates the IssuerParameters and runs the protocol (Figure 8) by its own (this means he simulates the Issuer). Now he is the holder of the Issuer private key $y_0$. The Prover presents the created token to the Verifier. Signature (Figure 4) for the presented token is correct. But the Verifier does not know if it was a trusted or untrusted Issuer, who created the token with the Prover. The Verifier just knows that the received token relates to the private key $y_0$.

What I understand out of the Issuance protocol (Figure 8) and saw in the SDK-Implementation is, that every time the Prover requests a token, the IssuerParameters (generators $g_i$, $i$ = # attributes) and the private key $y_0$ (as well as $g_0$) are generated new.

For any credentials scheme, trust is defined out of the scheme. It might be your employer or your government.

Please note there is no clear separation whether signature is coming from Issuer or Prover. Signature on token public key $h$ is verified with Issuer public key (Figure 4) as a proof of equality of two logarithms. However, it is created by running a blind signature protocol running both by Issuer and User (Figure 8). There is no chance to create this signature without Issuer private key $y_0$.

Please consider to double-check Issuer parameters generation (section 2.3.1): once on scheme setup.


What is the difference between various modes in FPE? Format preserving encryption has three modes FE1( FFX) , FE2(VAES) , FE3(BPS) . All of them are based on Feistel Networks .Can somebody explain  how they differ from each other ?

Ff1,2,3 are basically inspired by LubyRack off constructions . At the core they differ in their round functions and key scheduling

FF1 supports greater range of lengths and a tweak

FF2 generates subkey for each iteration to thwart any side channel attacks

FF3 has tweaks is split and used in rounding function, also the reverse the sub-strings of given input string while using in round function,

Both FF1,FF2 has 10 rounds FF3 has only 8 rounds

Read more at NIST's 800 38 G draft


Why does knowing the number of points on a curve help solve ECCDLP? Perhaps, this is a really obvious question, but I am still having trouble understanding how this all fits together. Why is knowing the number of points on an Elliptic Curve helpful in cracking it?

Because it can help factor $n$ (as in “mod $n$”) if it's composite? Is it because knowing the order of different points is helpful, and the order divides the number of points total?

Why is so much effort put into finding an efficient way to count points?

Actually, we don't count points to attempt to break Elliptic Curves, a major reason we count points is to ensure that we can't.

If the number of points on the curve is $n$, then we know how to solve the ECCDLP problem in $\sqrt{n}$ time.  However, if we know a factorization $n = pq$, then we can use that factorization to solve the ECCDLP problem in $\sqrt{p} + \sqrt{q}$ time.  Note that this is distinctly smaller; if $n$ is 256 bits, then $\sqrt{n}$ is 128 bits; we believe that no one has the computational resources to do $2^{128}$ work.  On the other hand, if $p$ and $q$ is 128 bits, then $\sqrt{p} + \sqrt{q}$ is about 65 bits; we know that performing $2^{65}$ work is achievable in practice.

To avoid this potential problem, we generate curves until we find one with a prime number of points on it (or, a prime times a small cofactor); once we have that, the above observation is of no use to an attacker.

Now, that's not the only reason knowing the number of points on a curve is useful, however it is a major one.


Correlation Immunity Of 4 bit S Box I have a 4 bit S Box

byte[] S = new byte[16] { 0x9, 0xE, 0x5, 0x6, 0xA, 0x2, 0x3, 0xC, 0xF, 0x0, 0x4, 0xD, 0x7, 0xB, 0x1, 0x8 };

How can i calculate Correlation Immunity of this S Box

A boolean function $f:\{0,1\}^n\rightarrow \{0,1\}$ has correlation immunity $k$ if its walsh-hadamard transform coefficients
$$F(a)=\sum_{ x \in \{0,1\}^n} (-1)^{f(x)+a\cdot x}$$
are zero whenever $1\leq w(a)\leq k,$ where $w(a)$ is the hamming weight of $a$.

An sbox  $S:\{0,1\}^n\rightarrow \{0,1\}^n$ has correlation immunity $k$ if the functions $b \cdot S(x)$ all have correlation immunity $k$ whenever $b$ is not the all zero vector.

Operationally this means that all nontrivial output linear combinations of the sbox are uncorrelated with all linear combinations of $\leq k$ of the input bits, raising the complexity of divide and conquer attacks in stream ciphers.

In block ciphers this means that any useful linear characteristic must have output weight at least $k+1$ provided we also require that the walsh-hadamard coefficients are zero when $a$ is zero, i.e., the relevant functions are $k-$resilient.

For you $n=4.$