Send an encrypted question and return answer without decryption Oke bear with me for a minute.

Once upon a time someone mentioned a hypothetical way where you would send an encrypted question to Google and Google would return an answer without decrypting it.
As of lately i'v been searching for this hypothesis thinking there would be something about it on the internet, the problem is i can't find it.

So my question, is this theoretically possible, sending something encrypted and without the receiver knowing what it is return the correct information. Of course i get that when you encrypt every possible question and compare the 2 you could figure out the question and return the answer but i believe this was not how it was hypothetically done.

Has anyone of you ever heard of this? where does it come from?

I'm very sorry I could not provide a link to a paper or anything, I just cannot find anything about it.

Is it theoretically possible? Yes.

Is it practical? Absolutely not.

In your scenario, there are two approaches, but both are pretty much theoretical only.

First, there is fully homomorphic encryption (FHE). This means, you can do computations like addition and multiplication of ciphertexts and get another encrypted message. To actually have some of your usual search algorithms transferred into an "encrypted mode", you would also need things like checking for equality, etc., where you could use other cryptographic primitives, like zero knowledge proofs, OT, secret sharing, ...

But FHE is not practical, because it has a very high constant factor for the overhead. Basically it means, instead of using a modern top-notch computer, you have the performance of a 30 year old one (or older).

Then, there is searchable encryption... Basically it allows the server to produce a result for your search query. But that is not along the lines of a google search but more "find this string in the database". It is not the semantic search, but more a syntactical one, where you search for specific objects, attributes, etc.

But basically, it suffers from the same weakness as FHE: It is not practical. In cryptography, something is efficient if it is polynomial. But for practical usage this is not enough, because constant factors and exponents matter - even if they are theoretical efficient (e.g. $2^{1000}\cdot n$ and $n^{1000}$ are unusable in practice, but they are polynomial)


Solving hard problems in $\mathbb Z_{p}^{*}$ when $\mathbb p$ is close to $\mathbb 2^{n}$ Suppose, for some security parameter $n$ you choose a prime $p$ such that $p = 2^n+c$ for some relatively small $|c| < 2^m << 2^n$. I have seen such primes being called Pseudo-Mersenne Primes (if $c < 0$), Barrett Primes or Crandall Primes.

Does choosing such special primes $p$ as the group modulus for Discrete Logarithm Problem based Finite Field schemes in $Z_p^{*}$ in any way weaken the hardness of any known Discrete Logarithm based problems? I have seen the answers to this related question, which imply that if $|c|$ is small enough, the magnitude $n$ has to be doubled to counter the improved efficiency of the Special Number Field Sieve, but how small does $|c|$ have to be for that to apply?

For instance, suppose $n = 2048$ and $m = 512$, and the Hamming Weight of $c$ is approximately $256$. Is this sufficient to counter the SNFS, while still retaining the possibility of Barrett Reduction implementation optimizations?

The complexity of the number field sieve can be obtained from the expected size of the coefficients of the polynomial $f(x) = x^d + c_{d-1} x^{d-1} + \ldots + c_0$: if $c_i \le N^{\epsilon/d}$, then the expected runtime is

$$ \exp\left(\left(\left(\frac{32(1 + \epsilon)}{9}\right)^{1/3} + o(1)\right) (\log N )^{1/3} (\log \log N)^{2/3}\right),$$

or simply $L[1/3, (32(1 + \epsilon)/9)^{1/3}]$. When $\epsilon = 1$, we get $L[1/3, (64/9)^{1/3}]$ aka the GNFS, and when $\epsilon = 0$ (more accurately $o(1)$) we get the SNFS. Where does that put your example?

This requires analyzing the probability of smoothness of the numbers tested in the sieving phase, which, among other factors, depend on the size of the evaluated polynomial. The sieving process tests integers of the form

$$ F(a,b) = (a - bm) b^d f(a/b) = (a - bm)(a^d + a^{d-1}b c_{d-1} + \ldots + b^d c_0). $$

If we bound $a$ and $b$ to $M$, and $m, c_i$ to $N^{1/d}$, the size of $F(a,b)$ is bounded by $2(d + 1) M^{d+1} N^{2/d}$. In the SNFS, since both $m$ and $c_i$ are $o(1)$, the bound is much smaller, since it does not carry a $N^{1/d}$ factor anymore.

In your case, we have a mixed bag: the upper coefficients of the polynomial will be very small or 0, while the lower ones will be larger. For example, with degree $8$ and base $2^{256}$, your example results in the polynomial

$$ x^8 + c_1 x + c_0. $$

This polynomial is sparse, yes, but its expected $F(a, b)$ value size bound is not very far out from the general case: $2h M^{d+1} N^{2/d}$, where $h$ is the amount of nonzero coefficients in the polynomial. This is a constant improvement, but does not asymptotically alter the smoothness probability. So I expect your suggestion to be somewhat easier that a random prime, but not significantly so.

Since finding good polynomials seems to be an art in itself, it is hard to say when exactly the $c$ in $2^n + c$ becomes large enough to thwart the SNFS. A good rule of thumb would perhaps be to ensure that at least $c_0$ is $N^{1/d}$, by setting $c>2^{n/d}$. Since $d$ is an exponent in the size expression stated above, it will tend to be small: 1024-bit numbers are expected to have a $d$ of $6$ or $7$; 2048-bit will probably use degree $8$; and the optimal asymptotic expression for $d$ is $((3\log N)/(\log \log N))^{1/3}$, so it is very slow growing.

On a related note, the Schirokauer method for low-weight primes would not work here: it bounds the $c$ in $L[1/3, c]$ complexity of the NFS for an integer of (signed) weight $w$ as

$$ (32/9)^{1/3}((\sqrt{2}w - 2\sqrt{2} + 1)/(w - 1))^{2/3} < c < ((32/9)(2w-3)/(w-1))^{1/3}. $$

Replacing $w$ with $256$ results in the bound $1.9215 < c < 1.9217$, barely distinguishable from the GNFS.


Can I find two specific words with the same md5 hash? I want to find two strings containing special words like "yes" or "no", mixed with random characters, for which the MD5 hash is equal.

An example of what I'm looking for:

First string : YES/d6g45d78h74jfhcf     MD5 : 4cf349066ce85e0c947eb1d0c94c13b1
Next string  : NO/djf986f98edf8dfv4     MD5 : 7fdefd9bd8a46db9b48a323e8e366150

As you can see the MD5 hashes are different; Is it possible to change the random characters to get equal MD5 hashes?

What you want is called a chosen prefix collision. Given p1, p2 you want to find m1, m2 such that hash(p1 || m1) = hash(p2 || m2).

Generic attack

The generic attack to find this, is creating messages starting with p1 and just as many starting with p2. Thanks to the birthday problem you'll find a match after around 2n/2 messages.

For a 128 bit hash like MD5, this means you need about 264 operations. This is feasible in principle, but exceeds your budget. I guess it costs 200'000\$ if you use GPUs and 5'000\$ if you already have developed appropriate ASICs.

Exploiting MD5's weaknesses

MD5 is a broken hash function. Finding normal collisions is very cheap, but that doesn't help you. Luckily(for you) there is also a chosen prefix attack against MD5.

According to a paper from 2009 this costs around 251 compressions. Which corresponds to to about 18 GPU days on a GPU that cost 200\$ in 2009.

So I estimate that the attack costs 10-20\$.

There are two caveats:

The random characters are no printable ASCII characters, but rather random bytes.

It might be possible to modify the scheme to only emit printable ASCII, but I didn't investigate that.
There will be more random characters than your example has, probably somewhere between 70 and 130.


Does some method exists to decrypt using some encryption keys (not all) I'm searching for a method/algorithm that is able to manage different encryption keys and guarantee that some subset of that keys is needed to perform the decryption (not all).

For example:
$$D_{K1, K2}(E_{K1, K2, K3}(X)) = D_{K1, K3}(E_{K1, K2, K3}(X)) = D_{K1, K2, K3}(E_{K1, K2, K3}(X)) = X$$

A real-world like example is where I have a bank account shared with my life, and I needs to withdraw money given only one sign.

So, used $$K_i \ with \ i \in {1, 10}$$ to encrypt some message, I need only $k<10$ keys to decrypt my message.

Extending from my comment:

  Yes it exists and is known as "threshold decryption". See Shamir's Secret Sharing. You may encrypt each share with with the respective preshared symmetric key for each party, or otherwise distribute the shares. Alternatively you may use asymmetric solutions instead which tend to have less ciphertext expansion than SSS at the cost of asymmetric operations.

For an example I'll use an online implementation of SSSS

The following example splits a secret message "my secret root password" into 5 components where any 3 may be used to recover the message.

% ssss-split -t 3 -n 5
Generating shares using a (3,5) scheme with dynamic security level.
Enter the secret, at most 128 ASCII characters: my secret root password
Using a 184 bit security level.
1-1c41ef496eccfbeba439714085df8437236298da8dd824
2-fbc74a03a50e14ab406c225afb5f45c40ae11976d2b665
3-fa1c3a9c6df8af0779c36de6c33f6e36e989d0e0b91309
4-468de7d6eb36674c9cf008c8e8fc8c566537ad6301eb9e
5-4756974923c0dce0a55f4774d09ca7a4865f64f56a4ee0

As demonstrated

% ssss-combine -t 3
Enter 3 shares separated by newlines:
Share [1/3]: 3-fa1c3a9c6df8af0779c36de6c33f6e36e989d0e0b91309
Share [2/3]: 5-4756974923c0dce0a55f4774d09ca7a4865f64f56a4ee0
Share [3/3]: 2-fbc74a03a50e14ab406c225afb5f45c40ae11976d2b665
Resulting secret: my secret root password

Instead of splitting the message, it is cleaner to split the key used to encrypt (and authenticate) the message. These key shares may then be encrypted using per-participant preshared keys or with public keys.

There are more threshold decryption options but they are more complicated. For more information these slides should be helpful. I must add that they reference trusted dealers, you may use verified dealers instead so they cannot cheat the protocol.


Schnorr Digital Signature I tried to rewrite the Schnorr signature algorithm for elliptic curves but I wanted to be sure to have not done any errors. So I would be very happy if someone could look over this algorithm and tell me if I have done anything wrong, or not precise enough:

Let $E$ be an elliptic curve over a finite field $\mathbb{F}_q$ (first question, is it here as in the ECDSA, that either $q=p$ an odd prime or $q=2^m$?) with parameters such that $E$ is a cryptographically safe curve.

Key Generation:

Choose $P\in E(\mathbb{F}_q)$ of prime order $l$, where $l$ is a large prime.

Choose $1 < a < l$ random and calculate $Q = a*P$. Then the public information is $E, \mathbb{F}_q, Q, P$ and the private signature key is $a$.

Signature Scheme:

Choose a random $1 \leq k < l$
Compute $S_0 = kP = (x_0,y_0)$
Compute $s_1 = H(m||x_0)$, where $H$ is a hash function, $x_0$ is the integer value of $x_0$ and $m$ is the message.
Compute $s_2 \equiv k + a*s_1 \text{ (mod }l)$

The digital signature is $(S_0,s_2)$ and Alice sends $(m, (S_0,s_2))$ to Bob.

Verification

Bob verifies if $s_2*P=S_0+H(m||x_0)*Q$.

This works since: $$s_2*P=S_0+H(m||x_0)*Q$$ $$\Leftrightarrow s_2*P-H(m||x_0)*Q = S_0$$ $$\Leftrightarrow (k+a*s_1)-H(m||x_0)*a*P = S_0$$ $$\Leftrightarrow kP + a*H(m||x_0)*P-a*H(m||x_0)P=S_0=k*P$$

Yes, pretty much the same groups usable for ECDSA are usable for Schnorr signature. That was in [Sc91] (see bibliography in this question):

  It is possible to implement the above signature and authentication scheme using a finite group $G$ other than the subgroup $\mathbb Z_p^*$ of units in  $\mathbb Z_p$ (..) Examples of suitable groups are e.g. class groups and elliptic curves $E(K)$ over a finite field $K$.

It looks like you invented yet another variant of the Schnorr signature algorithm for elliptic curves, not among the about 6 in this answer. Yours sends a group element rather than a hash as the first part of the signature (thus more directly matching the transformation to signature of the Schnorr indetification protocol, and allowing a more direct proof of security). This has a strong taste of EC-FSDSA (Elliptic Curve Full Schnorr Digital Signature Algorithm) of ISO/IEC 14888-3 (OID 1.0.14888.3.0.12), but:

For some reason you compute $H(m\|x_0)$ rather than $H(x_0\|y_0\|m)$ in said standard; hereafter I write $H(\dots)$. For an ideal hash and proofs in the ROM, hashing $m$ first or second is immaterial, and I can't decide if it makes any security difference for practical hashes. Not hashing $y_0$ might cost some security.
Your verification procedure omits to verify that $S_0$ is a point on the curve, which seems risky since you perform point addition on that. The standard mandates this check.
My understanding is that the standard does $Q=-a\times P$ (as suggested by Schnorr as soon a [Sc89]), so that verification can compute $s_2\times P+H(\dots)\times Q$ and compare it to $S_0$, with two advantages:

the computation of $s_2\times P+H(\dots)\times Q$ can use the simplest forms of Shamir's trick, or others
checking that $S_0$ is a point on the curve becomes redundant.

Note: for elliptic curves $y^2\equiv x^3–3x+b\pmod p$ at least (including NIST's FIPS 186-4 curves over prime fields), while you are at not hashing $y_0$ and using something non-standard, you could as well omit $y_0$ from the signature, with verification computing $s_2\times P+H(\dots)\times Q$ and comparing it's $x$ coordinate to $x_0$. That shortens the signature from $6b$ to $4b$ for $b$-bit security, and (for ideal hash) costs at most 1 bit of security (perhaps nothing), since $y$ can be found from $x$ within sign.


Can Add and Multiply On Cipher Text achieve all operations? A Fully homomorphic encryption scheme needs to support an evaluate function that can do add and multiply operations on cipher text.

Can we do all kinds of complex operations on cipher text like search, sort etc using just add and multiply ?

If addition and multiplication are preserved, then we can evaluate arithmetic circuits over the encrypted data.

It seems that your confusion about the class of problems that we can compute stems from the fact that you are envisioning boolean circuits in which we perform operations on the bitwise representations of the input. This is not an FHE question per se, but rather a question regarding the difference between the computational models of boolean circuits vs. arithmetic circuits. To understand the problems that can be computed with this model of computation, take a look at this paper. A relevant portion:

  The definition above shows an evident difference between arithmetic circuits and Boolean circuits.While Boolean circuits can perform operations on the "bit representation" of the input field elements,that are not necessarily the arithmetic operations, arithmetic circuits cannot. Nevertheless, most algorithms for algebraic problems fit naturally into the framework of arithmetic circuits.

In regards to why they defined FHE this way, it follows the definition of  Ring Homomorphism. By definition, a ring homomorphism is a function between two rings that respects addition and multiplication.

In practice, recent research on FHE studies lattices since ideal lattices yield both additive and multiplicative homomophisms.


Is there a guarantee that for each possible hash y there exists a number x such that with hash function H, H(x) = y? Specifically talking about SHA-256 here and its involvement in Bitcoin, this was a question someone asked me which I didn't know the answer to. Yes, I am aware that SHA-256 can only have a hash from $0$ to $2^{256} -1$, so it is fine for this to be the range for our y. I am asking within the range, is there a guarantee that there is an x for each possible y.

I ask this mainly because I wonder if there is anything that guarantees that a new Bitcoin block can always be made with a hash below its target.

TL;DR: there is no mathematical certainty that every output value of common cryptographic hash functions is reachable, but for most that's overwhelmingly likely. A notable exception is double-SHA-256 (SHA256d) used in Bitcoin mining, where overwhelmingly likely there are some unreachable outputs.

For an idealized 256-bit hash, it becomes likely that every possible hash value $y$ is reached by hashing some $x$ when there are about $2^{264}$ possible values of $x$, including all 33-byte $x$; then odds that some $y$ is not covered become vanishingly small: less than one in $2^{b-264}$ if there are $2^b$ possible values of $x$; so while there is never a guarantee, it is practically certain that all $y$ are covered when we allow say 40-byte $x$: odds of the contrary are less than $2^{-56}$.

Argument: a hash can be idealized as a random function. The problem of if a random function covers all its image set is the coupon collector's problem. If the destination set has $n$ elements, the expected number of elements in the source set to fully cover the image set is $E(n)=n\log n+\gamma\,n+{1\over2}+O({1\over n})$ where $\gamma\approx0.577$ is the Euler–Mascheroni constant; and odds of not covering the input set after hashing $E(n)/\epsilon$ elements are less than $\epsilon$. Changing $n$ to $2^b$ for a $b$-bit hash, we get $E(2^b)\approx2^b(b\log(2)+\gamma)$ and $\begin{align}\log_2(E(2^b))
&\approx b+\log_2\left(b+{\gamma\over\log(2)}\right)+\log_2(\log(2))\\
&\approx b+\log_2(b+0.833)-0.528766\end{align}$

SHA-256 is a Merkle-Damgård hash using a compression function built per the Davies-Meyer construction. The problem of if all $y=\operatorname{SHA-256}(x)$ are reached reduces, up to 55 bytes hashed, to if all $\operatorname{Enc}_x(IV)$ are reached for a certain constant $IV$ and a certain block cipher $\operatorname{Enc}$ where $x$ is the key, and key scheduling encompasses the block padding. For an idealized block cipher the same analysis as for an idealized hash would hold, so we'd cover all values with overwhelming odds. SHA-256 uses an ARX block cipher and I see no reason why it would significantly differ from an idealized one, but that's a weak argument.

We can be more positive that we get full coverage when we allow two rounds (say, 100-byte hashes), because the problem is now if all $\operatorname{Enc'}_{x_1}(y_0)\boxplus y_0$ are reached where $x_1$ is the 36-byte second block, and $y_0$ is allowed to vary among the nearly-full set of 32-byte values reachable with the first round ( $\boxplus$ is 256-bit addition without carry across 32-bit boundaries). Still, there is no mathematical guarantee.

In Bitcoin mining, what's computed is $y=\operatorname{SHA-256}(\operatorname{SHA-256}(x))$. We are, for the outer hash, much below the coupon collector's bound and overwhelmingly above the birthday bound, therefore it is overwhelmingly likely that there are some values of $y$ not reached.

I second Dave Thomson's comment below.


Secret sharing scheme with ability to add or update share number I would like to have a secret sharing scheme with the following properties:

Generate secret $S$ a split it to $N$ shares $(s_1, s_2, ..., s_N)$
Require $k$ of $N$ shares in order to reconstruct secret $S$
Update $N$ to $N+1$ and generate new share $s_{N+1}$ (everything remains
the same, $N$ shares not changed)

The scenario is that I use Shamir secret scheme to split secret $S$ into for example 4 parts and require 2 of them to be present in order to reconstruct $S$. In that case if I would like to reconstruct S then I have to also input scheme type, i.e. 2 of 4.

What if I need to update number of parts but need to preserve existing shares and be able to reconstruct the same secret $S$? Is there a way how to do it?

With Shamir's Secret Sharing you can add as many shares as you want, as long as the threshold and the secret is unchanged.

You can see that neither the generation of the polynomial that produces the shares nor the reconstruction of the secret by polynomial interpolation require the parameter $N$ (number of shares), but only the threshold $k$.

Of course the number of shares $N$ should obey $N\leq p-1,$ since they need to be obtained as polynomial values at distinct points of the field $F_p$ and one point, usually zero, is reserved for the secret. You can increase $p$ if needed, but shares need to then be recomputed modulo the new prime you choose.


How effective noise based voice encryption against attack? In WWII the primary way of encrypting radio broadcasts was to have the broadcaster transmit a signal with noise added from record, while the receiver would have an identical copy of the record subtracting the noise.

Assuming that the noise is totally random, and the record is never replayed. How would one attack it?

While this isn't strictly a cryptography question, do modern encrypted radios that work in frequencies that are too low to transmit digital data like this still use this principle?

In WWII the primary way of encrypting radio broadcasts was to have the broadcaster transmit a signal with noise added from record, while the receiver would have an identical copy of the record subtracting the noise.

This is referred to as "scrambling", which is "encryption" in the analogue domain.

  Assuming that the noise is totally random, and the record is never replayed. How would one attack it?

Randomness of noise is quite a vague concept. You seem to be hinting at some kind of "one time pad" here. I'll first hint you why this isn't a thing for a scrambler, then give you some hints at possible attacks.

One time pads are carried out using a xor operation. A key property of the XOR operator is that when the distribution of $s$ is equiprobable (50% 1's, 50% 0's, which hold for the pad of a one time pad), the resulting ciphertext $e=m\oplus s$ will also have this probability, independently of the distribution of $m$. This is what makes the one time pad unbreakable.

Compare this to a scrambler. A scrambler adds the message to the pad: $e=m + s$. The plus operator does not have this equiprobability; it even, when $m$ and $s$ are independent, mixes the frequency spectrum! (To see this: the Fourier transform is a linear operator)

Let's break some analogue scramblers, using digital technology! Let's assume our message is speech, which feels like a pretty broad assumption. Speech has some cool properties; one of which is that it has a lot of repetition it vowels, and that most information is below 3000 Hz.

You can, for example, try a windowed cross-correlation in windows of around 30 milliseconds. The peaks of the cross-correlation give you an idea of the repetition frequency of certain vowels (out of which you even might extract the vowels). You may now attempt averaging out over different shifts, which should give you your vowels back.

A bunch of other statistical attacks can be carried out here. You can try yourself easily in MATLAB: sample a sine wave, add white noise, and try the above trick. Speech is a bit more difficult, but should be doable.

As always, give me a ping if you want me to go more in depth. I have no real references here, as I have this in my head from my signal processing and statistics courses.

  do modern encrypted radios that work in frequencies that are too low to transmit digital data like this still use this principle?

I cannot really answer that question, sadly. e-sushi made a comment that points to this question though, which seems to answer your question partly.


What are good combinations of public key algorithms or primitives for long term security? There has been talk in literature about doing multiple encryption with different block ciphers or stream ciphers several times before, and the benefits and risks of such efforts. There may be hidden assumptions or weaknesses in designs of symmetric cipher algorithms, or perhaps they have been deliberately sabotaged by a hidden weakness by the design team, while on the other hand implementing multiple symmetric cipher algorithms introduces more ways that the code can go wrong and potential security problems in the implementation itself.

Focus on multiple symmetric ciphers to me strikes me as a misplaced concern, considering that the hardness assumption for symmetric ciphers seems largely based on the hardness of searching the keyspace. While its possible that there are breaks in one modern symmetric cipher that doesn't break another, it is starting to seem less likely.

Public key cryptography however relies on many different hardness assumptions, and so it seems strange to me that there hasn't been an effort to come up with protocols for multiple encryption with algorithms that have different hardness assumptions. The RSA problem is broken by factoring the modulus, elliptic curve cryptography is broken by discrete log, lattice based cryptography is broken by solving the shortest vector problem, and so on. And it seems all hidden subgroup problems for finite Abelian groups are broken in quantum computers (discrete log and factoring) and some groups that are 'close' to Abelian groups are also broken on quantum computers (factoring in quaternion groups for example.)

If we were to build a protocol or implementation that relied on multiple cryptographic primitives or algorithms for key exchange and signing, which  would be appropriate for such a scheme? Obviously some algorithms are more compute intensive than others, and some users would prefer more performance over security so we might want to rank them in terms of performance and a guess on the hardness.

I have in mind creating certificates that are grounded in multiple hardness assumptions, so if one link in the chain is broken, the whole scheme doesn't fall apart.

For the signatures, hash-based signatures provide a nice solution to your problem: You can use so called hash combiners to instantiate the signature. These are functions that construct a hash function given two or more hash functions and preserve certain properties as long as at least one of the hash function has this property. For example the concatenation combiner:
$C_{H_1,H_2}^{\|}(M) = (H_1(M)\|H_2(M))$

preserves collision resistance and second preimage resistance.

If you use hash functions based on different design principles, e.g. SWIFFT as one that has certain security guarantees steaming from the hardness of lattice problems and one classically constructed one like SHA-3, you can achieve good redundancy.

The big advantage is, that you do not have to implement two different schemes but only one: You would have to implement two different hash functions for message compression anyway but in addition you would also have to implement two "fixed length" signature schemes for multiple signatures.


Is Identity-based encryption used in the wild? I have a curious question.
Is Identity-based encryption used in the wild?

SM9 (GM/T 0044.5‐2016) is an IBE scheme widely used in China. Unfortunately most of the documents are in Chinese with no English translations available. But a description of basic SM9 scheme is available on eprint and an open source implementation is in the OpenSSL fork GmSSL


Transfer and hide ciphertext with hash functions? Can hash functions be used to transfer and hide ciphertext?

This somewhat similar locked question, "If cryptographic hashes are completely unique, could they theoretically be used to transfer data?", received several cogent no answers, but consider this:

Alice and Bob share a secret:

/p68J5gd3%}"jd9fkg;BtiAraGgsioe2:L<76e7emOngehf]jfur80}{_kod*6

Alice adds her ciphertext JWHSM to her copy of the secret:

/p68J5gd3%}"jd9fkg;BtiAraGgsioe2:L<76e7emOngehf]jfur80}{_kod*6 || JWHSM

Now she hashes (secret + message) with SHA-512 and sends the hash to Bob.

Bob knows that he has to do a bit of computation and find the ciphertext that will concatenate and resolve to the hash value he has been sent by Alice, and he knows how many characters there will be (5 in this case).  So, in effect, Alice sent Bob a message he could not immediately read, but he can resolve it.  They want to defeat certain aspects of traffic analysis, and they suspect that Mr. Attacker might be able to make easy preimage attacks on every hash they send--to which they respond "So what?"

Can hash functions be used to transfer and hide ciphertext in this unorthodox, expensive manner?

Yes, you can use a hash to "hide" messages like that. However, I don't see any advantage of this compared to normal symmetric encryption, which already is able to return a well randomized ciphertext.

Randomization in itself is not steganography as I've understood it. A fully randomized message may stand out, both on its own and when simply copied into a message. Let's perform a little thought experiment: with a bit of trouble you can create a block cipher with a block size identical to the output size from a hash function. I don't see how your scheme would be any different from that particular cipher or fare any better in hiding the plaintext / ciphertext.

Lets look at the drawbacks:

First of all, there is this relatively high amount of work to be performed by the receiving party.
Second, the method scales terribly bad. You can probably only have $2^{32}$ plaintext / ciphertext pairs, and that's already stretching CPU resources.
Thirdly, the ciphertext is much larger than it needs to be, even if it is static and limited to the output size.
And finally, as there is no IV, it is not semantically secure if you'd send multiple messages as the ciphertext would repeat.

As for the 4th point: introduction of a fully random IV send with the ciphertext is of course possible, but it would expand the ciphertext even further.

I can see some advantage if this code is used when a hash is already used, e.g. when authenticating an unencrypted message (or encrypted message with a known size) in signature generation or HMAC. In that case the other data is already present and doesn't need to be guessed. The scheme could then be used to create a subliminal channel, which is related to steganography I guess.

Of course you would want to make sure that the additional message is stuck at the end, rather than in front, so that you only have to hash the send message only has to be hashed once (except maybe for the last block). As for signature generation: you'd probably want to use PKCS#1 v1.5 padding to retrieve the full hash. Note that for signatures an adversary will be able to see that the original hash / signature doesn't verify, which kind of negates the hiding of the message.


Encryption/Decryption Modulo function I have an encryption line of code as follows:

a^x mod y = rem // ^ is the power fx

Given x, y, amd rem during decryption, how can we find the value of a?

I was thinking of using  xth root of rem mod y, but it's not working; probably because of modulo congruence.

Can someone please guide me as to what needs to be done?

You will have to find $d \in \mathbb{Z}_{\varphi(y)}: x * d
 \equiv 1 (mod\ \varphi(y))$. Then $rem^d=a^{xd}=a^1$ (Euler's theorem) in $\mathbb{Z}_{y}$. To do so you will need to calculate the prime decomposition of $y$ so you can calculate the value of Euler's phi ($\varphi$) in $y$. Then the problem of finding $d$ reduces to the problem of finding inverse (extended Euclidian algorithm on the power and the modulus -- find $a,b$ such that $1=GCD(x,\varphi(y))=ax+b\varphi(y)\equiv ax (mod\ \varphi(y))$). Note that the inverse does not exist if $GCD(x,\varphi(y))\neq1$.

E.g. in RSA the public key ($e$ that corresponds to your $x$) has an inverse ($d$) computed during the key generation and the inverse is then stored in the private key.


1 out of n oblivious transfer So I read some stuff about oblivious transfer and came a ross that 1 out of 2 OT can be used as a black box to build 1 out of n OT. At first it seemed trivial just feeding in 4 messages and 2 chooser bits but then I realized it's not that trivial since it doesn't guarantee security.
How is 1 out of 2 OT used to build 1 out of 4 OT if we can use 1 out of 2 OT as a black box?

The sender chooses log n pairs of secret keys (say, for encryption). Then, each number between 1 and n is naturally associated with a subset of exactly log n keys. The protocol then works by running log n 1-out-of-2 OTs where the receiver asks for the keys that are associated with its input (number between 1 and n). Finally, the sender encrypts each of the n messages with the subset of keys associated with the number (using encryption so that without all keys nothing is learned).
It is not difficult to formally prove the security of this using simulation (as long as the OT is secure for malicious adversaries, this is also secure for malicious adversaries).
This solution goes back to a paper by Benny Pinkas [1].
[1] Moni Naor and Benny Pinkas. 1999. Oblivious transfer and polynomial evaluation. In Proceedings of the thirty-first annual ACM symposium on Theory of Computing (STOC '99). Association for Computing Machinery, New York, NY, USA, 245–254. DOI:https://doi.org/10.1145/301250.301312


Is PGP's way of maintaining email security optimal? I read a book called "computer networking: A top-down approach". It talked about how PGP creates an email message between Alice and Bob to maintain confidentiality, integrity, and authenticity. Let me define some terminology and the procedure at the very high level:

m :              email message
H() :            cryptographic hash function
Ka_priv_sign() : signing using Alice's private key
|| :             contacternation
Ks :             session key
Ks_enc():        encryption using session key
Kb_pub_enc():    encryption using bob's public key
blob :           The final data blob Alice sends to Bob.

To send an email to Bob, Alice first signs the message with her private key:

m || Ka_priv_sign(H(m))

Alice then encrypt the message and signature

blob = Kb_pub_enc(Ks) || Ks_enc(m || Ka_priv_sign(H(m)))

Alice will send this final blob to Bob.

The cryptography seems to have a problem here since digital signature is applied before encryption and encryption does not provide data integrity.
I think the right order of operation should be:

Alice first encrypts the message with the session key and encrypt the session key with Bob's public key:

Kb_pub_enc(Ks) || Ks_enc(m)

Alice then signs the encryption results after hashing them:

blob' = Kb_pub_enc(Ks) || Ks_enc(m) || Ka_priv_sign(H(Kb_pub_enc(Ks) || Ks_enc(m))))

Questions:

Is PGP still using the way that the textbook describes today? Do you think my construction is better?

Yes, PGP's sketch as in the question is sound by today's textbooks on cryptography, and reasonable from a computer security standpoint. Applying digital signature then encryption (critically: including on the signature) does provide data integrity and confidentiality for the message.

PGP's way of doing things has the characteristic that one able to decipher the message can turn it into a cleartext message signed by Alice, that anyone (knowing and trusting Alice's public key) can verify. In many cases, that's a feature.

It can occasionally become a weakness when PGP is misused. Assume Alice sends a message to Mallory like "I love you", signed by Alice, encrypted to Mallory; Mallory can decipher the message, and forward it to Bob, still signed by Alice, perhaps even re-encrypted to Bob; Bob, if he does not understand what PGP signature really means, can be tricked into thinking Alice cares for him. That's also Alice's fault: she should have signed a more context-free message, like "I love you Mallory" (and be more selective). More examples here (which takes the debatable position this is a defect in PGP).

There's also the argument, legitimately made by some computer security material, that with sign-then-encrypt as in PGP, the receiver deciphers something unauthenticated, and that can allow exploitation of software bugs in the decryption, or after. In the context of PGP, that argument does not hold: PGP is designed to support unauthenticated enciphered messages; and one legitimately wants to be able to read messages that one is not able to authenticate, for lack of the alleged signer's trusted public key.

Update: this answer is only about the soundness of the overall structure of the PGP format as described in the question; I do not touch "optimality", for lack of a definition; nor try to examine the detailed PGP formats and implementations (which are not state of the art), as discussed in that other answer.


Using crypto to build a clone resistant system My question is related to using cryptography to build clone resistant system.

I am building an embedded system with ARM based commodity hardware board. Thus the intellectual property which makes the product differentiated lies all in software. What kind of cryptographic measures can be used so that the software on my system even if copied out of a genuine product can't be used to run on another board of same type and build a cloned fake?

Basically, some sort of hardware platform authentication is required in software. It should be practically unfeasible to bypass this authentication step by tampering software binaries. What options do I have?

That's actually a really interesting question. Mostly because I think there is no really good solution.

However, considering that we are putting more and more computing power into all devices and more and more of their value is derived from the software it seems to be very relevant for the future.

If you want something that can even remotely be called cryptography you should define your security model. Given that you are using a commodity board what is stopping your software from running on a different one of these boards? Clearly nothing, because that's how you are going to produce your devices. So the only option you really have is to keep your software secure in the first place.

I actually think solving this problem is the reason why many devices are IoT devices in the first place. It allows you to put the important parts of the software on the server and authenticate your users when they want to use it.
Let's say this is

Option 1: Keep parts of software on your own hardware and restrict access.

Now, there are a lot of other techniques that are somehow trying to achieve your goal...

Option 2: Trusted execution environment (careful, that article is basically advertisement) A way to protect your software from being extracted from the device. Something like Intel's SGX or ARM Trustzone.

Option 3: Make a mess

A combination of the following might give you sufficient security:

Whitebox crypto: Hide cryptographic keys that your software might be using. Afaik all schemes are broken. However there is no shortage of companies trying to sell it to you. (Sad, it doesn't even have its own Wikipedia article.)
PUF: To achieve hardware binding (that's the common term for making something run only on your boards) you use some hard to fake property of the hardware like the initial state of the RAM when turning the device on.
Code obfuscation: Add unnecessary abstraction and redirection and such to your code so that somebody cannot reverse engineer it with reasonable effort and remove all the safeguards you have put in.

Option 2 seems much more solid but a combination of these might help mitigate sufficiently many attacks for you to confidently deploy in a scenario where you don't have a TEE or the option to do things online.


Comparing stronger vs. weaker assumptions If I have to argue that an assumption A is stronger than B, should I argue this way:-

An adversary breaking the security of A does not translate to breaking the security of B. But, if an adversary breaks the security of B, it can break A too.

Right? or, there are other ways to compare stonger vs. weaker assumptions.

Yes you are right. Essentially when we say $A$ is a stronger assumption than $B$, what we mean is that assumption $A$ implies assumption $B$. $A$ implies $B$ tells us that:

if $A$ is true, then $B$ must be true.

$A$ implies $B$ is also equivalent to $\neg B$ implies $\neg A$, thus

if $B$ is false, then $A$ must be false.

In cryptography, assumptions often are related to the hardness of some problems. In this context, stronger assumptions are "easier" problems that can be reduced to  weaker assumptions that are "harder"problems (solving the harder problems means the easier ones are also solvable). For example, say we have the following two assumptions:

$A$: factoring an integer $n$ is difficult;
$B$: factoring an integer $n$ with only large prime factors is difficult.

Clearly, if $A$ is true, then $B$ is true; if $B$ is false, $A$ is false. If we can solve $B$ then we can use the algorithm that solves $B$ to solve $A$.


Where is CFB-MAC defined? I can find descriptions of using CFB mode to create a MAC and even implementations, but cannot find any standard or papers analyzing its security bounds.

Is there a standard for CFB-MAC?

Where can I find an analysis of its security bounds?

According to Handbook of Applied Cryptography (15.3.2, ii), ANSI X9.9 (which SEJPM mentioned in the comments but I have no access to) defined CFB-MAC only as a compatible alternative to CBC-MAC:

The X9.9 MAC algorithm may be implemented using either the cipher-block chaining (CBC) or 64-bit cipher feedback (CFB-64) mode, initialized to produce the same result (see Note 15.1).

With a segment size equal to the block size (so 64 bits with DES) and using the first message block as IV, the two are indeed equivalent. So this case of CFB-MAC clearly has all the properties of CBC-MAC.

However, the first definition of CFB MAC seems to be from FIPS 81 (DES Modes of Operation, see Appendix F):

A MAC may be generated using either the CBC or the CFB mode. [...]
In CFB authentication, a message is encrypted in the normal CFB manner except that the cipher text is discarded. After encrypting the final Kbits of data and feeding the resulting cipher text back into the DES inputblock, the DES device is operated one more time and the most significant M bits of the resulting DES output block are used as the MAC.

The example shows 8-bit CFB MAC using an IV, so clearly it was defined for arbitrary CFB modes.

What remains unanswered is how the security compares to that of CBC-MAC when segment size differs from the block size. However, the use of segments is somewhat historical anyway, so it is only a curiosity.


In Paillier homomorphism how do you substract? I'm trying to learn homomorphism so the problem may also be in my code (which I will include).

I want to compute $a - b$ where $a$ is bigger then $b$. In order to do this I tried to compute $\frac{a}{b}$. However when I decrypt this I get garbage. Or ciphertext $c$ is not in $\mathbb{Z}^{*}_{n^2}$.

Now because the problem may also be in my code here it is:

import java.math.BigInteger;
public class Main {
    public static void main(String[] args) throws Exception{
        Paillier pp = new Paillier (2048);
        BigInteger a=pp.encrypt(BigInteger.valueOf(100000));
        BigInteger b=pp.encrypt(BigInteger.valueOf(10000));
        BigInteger c=a.divide(b);
        c=c.remainder(pp.getNsquare());
        BigInteger res=pp.decrypt(c);
        System.out.println("res = "+ res);
    }
}

And I used this library

I also tried to see what happens if you multiply $b$ with $-1$ but that just gave me garbage. Anyone know how to do this?

So so far I tried

$c = \frac{a}{b}$ which tends to result in $c=0$ and unable to retrieve $c$
$c+2^{2047}=\frac{a \times 2^{2047}}{b}$ which results in $c$ is a large number
and $c$ is negative some larger number
$c+2^{2047}=\frac{a \times 2^{2047}}{b}$ inverse mod $N^2$ which results in $c$ is a
large number and $c$ is negative some larger number
$c+2^{2047}=\frac{a \times 2^{2047}}{b}$ remainder $N^2$ which didn't decrypt.

Is this a problem in my code or in my understanding of crypto?

Let $c_a$ be the encrypted version of $a$, and $c_b$ be the encrypted version of $b$. What you want to compute is $c_c$ which is the encrypted version of $a-b$, so that when you decrypt $c_c$ you get $c=a-b$.

Paillier supports a homomomorphic addtion of ciphertexts to get an encrypted version of the sum. The actual mathematical operation it takes to get this is modular multiplication. In otherwords, multiplication in the ciphertext domain results in addition in the plaintext domain.

Paillier also supports multiplication of a ciphertext value and a plaintext value. This is achieved by modular exponentiation.

To achieve what you want here, you need to negate $c_b$ by multiplying by $-1$ in the ciphertext domain. To achieve this operation (an encrypted negation of $b$, given only the encryption of $b$, $c_b$), you would do $c_b^{-1}\bmod{n^2}$. That would given you an encryption of $-b$. You homomorphically add that value to $c_a$ (which is achieved via modular multiplication on the ciphertexts) to get $c_c$.

I have an example of subtraction in Paillier in the library I wrote. I also had a writeup about negative numbers in Paillier you may find interesting at the old Google Code host.


Computing p and q from private key We are given n (public modulus) where n=pq and e (encryption exponent). Then I was able to crack the private key d, using Wieners attack. So now, I have (n,e,d). My question is, is there a way to calculate p and q from this information? If so, any links and explanation would be much appreciated!

It's actually fairly easy to factor $n$ given $e$ and $d$.  Here's the standard way to do this:

Compute $f = ed - 1$.  What's interesting about $f$ is that $x^f \equiv 1\  (\bmod n)$ for (almost) any $x$.
Write $f$ as $2^s g$ for an odd value $g$.
Select a random value $a$, and compute $b = a^g \bmod n$.
If $b = 1 $ or $-1$, then go back and select another random value of $a$
Repeatedly (in practice, up to $s$ times):

compute $c = b^2 \bmod n$.
If $c = 1$ then the factors for $n$ are $gcd(n, b-1)$ and $gcd(n, b+1)$
If $c = -1$, then go back and select another random value of $a$
Otherwise, set $b = c$, and go through another iteration of the loop.

If you are familiar with the Miller-Rabin primality test, this will look familiar; the logic is the same (except that we use $ed-1$ rather than $n-1$ as the startign place for the exponent)


Cipher Block Chaining Ciphertext Alteration I am new to cryptography. My professor's slides say that "Disadvantage: altered ciphertext only influences two blocks" for the CBC. However, since we xor the ciphertext from the previous block and the present plaintext, before encryption; it seems to me like if I alter a ciphertext block, every ciphertext block coming afterwards will change. I do not understand why would this chain reaction only influence two blocks.

One way is simply to look at the usual illustration of CBC decryption and follow the arrows.
Here is the figure from Wikipedia:

Imagine you alter the first block of ciphertext. Follow the arrows to see what will be altered in the plaintext: only two blocks.

We can also do this with math formulas:
CBC mode encryption can be described as follow,
where $ P_n $  and $ C_n $ are the $n$th plaintext and ciphertext blocks, respectively:

$$ C_n = Enc(P_n \oplus C_{n-1}) $$

(With the IV playing the role of $ C_0 $)

Thus

$$ P_n = Dec(C_n) \oplus C_{n-1} $$

As a result, if you alter $ C_n $ it is clear that
$ P_n $ and $ P_{n+1} $ will be affected but not $ P_{n+2} $ and the next blocks.

If you want to see this in practice, you may want to do the cryptopals challenges up to challenge 17.


Is there a feasible preimage attack for any hash function (no matter how deprecated) today? Has there ever been a hash function that was actually used in the field, no matter how long ago, for which there is now a feasible preimage attack?

All hashes that are nowadays considered 'broken' (such as MD5 and MD4 and older, and to some extent also SHA-1) are only susceptible to collision attacks, i.e. generating two arbitrary chunks of data with the same hash.

I'm wondering if a successful preimage attack has ever been found for any hash algorithm? And I mean either kind of preimage attack:

Regular, i.e. given a hash output H, being able to generate some data X so hash(X) = H
Secondary, i.e. given data X, being able to generate some other data Y so hash(X)=hash(Y)

And with 'feasible' I mean it can be done on a reasonably powerful cluster of fast computers (with fast GPUs) within reasonable time (e.g. 6 months).

Any hash function? Yes, certainly. In fact, most hash functions are not even designed to be resistant to preimage attacks. This includes CRCs and standard checksums like Fletcher. Creating preimages with them is trivial. The oldest popular hash algorithm is MD2 which has a preimage attack with a complexity of 273 and a memory requirement of 273 memory blocks. The complexity is low enough that modern technology could achieve the preimage, but memory requirements make it impractical.
There have certainly been older hashes that have not gained traction which were intended to be cryptographically secure but which ended up exhibiting preimage attacks. For example, there is a 233 operation second preimage attack on the very old 3-pass Snefru hash function.
If you want a more specific answer, you'll need to narrow down what kinds of hash functions you are talking about. I could give you a dozen old or experimental hashes that were either dropped or underwent tweaks which were vulnerable to practical preimage attacks. I could also list every non-cryptographic hash I know of, but I have a feeling you aren't asking for a list of standard checksums.


Is it possible to use the RSA algorithm, or a variant, for software licensing? I'm almost a newbie about RSA encryption, so my question could it be banal.
I'm beginning to create a licensing system for my software.
I need to distribute a crypted license file to many customers.
I was thinking to use RSA public key to encrypt license file (with OAEP padding or PKCS#1 v1.5).
The software that will be licensed to customers will have inside the private key in order to be able to decrypt the license content.
Now the question is if can be possible to know the public key giving the encrypted file, the private key and the final plain text.
This because an hacker could know these data because are all inside the distributed software.

In other words I need a crypto algorithm that use two different keys.
One pw for encrypt the data, and another to decrypt the data.
And where will not be possible to obtain the encrypt password giving the decrypt password and crypted text.

The answer to the question in the title is: Yes, it is possible to use RSA signature for software licensing (e.g. in the context either RSASSA-PKCS1-V1_5 or RSASSA-PSS in PKCS#1 as defined here, or any of the three schemes in ISO/IEC 9796-2 free but partial preview). One minor issue is that, for a decent security level, what protects the license file will be much too big to be keyed in.

There are a lot of terminology errors in the body of the question:

What's wanted is distribute a crypted encrypted signed license file to many customers
What's needed is use the RSA public private key to encrypt sign that license file; in signature schemes with message recovery (e.g. ISO/IEC 9796-2) this will have the (perhaps desirable) side effect of making at least some of the signed content not directly intelligible, though recoverable without any secret information;
The software that will be licensed to customers will have inside the private public key in order to be able to decrypt verify the license content (and recover what portion of the signed information was not directly intelligible, if applicable)
The question is if it can be possible to know obtain the public private key giving given the encrypted signed file, the private public key and the final plain text signed data.

The short answer to that other question is: No, there is not a reason to worry that the private key (or anything allowing to generate new signed license files) could be obtained, provided the legitimate private key is kept and used securely, and was adequately drawn.

You'll get one private key to sign (and perhaps, with message recovery, make not directly intelligible some or all of) the data forming the license file, and an associated public key to verify the integrity (and perhaps, with message recovery, recover all) of that data; and where it will not be possible to obtain the private key (or some equivalent mean) given the public key and the data in any of its form.

On the other hand, no amount of cryptography will really prevent that someone skilled modify the software to bypass the license check, or allow the use of a license duplicated from an authorized one even if the software attempts to lock a license to a particular computer. Without temper-resistant hardware, the best you could do is that some portion of the software is unusable without access, at least temporarily, to a valid license to use that portion of the software.


Is the simulation-based proof difficult and needed? What is the role for simulation-based proof under the semi-honest model without considering malicious adversaries?
I agree with that a view of a some party is important to prove that a protocol is secure under some assumption which is semi-honest or malicious setting.
I'm wondering if a proof of simulation-based for a protocol makes sense. I see some papers providing proofs using simulation-based technique under semi-honest adversary.
But I don't think it is needed since its semi-honest. Most of cryptographers take care of the information leakage.

In other words, I think a simulation-based proof under the semi-honest adversary is not reliable. Often it's trivial while a proof for malicious adversary is NOT trivial.
Moreover, when non-experts read that paper, the proof makes paper difficult to read.

So, is the simulation-based proof under semi-honest model really needed in the literature?

The essence of semi-honest security is that "the protocol transcript leaks no more than the function output." How do you propose to formally prove this without a simulator? After you become comfortable with simulators, it becomes obvious that they are the correct way to formalize this idea.

Yes, simulators also do a good job of formalizing properties unique to the malicious setting (particularly input extraction). But that is not an argument against simulators for semi-honest definitions. If anything it reinforces the fact that simulators are the correct paradigm to formalize MPC security in all scenarios!

Yes, security proofs are much harder in the malicious setting. This is to be expected since the adversary has much more power.

Overall, it's not really clear what you are suggesting. First you say that a simulator in semi-honest is "often .. trivial" but then you say "the proof makes paper difficult to read". Simulation-based security is there because it is the most elegant way to formalize the relevant security concepts; it's not there to make things difficult for no reason.


Using AES-GCM (or AEAD ciphers in general) as a pure MAC without encryption What's the opinion on using an AEAD cipher such as AES-GCM for example as a pure message authentication code (MAC) when only message authentication but not encryption is required.

does it bring any benefits?
does it have any obvious disadvantages?
does it have any security implications?

does it bring any benefits?

Yes, it could. It is likely that e.g. GCM is sped up more than e.g. HMAC. GMAC - the underlying MAC - is using faster operations than HMAC as well, and GMAC is unlikely to be present as MAC in most runtimes. Besides that, it would also require a 128 bit block cipher, so you'd basically have everything you need for an AEAD cipher again.

  does it have any obvious disadvantages?

It could wrong-foot casual readers of the protocol or code. Suddenly they are presented with a cipher rather than a MAC, and that might lead to incorrect conclusions.

It may also well be that there is an additional overhead to take care of verifying a nonce and ciphertext. Although that's a constant overhead that is not related to message size, it may still be significant for small messages.

  does it have any security implications?

Depends on the MAC used and the MAC that it is compared against (and configuration, usage scenario etc.).

EAX mode is an AEAD cipher that uses CMAC for all MAC calculations. It is very likely to be as secure as using CMAC directly.

GMAC security on the other hand is more dependent on the size of the authentication tag compared to e.g. HMAC. It has a substantially lower limits for message count, message size, total message size compared to an algorithm such as HMAC configured with a SHA-2 hash.

Furthermore, a MAC as GMAC or CMAC is limited to 128 bits while e.g. HMAC can output 256 bits or 512 bits. Not that you're likely to ever need that amount of security for a MAC, but it can weigh in none-the-less.

Key reuse for two ciphers can negate all security and even lead to leaking the MAC key, something that is less likely an issue for a cipher + HMAC.


Selecting bijective functions for permutations How would one go about selecting an appropriate bijective function for introducing permutations into a cipher or hash?

For example, $f(x) = x+1 \space mod \space n$ is a bijective function, but isn't particularly good as a permutation, in that the outputs do not vary sufficiently when an input bit is changed.

The same applies to $f(X_i) = X_{\sigma(i)}$, where $\sigma(i) \equiv i+1\space mod\space |X|$, i.e. a circular shift.

If I understand it correctly, modular exponentiation can be bijective if you select appropriate parameters, but it's rather slow.

It depends.  There is no single answer, and no single recipe that works for all block ciphers.  The permutation is chosen to work well with the rest of the block cipher design.  Therefore, this question can't be answered in general.  A  question like "Why did cipher X use Y as its permutation?" would be more meaningful and more answerable.

For instance, some ciphers use a permutation to diffuse the bits, or to resist some kinds of attacks (e.g., algebraic attacks).  As CodesInChaos says, often one chooses a permutation that is as fast as possible and just barely good enough to meet the other requirements.


How can a Vigenère cipher be broken if the message is short? I was watching a Stanford lecture on Vigenère cipher and in it the professor said that – to break the cipher – we assume the length of the key is known. We then break the cipher into groups of this known length and then pick up (successively) the first, second, etc. members of each group and then break each of these using Caesar cipher.

The problem is: how would one break the cipher if the message length is short? Because then, we can not use the method which utilizes the frequency of letters to break the code.

For example:
Given the ciphertext ZZZJUCLUDTUNWGCQS and key is of size 6, can you crack this?
(Assuming you don’t know that the plaintext is WHATANICEDAYTODAY and the key is crypto.)

If the message is shorter than the key, then the Vigenere cipher is essentially the one-time pad, which is unbreakable for a random key. If the key is not random, then you may get some information on the plaintext.


Reverse Shamir's Secret Sharing Algorithm? Shamir's Secret Sharing algorithm works by breaking a single secret to multiple parts. While it is trivial to implement the reverse in a $n$-out-of-$n$ scheme, how would one implement an $m$-out-of-$n$ scheme were $k$ predefined shares $(k < m)$ are included in the share pool?

It is obvious that the resulting secret will be random but deterministic-ally derived.

Let's first recall the normal construction for Shamir's Secret Sharing:

We work in a finite field $\mathbb{K}$. This will usually be $\mathbb{F}_{256}$ (the binary field with 256 elements), so that the sharing can be conveniently done on a per-byte basis. We want an $m$-out-of-$n$ scheme, so the finite field must have at least $n+1$ elements. For each value to share, a random polynomial $P \in \mathbb{K}[X]$ of degree at most $m-1$: we write $P = \sum_{i=1}^{m-1} p_i X^i$ where the $p_i$ are chosen randomly and uniformly in $\mathbb{K}$, except for $p_0$, which we set to the secret value to share.

Thus, $P(0) = p_0$ is the secret value. The "shares" are $P(v_1)$, $P(v_2)$... $P(v_n)$, where the $v_j$ values are $n$ distinct non-zero elements of $\mathbb{K}$, that are chosen arbitrarily through a fixed, public convention (exactly which convention is used does not matter).

To retrieve the secret out of $m$ shares, we really rebuild the polynomial $P$, using Lagrange's polynomials. Let $N_i \in \mathbb{K}[X]$ be the following polynomial:
$$ N_i = \left(\prod_{1\leq j\leq n, j\neq i} (X - v_j) \right) $$
It is easily seen that $N_i(v_j) = 0$ for any $j \neq i$, but $N_i(v_i) \neq 0$. We thus define the Lagrange polynomial $L_i = N_i / N_i(v_i)$; it has value $1$ on $v_i$, and $0$ on all other $v_j$.

Then, $P$ is reconstructed as a linear combination of the Lagrange polynomials. If we have shares $P(v_1)$, $P(v_2)$,... $P(v_m)$, then we can write:
$$ P = \sum_{i=1}^{m} P(v_i) L_i $$
Therefore, the secret is:
$$p_0 = P(0) = \sum_{i=1}^{m} P(v_i) L_i(0)$$

In a practical implementation, the coefficients $L_i(0)$ will be precomputed, and the reconstruction needs not bother with actually rebuilding the polynomial $P$; it just recomputes the secret $p_0$ as a linear combination of the shares $p_i$.

Now, let's examine the problem at hand: you have $k$ predefined "shares" and want to use them in a secret sharing. To do that, you simply apply the reconstruction above, and use fresh random values when needed. In other words, you first declare that the polynomial $P$ really exists, and that the $k$ predefined shares are $P(v_1)$, $P(v_2)$,... $P(v_k)$. You then generate randomly and uniformly $m-k-1$ extra shares, which you call $P(v_{k+1})$, $P(v_{k+2})$,... $P(v_{m-1})$. Finally, you define that your secret value is $P(0)$. At that point, you have the evaluation of $P$ on exactly $m$ values ($0$, and the non-zero elements $v_1$ to $v_{m-1}$). You then define new Lagrange polynomials for a set of values that include $0$:
\begin{eqnarray*}
N'_0 &=& \prod_{1\leq j\leq m-1} (X - v_j) \\
N'_i &=& X \prod_{1\leq j\leq m-1, j\neq i} (X - v_j) \\
L'_0 &=& N'_0 / N'_0(0) \\
L'_i &=& N'_i / N'_i(0) \\
\end{eqnarray*}
At that point, you can find $P$:
$$ P = P(0) L'_0 + \sum_{i=1}^{m-1} P(v_i) L'_i $$

What happened here is that you rebuilt a polynomial $P$ that matches your predefined shares and the target secret value; you also generated new random shares in order to have enough value to make a unique candidate for $P$. Now that you have the polynomial $P$, you can compute as many extra shares $P(v_i)$ (for $i\geq m$) as you need.

Some extra notes:

If $k < m$, you can still choose the secret value, as shown above. It does not need to be "something random". If you do not want to choose the shared secret, you can simply create $m-k$ extra shares (instead of $m-k-1$) and use the normal Lagrange interpolation to get $P$, at which point you can obtain $P(0)$ as the shared secret. The computations always work, for all input values (that's how the scheme is secure, indeed). This would also be the situation if you started from exactly $m$ predefined shares: if you want a threshold of $m$ and already have $m$ shares, then there is no room for choice of the secret.
In all of the above, I used $P(0)$ for the secret, but that's purely conventional. $0$ is not special here. The gist of Lagrange interpolation is that, for any set of values $P(v_i)$ on $m$ different field elements $v_i$, there is a unique matching polynomial $P$ of degree less than $m$ (i.e. a polynomial that can be represented as $m$ coefficients).


Summary of definitions of cryptographic variables and operands I have recently developed a fascination for cryptography since I looked at some of the complicated questions on this Stack Exchange website. I'm a good portion through Crypto 101, but it's getting more and more inconvenient to have to look up what each operand and variable does or means (respectively). Is there any good summary or Cheat-Sheet that defines rather basically common things like E: Encryption Function or ⊕: XOR? I understand this is a very novice question, but I have to break out of being a beginner somehow. Any help is appreciated!

I haven't seen a cheat sheet for anything cryptography-specific but most, if not all, you can find in a math symbols cheat sheet. For example Wikipedia math symbols list also lists the XOR function.


Eavesdropping experiment with private key I am extremely new to cryptography, still trying to learn basics. I got stuck in the following example of an eavesdropping experiment with a private key.

$$\begin{array} {|r|r r r|r|}
\hline
C & & & & A \\
\hline
k & \leftarrow & Gen(1^{n}) & & \ \\
b & \leftarrow & {0, 1} & \leftarrow [m_0,m_1] \leftarrow & input 1^{n} \\
c & \leftarrow & Enck (m_b) & \rightarrow [c] \rightarrow & output b_0 \\
\hline
\end{array}$$

$A$ succeeds, if $b = b_0$.

Could someone give a basic of what is going on here and point to some resources where I can get the hang of these things?

Here is a simple/laymans explanation of what the example is (most likely) about:

Suppose you are given a new ciphering scheme (set of encryption and decryption algorithms) and you need to find out if it is secure. In cryptography, the security can be analyzed by issuing a challenge to the eavesdropper or adversary $A$. If the adversary wins the challenge, the cipher is insecure and vice-versa. This exercise consists of the following steps:

The challenger $C$ (on the left in your figure) generates a random key $k$ of appropriate length: a randomly-generated $n$ bit key would mathematically be represented as $k \leftarrow Gen[1^n]$ or $k \leftarrow \{0,1\}^n$ (I find the latter representation clearer).
The adversary $A$ (on the right in your figure) inputs two messages $m_0$ and $m_1$ to the challenger. Assuming these are $n$ bit messages, one can represent them as $\{0,1\}^n$ too.
The challenger encrypts only one of these messages $c \leftarrow Enck(k,m)$ with $m$ = $m_0$ or $m_1$. (Think of the challenger tossing a coin; if he gets heads/tails, he encrypts $m_0/m_1$). In the figure, this operation is represented as $c \leftarrow Enck(k,m_b)$ which then depends on the value of a single bit $b$.
The ciphertext $c$ is handed to the adversary who analyzes it with all possible resources he/she possesses (remember though that they don't know the key) and at the end of the analysis, outputs a bit $b_0$.
If $b_0 = b$, the adversary has won the challenge.

Remember the last line is to be interpreted in a statistical sense, i.e., if the challenger-adversary game is played $2N$ times, $b_0 = b$ must be true for $>N$ times.


Why would an RSA library tell me that the public key must be at least 512 bits in size? I'm trying to interoperate with a web service by reverse-engineering it. Currently, when sending a POST request, it encrypts the form data one-by-one with a 'RSA' function. But it's rather weird as everywhere else i've tried to use these values have given me errors. It's using this library: https://code.google.com/p/pajhome/source/browse/trunk/crypt/md5/rsa/RSA.js?r=133
Like this:

var crypto = new RSAKeyPair(
    "9d7aa162117a8a9610ed2ddea713d7b",
    "",
    "c9869917572adbb60a2c30ddec2551f")

I know just a little bit of RSA, but if i'm right, this should be the public key with (e,m). But when trying to work it in Java I get the error saying that the RSA public key must be at least 512 bits in size. Where is my mistake happening here?

BigInteger e = new BigInteger("3855b21eba4eb9a8a88117878e1fda49", 16);
BigInteger m = new BigInteger("ac5d160611804794d3e0240f2042b919", 16);

RSAPublicKeySpec spec = new RSAPublicKeySpec(e, m);
KeyFactory keyFact = KeyFactory.getInstance("RSA");
PublicKey publicKey = keyFact.generatePublic(spec);

On my setup, (e,m) are being (13082845549543033994073971762152947067, 229110545576645850236522690668306544921) in decimal (?!?!)

Your javascript library linked to has no restrictions on key size. Many libraries out there that implement RSA will have a restriction on the key size. This is to make sure developers are following best practices as if the key size is too small, the security of the cipher is completely blown. It looks like the Java library you are using won't let you use key sizes of less than 512 bits (which is still too small, even 1024 bits for RSA is no longer recommended for long term security).

If you remove the check for 512 bits, that should take care of the error.

Final Thoughts
I think it should be noted again that 512 bit RSA keys are way too small. Since you will be interoperating with something that is not secure, you'll need to think about what that means when it comes to the security of your system. You won't be able to change what the web service is doing, but you still need to think about how it affects the security of your system.


What should be broken to break a cipher with perfect forward secrecy? What should be broken to break a cipher with perfect forward secrecy as a passive observer? RSA/EC analog, (EC)DHE or both?

If the key exchange (i.e. (EC)DHE) is broken then a passive observer might be able to find out the symmetric key used for encryption which thus would allow the attacker to decrypt the traffic.

If instead only the public key or signature algorithms in the certificate are broken (that's what you probably mean with RSA/EC) then an active attacker might be able to man in the middle the connection but this ability does not help in passive attacks.


Possible attacks on CMAC I'm studying possible attacks on CMAC and I've found the NISTSP800-38B document where a list of possible attacks are defined.
However I have some doubts on possible attacks using forged messages. For example:

Considering a key of 128bit and a message of 128bit, is it possible to recover the key (e.g. if the message is all zeros)?
Which is the suggested minimum message length compared to the key length? Do you suggest some requirements in order to avoid forgery attacks?
Do you have any link or document about other attacks on CMAC?

Considering a key of 128bit and a message of 128bit, is it possible to recover the key (e.g. if the message is all zeros)?

Yes, but only by brute-force. That is when given a $(m,\tau)$ message-tag pair for a deterministic MAC (such as CMAC), you can always brute-force the key $k$ to get $\tau=\operatorname{MAC}_k(m)$. However with keyspace $\mathcal K$, this will take $|\mathcal K|/2$ MAC calls on average, which is $2^{127}$ evaluations which are usually assumed to be infeasible.

  Which is the suggested minimum message length compared to the key length?

There is no minimum message length. In fact, quite the opposite is true, MAC security degrades with message length. However, short messages may be more susceptible to replay attacks, but it's the task of the higher-level protocol to deal with them.

  Do you suggest some requirements in order to avoid forgery attacks?

The security bound for CMAC as a MAC is

  $$\mathbf{Adv}^{\textsf{MAC}}_{\operatorname{CMAC}(\pi)}(\mathcal A;q,ln)\leq \frac1{2^n}+\mathbf{Adv}^{\textsf{PRP}}_\pi(\mathcal B;\sigma)+\frac{2.5(\sigma+1)^2+1.5q^2+2q^2l^2}{2^n}$$

for an adversary, $\mathcal A$ making $q$ signature queries each of length at most $ln$ bits - with $n$ being the block size of the underlying block cipher $\pi$ - resulting in a total of at most $\sigma$ different evaluations of the block cipher $\pi$.

$\mathbf{Adv}^{\textsf{MAC}}_{\operatorname{CMAC}(\pi)}(\mathcal A;q,ln)$ is the chance that an adversary $\mathcal A$ can forge a tag for a message where they did not query the signing oracle beforehand and using at most $q$ queries each of length at most $ln$ bits.

$\mathbf{Adv}^{\textsf{PRP}}_\pi(\mathcal B;\sigma)$ is the probability that the block cipher $\pi$ can be distinguished from a random permutation using $\sigma$ encryption queries.  This bound was proven (written slightly differently) in "Formal Security Proof of CMAC and Its Variants" by Baritel-Ruet, Dupressoir, Fouque, and Grégoire in 2018 (PDF).


Can/Which encryption algorithms be daisy chained to create a cryptographic computational puzzle? Goal

Create a computational puzzle that is fast to generate, takes an average computer minutes to solve, doesn't have any exploitable weaknesses, makes use of existing/tested encryption algorithms

Problem

Let's say we have a string: "Prefix: LLLLLLLLLLLLLLLLLLLLLL" where L can be any alphanumeric character, "Prefix: " is a pre-set prefix, and "LLLLLLLLLLLLLLLLLLLLLL" the solution to the puzzle.

Let's pick 3 encryption algorithms (as an example), AES256, Triplefish, Camellia

The puzzle-creator takes "Prefix: LLLLLLLLLLLLLLLLLLLLLL", encrypts it with AES256 using key_AES256, then Triplefish with key_Triplefish, then Camellia with key_Camellia, resulting in a daisy_chained_puzzle

To the puzzle-solver, the puzzle-creator sends daisy_chained_puzzle, key_AES256 with 1-character prefix missing, key_Triplefish with 1-character prefix missing, key_Camellia with 1-character prefix missing

The puzzle-solver exhaustively tries all combinations of those 3 missing characters, and returns the solution once it stumbles onto a decrypted solution with "Prefix: ", and deducts that the solution is the suffix "LLLLLLLLLLLLLLLLLLLLLL"

Worries

Would the provided "Prefix: " provide a weakness that can be exploited?

Would providing the suffix of each key result in a weakness?

Question

Can encryption algorithms be used daisy chained like this to create a simple computational puzzle / which encryption algorithms would be ideal for the task?

Can encryption algorithms be used daisy chained like this to create a simple computational puzzle…

It can be done, but remember encryption algos are built to be (among other things) fast/speedy while hash algos generally tend to be slower (which is the main reason why — as an example — Bitcoin uses SHA256d for its POW). This is one of a few reasons I would recommend to not use encryption algos for blockchain-alike Proof Of Work thingies.

Instead, I would recommend using hashes. An alternative would be hash based MACs (HMACs) as they allow to tweak things using a secret (what some call the password value) or maybe even things like Argon2 which allow further tweaking which (among other things) can influence speed (read: hardness to solve, while avoiding some of the main probs arising from potential ASIC and GPU implementations).

  …which encryption algorithms would be ideal for the task?

Depending on the length of your puzzle, it's going to be less a question of encryption algo, but more a question of algo type (stream cipher or block cipher) and (when using block ciphers) the mode of operation.

Last but not least, related to your

  …takes an average computer minutes to solve, …

you should be aware that computer systems differ greatly and recent CPUs even have AES functionality embedded which raises an even bigger problem when trying to balance out the several systems out there to make your puzzle fair.


Perfect Secrecy in Symmetric Key Systems For symmetric key systems does perfect secrecy imply that all ciphers in the cipher space are equiprobable?

I would think not, but I am finding it hard to come up with a counter example.

In general, no. Consider the following perfectly secret probabilistic encryption scheme. Encrypt exactly like a one-time pad. Then, with probability 1/4 add a 0-bit after the ciphertext, and with probability 3/4 add a 1-bit after the ciphertext. For decryption, first throw away the last bit, and then decrypt as in the one-time pad. The ciphertexts in the ciphertext space are now not equiprobable.

Having said this, Shannon's theorem says that when the message space, ciphertext space and key spaces are all the same size, then a scheme is perfectly secret if and only if every key is chosen with the same probability and every plaintext and ciphertext have a single key mapping one to the other. A simple corollary from this theorem says that in this case (where all spaces are the same size) then the ciphertext values are all equiprobable.


What happens if no final subtraction is done in Montgomery multiplication? I'm doing Montgomery arithmetic modulo $N = 2^{255}-19$ for the Curve25519, picking $R = 2^{256}$ for Montgomery.

After multiplying two numbers $0 \leq A,B < N$ in the Montgomery representation using MonMul, I would normally obtain the result $0 \leq C < N$ also in the Montgomery representation.

However, if I forget the conditional subtraction in MonMul I obtain some $0 \leq C^{\prime} < 2N$. In other words, I basically ended up in a different representation which is not unique anymore.

I could live with that and do all the additions/subtractions modulo $2^{256}-38$ instead afterwards. That means I basically postponed the conditional subtraction until the end of my whole computation.

But my question is what happens if I have to do MonMul again somewhere during my computation? It would mean that one (or both) of the input numbers for MonMul could be in fact between $N$ and $2N$.

Do I have to make the conditional subtraction before doing the MonMul again (to put my numbers back in the right representation)? Or can I still postpone it until the end? I realized that not doing the subtraction before any repeated multiplication didn't spoil the computation so far. Does it really hold universally for my $N$?

Theorem 2 in [Dussé et al. 1991] states that, if we skip the final subtraction, then, for $N < R / 4$ and $0 \leq A, B < 2 N$, we have $0 \leq C = \text{MonMul}(A B) < 2 N$, while keeping $C \equiv A B R^{-1} \pmod N$. I think the condition $N < R / 4$ inherently holds in your case e.g. you are using larger $R$ value acutually.


Paillier Complex Residuosity problem? Paillier Cryptosystem depends on both the factorization where $n = p.q$ and the complex residuosity problem which is defined in the original paper as:

The problem of deciding n-th residuosity, i.e. distinguishing n-th residues
from the non n-th residues will be denoted by CR[n]. Observe that like the problems of deciding quadratic or higher degree residuosity, CR[n] is a random-self- reducible problem that is, all of its instances are polynomially equivalent. Each case is thus an average case, and the problem is either uniformly intractable or uniformly polynomial. As for prime residuosity, deciding n-th residuosity is believed to be computationally hard. Accordingly, we will assume that :

Conjecture 2. There exists no polynomial-time distinguisher for n-th residues modulo n2, i.e. CR[n]is intractable.

So, based on what this note states given a number in $\mathbb{Z}_{n^2}^*$ I cannot determine whether this number is on the residues set or not.

My Questions are:

What is so difficult about this if $z=y^n\ mod\ n^2$
The more important thing what is so dangerous in knowing that a number in the residues set. How It can help me break the encryption?

What is so difficult about this if $z=y^n\ mod\ n^2$

We don't know of an efficient way of solving it.  That's essentially what we can say about just about any hard problem in cryptography.

We also don't know a reduction to a better studied problem (for example, the factorization problem); hence it gets called out as a separate hard problem.

  The more important thing what is so dangerous in knowing that a number in the residues set. How It can help me break the encryption?

That's easy; an Oracle that can solve the n-th residuosity problem (without knowing the factorization) allow us to determine whether a Pallier encrypted message is an encoding of 0 (because a ciphertext is an encoding of 0 if and only if it is an n-th residue).

Not only would that, in itself, be considered a break in security, we could (for example) test an encrypted message for equality with any other value (by encrypting that value, homomorphically subtracting the test ciphertext from the ciphertext of the encrypted value, and checking if that is an encoding of 0).


What kind of information in cryptography is called semantic information? I have been studying cognitive cryptography from this article. Its definition of cognitive cryptography is:

  Cognitive cryptography is a division of cryptography
  within which any information set can be secured using personal
  information contained in the biometric sets of information and
  semantic information unambiguously identifying individual features
  of protocol participants.

What does the following part of the definition mean?

  ...semantic information unambiguously identifying individual features...

I don't understand what semantic information means. Specifically, what kind of information in cryptography is called semantic information?

I would greatly appreciate your assistance.

I'm not an expert but...

Semantic analysis is a concept not from cryptography but more from machine learning. The goal is for an AI to learn semantic information from some base set of inputs. For example we might train an AI to detect whether a arbitrary image contains a dog.

For the purposes of encryption an AI might learn to recognize an individual from a camera, microphone, and/or other inputs. In this case the "semantic information" would be the individual's characteristics necessary for an AI to identify that person from such external data.


How to sign low-entropy messages? Suppose you would like to prove authenticity of messages where the message space is small. Suppose the meaning of the message depends highly on the context, e.g. on time but also on events that are hard to encode, like political or social events. An extreme example would be a message space of "yes" or "no" (1 Bit), which are obviously context-dependent. Consider, e.g., the answer to the question: Do you love me? It also depends on who asked the question.

If you just use digital signatures, someone could just replay a pair of a message and a digital signature in a different context, giving it a completely different meaning, but still using someone else's correct signature.

How could you prevent these replay attacks?

I first thought of randomisation/salting, but all the probabilistic encryption schemes that I know use public salt, so an attacker could just re-use the salt as well.

Disclaimer: I'm not planning to build my own crypto. I'm just wondering how this problem could be solved, since to me, it doesn't seem so far away from reality...

Either you make sure that you use separate key (pairs) for each different purposes, or you simply include all possible context in the signature, including the entities.

So sign a message consisting of "Allice: Bob, do you love me? Bob: yes".

Note that it is not required to send all the data together with the signature, as long as you can regenerate the input.

Note that low entropy is not really the issue in your question. It's the amount of context that you sign. Low entropy is mainly a problem for random number generation and the functions that rely on it, such as the key pairs themselves.


What is the best way to derive a encryption key from the serial number? I have a couple of Android devices which run my app. Every device has it's own unique serial number - a hex string 16 characters long.

The app needs files, which usually reside on external SD.
These files should be usable only by a device which they are intended for.
So I need to encrypt these files, with a unique key derived from the serial number.

Now the question: What is the best way to derive a encryption key from the serial number? I thought I could just reverse it and use it as input for some hash function. But this is quite obvious I think....

The standard way to make a key out of some information (like your serial number), is to use a Key derivation function (KDF). If you do not consider a brute force attack to the serial number a realistic threat, then HKDF would be the suggested route to go, otherwise you should use a password based KDF like SCrypt which is much slower (which is a good thing against brute forcing).

I feel obliged to add, that using nothing but a serial number as a secret will not give you a secure encryption. While 16 bytes are basically enuogh to thwart attackers these days, it has to be assumed that the serial numbers are not really random but do follow some pattern, thus making them nuch more easily guessable. So while this scheme will be ok if you just want to prevent accidental misuse or passive attackers, it will most certainly not be good enough against an active attacker.

Update after your comments to the question above:

SCrypt won't help you in that scenario, so should use HKDF to derive a key for symmetric encryption (probably AES). Since you obviously never have an online connection to your app, using a random salt also won't be possible.  The only additional secret you could use to strengthen the process would have to be hardcoded in your app, protected by some code obfuscation. All this will protect you from the casual file sharer who just copies the file to a different device, but not from anyone more active.


Use HMAC or encryption for deep links? On a few occasions I've converted URLs with authentication via a session cookie to deep link URL's with no cookie authentication. These are URL's with simple id's like /download/pdf/1.

I convert them to deep links either by appending a HMAC of the ID (/download/pdf/1/7e3aefd25fb9…) or encrypting the ID using AEAD and omitting the id from the url (/download/pdf/7e3aefd25fb9…).

In both cases I store a longterm key on the server which is used for all deep links.

I was wondering: which (if any) of these approaches is best practice?

I like the HMAC approach because it clearly states the intent.
I like the AEAD approach because the programmer cannot read the ID from the url and then accidentally forget the authentication.

(I realize there is a third option which is to use an entirely random number for the deeplink. This is the simplest cryptographically speaking, and the best practice I suspect. But it has downsides because you must store these numbers and references to which resources they belong. Generating the URLs can't be done "on the spot" any more, you must push to the centralized storage.)

Usage scenarios:

The URL must work inside an iframe where cookies cannot be used in some browsers
The URL is automatically opened by another application such as Androids PDF reader which has no access to your browser cookies
We send an email with the resource URL and the recipient has no account in the system
We wants the users to be able to share the resource without sharing their credentials

Description of the attacker:

he uses HTTP
he might have access to the website as a cookie-authenticated user but NOT to all resources
he might have some valid deep links in his possession
he can easily guess a valid ID
he should not be able to create a valid URL from an ID unless it was provided to him
he should not be able access the resource

In my opinion your choice should come down to whether you want to hide the ID or not. If not, the use of encryption is just extra complexity and not useful. Most AEAD schemes allow decryption without authentication if the programmer really tries, so even that benefit is not very convincing to me.

A MAC, on the other hand, fits the problem perfectly well.

(Of course HTTP and plaintext email mean that your system has holes. Especially the former, since any eavesdropper to the connection will get to know both the URL and the content if you do not use TLS.)


Difference between actual attacks and theoretical attacks on SHA cryptographic series Could anyone tell me what the difference is between a theoretical attack (Like the one done on SHA-1) and an actual, practical attack (Like the one done on SHA-0)? Is a theoretical attack a proposed method of attacking, that no one has ever done due to lack of resources (like computing power)?

A theoretical attack is an attack strategy that was born out of “theory”, “calculation”, and — in the least cases — “simulation”. Yet, the strategy is yet to be proven in practice.

An actual attack which is practically proven and can be replicated is actual proof that a theoretical attack works. Therefore, the first is an indication of a weakness, while an actual attack is proof that that weakness actually exists.

It's actually not so much different from every regular science project. A theory is just a theory until someone can prove the theory is correct... transforming the theory into a fact.

In your SHA examples, SHA-0 is practically proven to have a weakness and - depending on available resources available for the attack - that weakness translates into "it's broken".

SHA-1 on the other hand has been proven - in theory - it's broken too, but up until now, I’m not aware of anyone having put the theory in practice. Since attackers don’t usually share the news about their efforts, chances are practical attack efforts exists but news about it hasn’t been shared with the general public.

Personally, I regard "theoretical attack vectors and/or strategies" as a warning, while I regard "practically broken" as a red alert. After all, a theory could have some flaw rendering it void, but if someone has practically broken something, statistical chances that others will do the same rise every second.


Galois LSFR Subsequence Periodicity I had the following questions -

Concerning generating sequences of bits $\textbf{x} = ( x_{0},x_{1}, ... , x_{n-1})$ where the $x_{i} \in \{0,1\}$  are considered coefficients of a polynomial in $\gamma$ (i.e. a polynomial of form $x_{0} + x_{1}\gamma^{1} + ... + x_{n-a}\gamma^{n-1}$) where $\gamma$ is the root of a polynomial $ \Lambda(\gamma) = c_{0} + c_{1}\gamma + ... + c_{n}\gamma^{n} = 0$, $c_{i} \in \{0,1\}$ (i.e. $\textbf{x}$ is an element in a Galois extension), I understand that all the elements of this extension (i.e all possible n bit binary strings) can be generated through the relation $\textbf{x}_{j} = \gamma \textbf{x}_{j-1} \textbf{mod} \space \Lambda(\gamma)$ for correct choice of $\Lambda(\gamma)$, the "period" of this generator is $2^{n} - 1$ after which the recurrence relation "wraps around" the ring and generates the first element over. This is described on page 11 here. If we consider $k$ bit subsequences of this $n$ bit string, is it possible to derive the period for a such a subsequence?
Is there a reference that concretely describes how to go from a construction above based on arithmetic in the field extension to the familiar Galois LSFR as described here?

Although I cannot speak to the first part of your question, I can answer the second part.  Also, I have never seen a formal explanation of how to map polynomials to a LFSR.  In retrospect, I honestly do not know if the polynomials that I have been given were picked because it was known that they would map to circuits, but here is how I do it.

As our example, we will start with the irreducible polynomial used in AES:

$$P(x)=x^8+x^4+x^3+x+1$$

I drop the $+1$, which is the $x^0$ term.  This gives me 8 total flip flops: $x^8,x^7,x^6,x^5,x^4,x^3,x^2,x^1$.  Due to the form of $P(x)$, I expect XOR feedback taps after $x^8,x^4,x^3,x^1$, which tap $x^8$ becomes just a feedback line as it goes to nothing.  The resulting circuit is:

In the circuit above, the data moves to the left from the right.  Taking the initial condition for AES as 0x01, we get the logic of:

01: 0x01
02: 0x02
03: 0x04
04: 0x08
05: 0x10
06: 0x20
07: 0x40
08: 0x80
09: 0x1b
10: 0x36
11: 0x6c
12: 0xd8
13: 0xab
14: 0x4d

This method has worked every time that I have implemented a LFSR as an irreducible polynomial. The first time I looked at the problem was with a simple polynomial and the answer was just "obvious".  I carried that system forward to ever other time and so far, so good.

Additions, comments and a proper method would be welcome.


Merkle signature scheme I was browsing the Wikipedia article on Merkle signature schemes and noted that it says:

The number of possible messages must be a power of two[…]

Why is that? If the nodes of tree are formed by hashing two public keys together by concatenation, why can't three or four be concatenated to form nodes? Also, since the structure does not take the form of certificates that contain a set of public keys signed by another public (root or otherwise), how can new keys be added?

You could, indeed, form a Merkle tree where each internal node is formed from the hash of 3 (or more) lower level nodes.  However, because it hurts signature size (which is the main expense of Merkle trees), we never do it.

In a Merkle signature, we reveal the preimage to the leaf node (which may involve a Winternitz signature), and also the authentication path; that is, the internal values of the nodes that are hashed along the path between the leaf and the root.

For example, in this three level Merkle tree:

We reveal $H(Y[2])$, from which the verifier can compute the value $A[0]$.  And to prove that it is the correct value, we reveal the values $auth[0]$ (so that the verifier can compute $A[1]$), the value $auth[1]$ (so that the verifier can compute $A[2]$), and the value $auth[2]$ (so that the verifier can compute $A[3]$, which is the root value).  The verifier would then compute the computed root value from the expected value in the Merkle public key; if it compares, then either this was signed by the correct private key, or someone managed to find a preimage for either $A[0], A[1], A[2], A[3]$.

So, this Merkle tree can sign up to 8 signatures using a signature size of 3 hashes (plus whatever hashes the lower level Winternitz uses).  In general, a Merkle tree of height $h$ can sign $2^h$ messages by revealing $h$ internal nodes.

Now, let us consider a Merkle tree where each internal node is 3 lower level nodes hashed together.  In this case, every part of the authentication path must consider of 2 revealed nodes (as the verifier needs to be able to recompute that hash value of the internal node).  So, we get a Merkle tree of height $h$ that can size $3^h$ messages, however each such message reveals $2h$ internal nodes.

It turns out that, for any desired total number of messages, the Merkle tree of degree 3 has a total authentication path that is at least as most (and usually more) than a Merkle tree of degree 2.

In addition, you asked:

  how can new keys be added?

In a single level Merkle tree, we can't.  Because the public key at the root is a complex function of all the leaf nodes, we need to compute all the leaf nodes (and the value of all the internal nodes) at key generation time.

However, we can get around this by using a two (or more) level Merkle tree.  That is, we generate two Merkle trees, a top level one, and a bottom level one.  And, we sign the root of the bottom level tree with the top level.  We then use the bottom level one to sign actual messages (and the signature of this joint system would be the Merkle signature of the bottom level tree, along with the signature of the bottom level tree with the top level tree).  We keep on signing the bottom level tree as new messages until that runs out.

Then, once that runs out, we generate a fresh bottom level Merkle tree, and sign that with the top level Merkle tree (which has signed only one value so far, and so can sign a second message).  We can keep on signing; if both the top level and the bottom level trees are of height $h$, then we can sign a total of $2^{2h}$ messages, and only have to generate a total of $2^{h+1}$ leaf nodes (and internal nodes) when we generate the initial public key.

This does increase the signature size (because of the internal Winternitz signatures); however it does allow us to create a signature scheme that can sign a large number of messages, but doesn't require a huge amount of time to generate the public key.