RSA finding p and q integer with condition I'm given $N=p\,q$ and told that $44\,p\approx 17\,q$ (with the value given for $N$ some 49-digit integer 8124642558124642555899928124642555899924479992447).

In RSA $p$ and $q$ must be prime.

So how can I solve this equation?

I'm using Maple, I began with s := evalf(solve(eqns, [p, q])) with eqns := {N = p*q, 44*p = 17*q}.

The result is not a prime number. How can I put another condition to force $p$ and $q$ to be prime? Or am I missing something?

Note of the editor: superlative HUGE removed for $N$, since it is way too small for RSA being secure.

The question's attempt at resolution is headed in the wrong direction for two related reasons

It informs the math tool that 44*p = 17*q when the problem statement has $44\,p\approx 17\,q$. If we had $44\,p=17\,q$, then $p$ and $q$ could not be primes, as stated in the problem.
It is not informing the math tool that $p$ and $q$ are integers. I can't help about how to do that for Mapple, and it is off-topic anyway.

$N$ is way too small to be useful as an RSA modulus, and could be easily factored without the hint that $44\,p\approx 17\,q$. Anything below 100 decimal digits has long been factorable by a single PC in minutes (see this); the lowest considered reasonable by Y2K was 1024 bits ≈ 309 digits; current is double that, moving to triple or away from RSA in the long run.

This is an application of Fermat's factoring method. This method is very efficient to factor integers of the form $C=A\,B$ with $A\approx B$. The hint $44\,p\approx17\,q$ tells that $C=44\cdot17\,N$ must be of this form, with $\{A,B\}=\{44\,p,17\,q\}$. Once we have factored $44\cdot17\,N$ using Fermat's factoring method, we can easily get at $p$ and $q$.

Don't fall into the trap of thinking that we must specifically guard against Fermat's factoring method and extensions when choosing an RSA key. The likelihood that the product of random primes $p$ and $q$ of practical size can be factored in this way is infinitesimal.

Update: there must be some typo in the value given for $N$, since (as commented by kelalaka) the integer given has 4 prime factors.


Default algorithm for scalar multiplication of elliptic curve points by the MIRACL Library What is the default algorithm used by the MIRACL-Library [1] for elliptic curve cryptography systems to perform scalar-point multiplication with curves of Weierstrass form satisfying the equation : $y^2 \equiv x^3 + a\cdot x + b \pmod p$ defined over a prime Field $\mathbb{F}_p$ ?

I can't find any satisfying information about the used method, the point representation and the costs for the formulars.

[1] https://github.com/CertiVox/MIRACL

It depends your compilation options but the function ecurve_mult in MIRACL/source/mrcurve.c seems to use the w-ary non-adjacent form (wNAF) method.


Slide attack: creating an actual attack on the Simon Cipher I have been reading the Simon Cipher paper.  It has the line: "The SIMON key schedules employ a sequence of 1-bit round constants specifically for the purpose of eliminating slide properties and circular shift symmetries", and I am curious.

I have read on the theoretical attack, but I am trying to find an approach to learn about the actual attack.  I hope to break the Simon key schedule to make it susceptible to a slide attack and the SIMON32/64 bit-width is small so it might be possible.   If I remove the constant z0 that is added to protect from a slide attack, I should be able to succeed in the attack.

Is there a good primer for slide attacks?

You should read David Wagner's original paper.  You can see all of his work here.

He authored the 'Slide Attack', 'Advanced Slide Attacks' and a few more related to the attack.

Wikipedia has a good introduction here

Feistel ciphers like Simon are very vulnerable to Slide Attacks and similar.  Removing the round constants from the key schedule will likley lead to an easy break in the cipher.  Partial attacks on the real cipher seem possible if multiple round keys can be forced to collide in a related key attack.


"official" guidelines about the minimum length of a truncated hash I am looking for some reference documentation suggesting a minimum reasonable length for a truncated hash (specifically, a truncated SHA-256 hash) to ensure preimage resistance.

Obviously, truncating a SHA-256 hash to, let's say, a 32-bit value is unsafe since a preimage can be quickly found by bruteforcing.

But what about a 64bit value? What about a 128-bit value?

I found NIST Special Publication 800-107 R1: Recommendation for Applications Using Approved Hash Algorithms but I did not find there any specific suggested minimum value.

minimum reasonable length for a truncated hash (specifically, a truncated SHA256 hash) to ensure preimage resistance.

To answer this one might consider the attacks.

Brute-force preimage algorithm: Currently, the collective power of the BitCoin miners reached $\approx 2^{92}$ SHA-256 double hashes per year in 06 Agust 2019. If you assume that the miners double this in every year, they need 18 years to reach $2^{128}$. Though doubling every year is highly unreasonable and we don't expect that. Here, larger than 128 will be enough.

Multi-target preimage algorithm: There is also multi-target attack by using classical computing. Using Oechslin's rainbow tables on a parallel machine:

For $\mathcal{O}(2^n/t^3)$ sequential evaluation of the hash function it will require $\mathcal{O}(2^n/t)$ time if parallelized $t^2$ ways to find a preimage for the first of $t$ targets.
This really depends on the number of the target, however, with 128-bit output, for a billion targets the cost would be below $2^{100}$ and the time would be below $2^{70}$ if you truncated to 128-bit. Adjust the numbers according to your requirements.

Generic quantum preimage algorithm If ever build a quantum algorithm for Grover's algorithm it will find a pre-image in $\mathcal{O}(2^{n/2})$-time. Therefore, if you consider this target you need to double the output size like stay with around 256.

The above cost is not included the cost of the hash implementation and set times.
The hash functions, classically, recommended by the collision resistance, which hash $\mathcal{O}(\sqrt{2^n})$ by the generic birthday attack where $n$ is the output size of the hash function in bits.
Recommending a truncation for a hash function with only pre-image resistance like 100-bit is not a good idea. Since there will be some people who will use this truncated version where collision resistance is also required. The 100-bit output will have 50-bit collision resistance with 50% probability and the 50% probability for an adversary it too high, which is not negligible in some sense. One might consider, the lower probabilities.
In short, SHA256-224  is the least recommended size if you consider all available NIST hash families after the SHA-1 which has 160-bit output. Of course, for SHA256-224, the collision attack is considered, too.


Help with a zero knowledge proof Can you please help with the following?

Let $C_1= g^r h_1^x h_2^y$, $C_2 = a^z$ and $C_3=(g^{r'}h_1^x h_2^y)^z$.

Basically, $C_1$ is a commitment on the values $x, y$ and $C_3$ is another, blinded commitment on the same values. $C_2$ is a commitment to the blinding factor $z$ of $C_3$.

We would like to prove in ZK that the values $x, y$ in the two commitments $C_1$ and $C_3$ are the same. Public knowledge are the values $a, C_1, C_2, C_3$ and the generators $g, h_1, h_2$. The secret values are shown in parentheses below:

\begin{align}
\pi = PK\{(r,  r', x, y, z):\; & C_1= g^r h_1^x h_2^y \; \; \wedge \nonumber \\ & C_2 = a^z \; \;\wedge \nonumber \\
& C_3=(g^{r'}h_1^x h_2^y)^z  \;    \} \nonumber
\end{align}

I have a proof but I find it somewhat ugly. It would be greatly appreciated if you can provide a more elegant one...

Thanks!

It could be straight-forward with verification equation quadratic in challenge, compared to well-known equation of Schnorr protocol that is linear in challenge.

In particular, for well-known responses like
$X = xc + \alpha$, $Y = yc + \beta$, $R, R', Z$
and equations for $C_1, C_2$ do it:
$(g^{R'} h_1^X h_2^Y)^Z = C_3^{c^2} D_1^c D_0$

Produce explicit formulae for $D_1$ and $D_0$ to complete this homework.

$(g^{r' c + \delta} h_1^{x c + \alpha} h_2^{y c + \beta})^{z c + \gamma} = C_3^{c^2} D_1^c D_0$

This approach with higher-degree polynomials in challenge rely on an upper bound for number of roots, two in this particular case.


Soft question: Examples where lack of mathematical rigour cause security breaches? Cryptographic tools can often become adopted even when their security proofs lack mathematical rigour - or altogether missing.

Are there famous cases of security breaches in the industry, where the underlying cryptography was  (up until then) considered secure?

The SSH protocol has a complicated record format with an encrypted message length, variable padding, encrypt-and-MAC, etc.  This complicated system, which was designed without any formal analysis relating the security of the system to the security of the building blocks, turned out to be vulnerable to an attack (paywall-free) exploiting the MAC verification as an oracle for information about the plaintext, leading to plaintext recovery attacks on SSH in popular implementations like OpenSSH.
The SSL/TLS protocols have a long and sordid history of informal design, leading to a multitude of attacks:

The Bleichenbacher RSAES-PKCS1-v1_5 padding oracle attack, which breaks an RSA-based encryption scheme designed without formal analysis, broke SSLv3 with RSA key agreement in 1998, and then broke it again in 2014 with the POODLE attack because of security-destroying protocol compatibility fallbacks, and then broke it again in 2018 with the ROBOT attack.
The BEAST attack, which had been noted by Phil Rogaway in 2002 and documented in theory for SSL/TLS in 2004, exploited the failure of SSL/TLS to follow the security contract of CBC which requires the IV to be unpredictable in advance for each message—the protocol had deployed CBC without formal analysis of how the IV is chosen.
The Lucky 13 attack (web site) recovers plaintext by using timing of padding verification as a CBC padding oracle, which arose from a CBC padding mechanism designed without even a simple-minded formal analysis of its timing characteristics.
The TLS renegotiation attack exploited a complicated state machine in the TLS protocol involving key renegotiation and authentication, which was never formally analyzed for its security properties, to forge messages sent to a TLS peer without its notice.

The OpenPGP protocol was designed by the ad hoc '90s-style composition of generic and poorly-understood public-key encryption and signature building blocks with no formal treatment for how they fit together.

The original promise of ‘Pretty Good Privacy’ was to keep email private.  But the method for combining fancy math primitives like RSA and standard symmetric cryptography like AES to encrypt long messages in OpenPGP was designed without formal analysis relating them to the security of the building blocks.

And it turned out this method was exploitable in practice in real email clients in an attack dubbed EFAIL that can leak message content (my answer on it).  It took a decade and a half after the problem was first reported in theory in 2002 for the OpenPGP world to catch up when an attack was published in practice in 2018.
A secondary promise of PGP was to prevent forgery in private email.
But there is no formal concept of a message from Alice to Bob—only of an encrypted message to Bob, and a signed message from Alice, nested however you please*…and usually nested in a way that Charlie can take a message Alice sent to him and make it look to Bob like Alice had sent it to Bob instead.  Alice can, of course, take the extra step to name the recipient in the message, and Bob can take the extra step to check for his name.  The software could also do this.  The OpenPGP designers could have tried to formalize the human-relevant interactions and analyzed their security properties—and could have designed the cryptography to support human use.

But, when confronted with the problem, instead the OpenPGP designers abdicated that responsibility by asserting that cryptography cannot solve the problem of appropriate use of technology.  To this day the OpenPGP protocol doesn't have a formal concept of a message from Alice to Bob—which could be implemented by standard well-understood public-key authenticated encryption—even though it is nominally intended for private email.
The public-key encryption and signature schemes chosen in OpenPGP were themselves designed without any formal analysis relating them to well-studied hard problems like the RSA problem or the discrete log problem, and it turned out that both the particular Elgamal signature scheme and RSA encryption scheme used by OpenPGP were problematic.

It is unclear to me whether these led to practical exploits on OpenPGP—except perhaps for the implementation error in GnuPG of using the same per-message secret for Elgamal signature and encryption, which illustrates the danger of proving a protocol secure without proving the code implements the protocol correctly.

These attacks are all on protocols that were designed by ad hoc engineering without formal analysis guaranteeing the security of the protocol relative to the security of its building blocks.  But the primitive building blocks—like $x^3 \bmod{pq}$, cubing modulo a product of secret primes; like $g^x \bmod p$, exponentiation of a standard base modulo a safe prime; like the AES-256 permutation family; like the Keccak permutation—don't have formal analysis guaranteeing their security relative to anything.  What gives?

The formal analysis or provable security for protocols, which consists of theorems relating security of a protocol to security of its building blocks, is only one part of a global sociological system for getting confidence in security of cryptography:

The reason we suspect the RSA problem is hard is that some of the smartest cryptanalysts on the planet have had strong motivation to study it for decades, and they have left a track record of decades of failure to find any way to break (say) RSA-2048 at cost less than $2^{100}$ per key.  The same goes for discrete logs in certain groups, for AES-256, etc.
The formal analysis of a protocol using RSA and AES enables the cryptanalysts to focus their effort so they don't have to waste time studying SSH, studying OpenPGP, studying SSLv3, studying TLS, studying WPA, etc., to find whether there's some way to break those protocols.  If the formal analysis is done well enough, the cryptanalysts can spend their effort on a small number of primitives, and the more effort they spend failing to break those primitives, the more confidence we have in the primitives and everything built on them.

Protocols like SSH, OpenPGP, SSL/TLS, etc., without formal analysis, are a colossal waste by society of the world's supply of cryptanalysts.  Formal analysis enables much more efficient use of the world's resources—and it would have paid off, because nearly all of the above attacks could have been caught just by studying the security properties of the protocols involved and the security contracts of the building blocks: CBC in TLS with predictable IVs, public-key encryption in PGP failing the IND-CCA standard, RSA-based encryption schemes in PGP and TLS without a reduction to RSA security, representing one's error responses in SSH and TLS as oracles for a chosen-ciphertext adversary.

Not all protocols are easy to formally analyze once designed—like the trainwreck that was TLS renegotiation—but protocols can be designed out of well-understood composable parts with clear security contracts to facilitate formal analysis, instead of ad hoc agglomerations of crypto gadgets like the '90s, and today there are tools like the Noise protocol framework with the Noise explorer to compose protocols with built-in formal analysis.

* Sometimes infinitely nested!


Why create a subkey in the digital signature algorithm In the signing step, wikipedia, a subkey is created.

A key k is randomly chosen from 1..q-1.

What's the use of that k?

If the k is to make less exposure to the private x; however, x is inevitably used in the signing part when computing s.

What's the use of that k?

The following lines of the wiki tell you:

Compute $r := ( g^k \bmod p  )  \bmod    q$

Compute $s := ( k^{−1} ( H(m) + xr  ) ) \bmod    q$

That is, it is used to compute both $r$ and $s$.

However, that's not what your really asking.  You're asking "why did they design DSA that way?"

Well, it's actually a variation on a noninteractive Schnorr proof of knowledge of a discrete log (in particular, of the private key); the modifications are there to reduce the size of the signature.

And, since Schnorr requires a "commitment" (what you call a subkey), well, so does DSA


Perfect hash function Is a perfect hash function always bijective ?
  In Wiki  "In mathematical terms, it is a total injective function" but it does not mean, that it is bijective.

No, it is not always bijective.

A perfect hash guarantees that no two inputs (from the set of valid inputs) collides, so it is clearly a 1 to 1 mapping.  However, in the case where the output range contains more possible values than there were valid inputs, there will be outputs which do not map back to inputs.  hence it is not bijective.

If you restrain the problem dramatically, and define the range of the outputs to be "the set of outputs attained from valid inputs," then you could argue it is bijective because you have constrained the output sufficiently to make such a claim.  However, it would be up to you to explain why this very particular output range is a valid one for whatever topic is being discussed at that time.


Generating nicer diceware passwords without losing entropy Yes, another one of those "I have found a great password-generation strategy"  waiting to be shot down!

It seems that although diceware aims to be a secure and user-friendly password generation method, there is a consensus that its output is not typically user-friendly. Over the years I have read many posts asking how to generate "nicer" passwords from it.
For example 1 2 3 and in particular 4.

To get "nicer" passwords, whatever that means, the suggestions are typically:

create your own word list (a lot of effort and need a longer password for same entropy since manual word lists are typically shorter)
use a selection method but be aware you lose entropy (e.g. pick $1$ out of $16$ passwords at the cost of $4$ bits of entropy)

But it seems to me that there is an easy way to get a more memorable yet shorter password, especially if you're bilingual. What you need is a set of $N$ disjoint diceware word lists, each with $6^5$ words.

When drawing a word, lookup the dice combination in the $N$ lists and pick the word you like most.

This is exactly as secure as drawing from a single list. Indeed, assuming there is no overlap between the lists, this is equivalent to processing the $6^5$ sets of $N$ words to create your own "preferred" word list and use a standard diceware on that list.

1 - Am I correct that generating a password in this fashion does not decrease entropy?

In practice, it is hard to find non-overlapping lists (unless you speak several languages, and even then there might be duplicates). The impact of overlaps is trivial to quantify when $N = 2$ but

2 - What is the impact of overlaps between lists when $N > 2$?

Even better, pick your $2$ preferred out of $N$ and flip a coin to choose. You just increased the entropy ($+1/$word) and still get a nicer password than single-list diceware.

Pushing this idea further: there are around $500$K words in the English language, from which one can create $\dfrac{500\cdot 10^3}{6^5} \approx 64$ non-overlapping word lists. For each dice combination, pick your favorite $K$ out of $64$ and pick a final word at random.

That's $\log_2(K)$ extra bits of entropy per word, so with $K=4$ you have $14.9$
 $bits/word$ instead of the standard $12.9/word$.

Nicer and shorter password for the same entropy / more entropy for the same number of words.

You control the trade-off between entropy and nicer words by adjusting $K$. With $K=8$ you gain $3$ $bits/word$ whereas with $K=1$ you get your preferred words but standard diceware entropy.

3 - Why is nobody doing this? This is easy enough to automate. Unless something above is wrong?

To get "nicer" passwords, whatever that means, the suggestions are typically:

  …

  use a selection method but be aware you lose entropy (e.g. pick $1$ out of $16$ passwords at the cost of $4$ bits of entropy)

What you are doing is effectively ‘a selection method’ (more commonly known in the literature as rejection sampling) with a bound on the number of rejections.  For your method to work, you need (say) a word list 16 times the size of a word list for standard (no-rejection) diceware in order to attain the same entropy while giving the user 16 distinct choices for each word position.

  1 - Am I correct that generating a password in this fashion does not decrease entropy?

Provided each of your 16 word lists has the same number of distinct words, you are correct that this does not decrease entropy vs. doing standard (no-rejection) diceware on one word list.

  2 - What is the impact of overlaps between lists when $N > 2$?

As far as the probabilities are concerned, nothing, provided (a) each word list has the same number of distinct words, and (b) you always accept exactly one of the 16 options presented.  As far as the user is concerned, they may be presented with the same objectionable word twice for one position.

  3 - Why is nobody doing this? This is easy enough to automate. Unless something above is wrong?

How do you decide how to partition the word lists?

If you have a 16x word list, you could just do rejection sampling on that word list and as long as you reject on average fewer than 16 words per position in the pass phrase, you get the same security with less user interface complexity.  For example, you could draw 16 words independently from your 16x word list, and ask the user to pick exactly one of them.

Exercise: Find the probability distribution on what you get by selecting 1 of 16 choices drawn without replacement for each word position.  (Independent samples as in the previous paragraph, in contrast, are ‘with replacement’.)  This avoids partitioning the word list.


Is it possible to represent max{a,b} as a binary polynomial? For privacy-preserving comparison, is it possible to represent the function of $f(a,b)=\max\{a,b\}$ as a binary polynomial $p(a,b)$?

I found the following solution due to Damgard et al.

[1]. Ivan Damgard, Martin Geisler, and Mikkel Kroigaard. Efficient and Secure Comparison for On-Line Auctions. ACISP 2007, LNCS 4586, pp. 416-430, 2007.

Background. Given the binary represetations of $m=m_{\ell}..m_1$ and $x=x_{\ell}..x_1$, let
$$w_i=m_i\oplus x_i\quad\mbox{and}\quad c_i=x_i-m_i+1+\sum_{j=i+1}^{\ell} w_j,$$
then if $m>x$ there is exactly one position $i$ where $c_i=0$, otherwise, no such position exists.  (Please see Page 423 of [1].)

A maple code：

with(Bits)：

pcomp := proc (a, b)

local abin, bbin, la, lb, w, v, c, i, f;

abin := convert(a, 'base', 2); la := nops(abin);

bbin := convert(b, 'base', 2); lb := nops(bbin);

if la < lb then

abin := [seq(abin[i], i = 1 .. la), seq(0, i = 1 .. lb-la)]; la := lb;

elif lb < la then

bbin := [seq(bbin[i], i = 1 .. lb), seq(0, i = 1 .. la-lb)]; lb := la;

end if;

w := [seq(Xor(abin[i], bbin[i]), i = 1 .. la)];

c := [seq(bbin[i]-abin[i]+1+sum(w[j], j = i+1 .. la), i = 1 .. la)];

for i to la do

if c[i] = 0 then f := 1; return f; end if;

end do;

f := 0; return f;

end proc;


How does the 'Flatten' function reduce the coefficients of a vector/matrix? Seen here, at the bottom of page 5, $\operatorname{Flatten}(\vec{a})$ is defined as:

$\operatorname{Flatten}(\vec{a})=\operatorname{BitDecomp}(\operatorname{BitDecomp}^{-1}(\vec{a}))$

For an n-dimensional vector $\vec{a} = (a_{1,0},\ldots,a_{1,l}, \ldots, a_{k,0},\ldots,a_{k,l-1})$. Where $a_{i,j}$ is the $j$-th bit in $a_i$'s bit representation.

But if we're computing the function through its own inverse, would this not just result in the original vector a?

When all the entries of $a$ are binaries, then yes, $Flatten(a) = a$, because $BitDecomp^{-1}(a)$ will give a $k$-dimensional vector whose entries are decomposed back to $\ell$ consecutive entries of $a$ (by $BitDecomp$).

However, when $a$ has non-binaries entries, this is not the case.

For instance, for $\ell = 3$ and $k = 2$, we would have $N = 6$. Then, consider $a = (0, 3, 0, 0, 0, 1)$.

Then, $BitDecomp^{-1}(a) = (3\cdot 2, 1\cdot 4) = (6, 4)$, and $BitDecomp(6, 4) = (0, 1, 1, 0, 0, 1)$.

Notice that for the last block of $a$ (last $\ell$ entries), $Flatten$ worked as the identity, because this block was binary.


A hash function that returns a value interpreted as integer I am new in cryptography. I need to compute a hash of a string value represented as follows:
$name||i$ where $i$ is an integer.
I use the following pseudocode:
message = []byte(name||i)
hashize = 1536
// Using SHA256 full-domain-hash with 1536 bits
hashed = fdh.Sum(crypto.SHA256, hashize, message)
Print(hashed)

Here the hash is a vector of integer values. How can I have only one integer that represents the hash of the message?

My guess is that the intention is to make an RSA-1536 (or Rabin) signature of name (as a string) and integer $i$ per Full Domain Hash. Thus I answer, form a crypto standpoint, a rephrasing of the question as:

How do I make a full-domain hash of the concatenation of a name (given as a string) and an integer, towards signing these per RSA-FDH.

In a nutshell, my recommendation is to make that as in RSA-PSS, but with a fixed salt.
An implementation of that could be

Express name and $i$ as a bytestring per ASN.1 Distinguished Encoding Rules (DER). This will avoid ambiguities of string concatenation (so that name foo and integer 10 won't have the same hash as name foo1 and integer 0), and normalize the integer (so that integers 00 and 0 will result in the same hash). Formatting could be as a SEQUENCE (tag 16) with name as UTF8String (tag 12) then INTEGER (tag 2). See Burton S. Kaliski's A Layman's Guide to a Subset of ASN.1, BER, and DER (RSA labs, 1993), which is enough for an implementer, except for the UTF8String type.
Apply to the resulting bytestring the EMSA-PSS transformation of PKCS#1v2.2 with SHA-256 hash, MGF1 with SHA-256 hash, $\text{emBits}=1536$, and fixed salt (e.g. 256 bits at zero). Part of that step includes hasing the input bytestring with SHA-256.
Convert the outcome to integer (per big-endian convention); this yields an integer as asked in the question.
Apply textbook RSA signature $x\mapsto x^d\bmod N$ (or the Rabin alternative).
Convert the integer outcome to a bytestring of $\left\lceil\text{emBits}/8\right\rceil=192$ bytes (per big-endian convention), yielding the signature.

Note: when targeting RSA, the combination of 2…5 is precisely signature per RSASSA-PSS of PKCS#1v2.2, and implementations of that should be reusable directly, if they have an input for the salt or for the salt-generating method.


Is there a property comparable to IND-CPA for hash functions taking a random value? I would like to have a function $F(x, rnd)$, where $rnd$ is a fresh random value, such that it is hard, given $x_0$ and $x_1$, to distinguish $F(x_0, rnd)$ from $F(x_1, rnd)$,
EDIT: but the values should be different, i.e., I should be able to recompute the value from $x_0$ and $rnd$ and see that it is the correct value.

I can do this with an asymmetric encryption function that has the IND-CPA property, but in my case, I do not need decryption. Thus, I thought about using a hash function, and my first simple idea was to simple concatenating the randomness, $H(x || rnd)$, but I'm not sure that this is sufficient.

I have looked into keyed hash functions, but I don't really want to use a key, just a random value. I did not really find a "randomized hash function" that would have a property comparable to IND-CPA.

Do I want something else, like a pseudorandom function, for my case? Can I construct one from a hash function?

Thank You for your help.

Not only is your idea of using $H(x|| r)$ sufficient, it will even in general provide unconditional security, if $H$ satisfies some regularity property, which is (roughly) that the size of the preimage of $H$ with a given prefix $x$ is always approximately of the same size.

To reformulate your question, you are asking whether $H(x || r)$ leads to a hiding commitment scheme, i.e., a scheme com for which it is infeasible to distinguish com$(x_0)$ from com$(x_1)$ given $x_0$ and $x_1$.

If you use any standard hash function which maps long strings to shorter string, observe that there will be in general many preimages to any given output of the hash functions. This means that given a hash value $h$ and strings $x_0$ and $x_1$, there will almost always exist values $r_0,r_1$ such that $H(x_0|| r_0) = H(x_1||r_1) = h$ (and the number of such values should be essentially the same for $x_0$ and $x_1$). This means that it is impossible to find out whether $h$ was obtained by hashing $x_0$ or $x_1$, even if the adversary is computationally unbounded.

If you want more formal details, an improved variant of this scheme was studied in this paper (where they show that their scheme is also binding - i.e., you cannot change your mind about $x$ if you later reveal the input you've fed to the hash function - and obtain a perfectly hiding commitment scheme without even having to assume that $H$ is regular).


Are there encryption systems that are both homomorphic and commutative? If so, which ones are?

If not, is it known whether or not these are mutually exclusive?

Is there a page that exhaustively lists encryption systems and properties such as these? I could not find a resource to help me find these answers on my own.

$\newcommand{\Enc}{\operatorname{Enc}}$
Actually, Pohlig-Hellman exhibits a homomorphism and commutativity.

For the commutativity, see poncho's answer on your other question.

The homomorphism goes as follows
(it is really just plain multiplication, not unlike what is possible with textbook RSA):
$$\Enc(m_1)\cdot\Enc(m_2)=m_1^a\cdot m_2^a=(m_1m_2)^a=\Enc(m_1m_2)\pmod p$$


Why not just generate random strings for one-time password (OTP)? http://en.wikipedia.org/wiki/One-time_password#How_OTPs_are_generated_and_distributed

Why have so many methods to generate OTPs, why not just use just random strings?

Just using random strings is simple and often reasonable solution. However, if you have significant customer base, it can become too expensive, because all of those random strings need to be stored.

But in short, these more complex schemes are mainly for reducing storage requirements and amount of entropy needed. Note: I am partially building this reply on previous two replies.

Reducing required entropy and storage requirements

Just generating random strings means need to generate and store lot more random bits than many of more well thought OTP mechanisms. For instance, S/KEY needs to generate and store just one value, even there can be e.g. one hundred passwords, thus reducing storage costs to one (theoretically) up-to one hundredth of random strings. Because less random bits (entropy) are needed, the OTP mechanism is easier to test and validated.

(Note: to handle transitions and expirations smoothly, usually more than one value needs to be stored.).

I agree to some degree with md_1976, however, I disagree on amount of information stored on the server. Time-based OTP schemes typically still need some information on user account, like serial number of user's authentication device (hardware device). In case there is software implementation of time-based OTP, server likely needs to know the public key of user's device or possibly the server and device needs a shared secret. One possible issue with time-based OTP schemes is that they tend to require special client-side software or hardware. One the other hand traditional OTP schemes can work even just via e.g. letter and phone network.

In time-based scheme with client side hardware device, typical information to store per account could be serial number and or other identification codes of the device.

Sizes of stored values

For purposes of comparing cost. (The possible other values e.g. account id or timestamps not considered.)

Original S/KEY (RFC 1760) - this is based on MD4 hash function, which is considered broken. Not recommended to be used.
OTP (RFC 2289), based on MD4/MD5, or SHA1. 64 bits storage needed, per OTP key.
HOTP (RFC 4226): Shared Secret is 128-bits or more (recommended 160-bits).
TOTP (RFC 6238): Uses same sized shared secret as HOTP.


Can I use my own implementation of a widely used, supposedly secure cryptographic algorithm for securing data at rest? I know you shouldn't roll your own crypto and generally its not a good idea to implement (and then deploy) any extensively tested and recommended algorithms by yourself either.
I have already seen this question, and as far as I understand, the main problem with implementing things yourself is that you will probably remain vulnerable to a host of side-channel attacks.
But suppose I have already implemented AES (just for fun and as a learning experience). What if I now use that implementation for simply encrypting files locally (and then perhaps back them up on the cloud or on removable media)? Since nobody other than me would be using the implementation, most of the side channel attacks would not apply. For instance, since no attacker can request an encryption/decryption (the way it works with a server), no timing attack can be carried out. Would this be as secure as using an extensively tested implementation?
In other words would using my own implementation of AES provide security for data at rest equivalent to the security provided by extensively tested implementations or will using it still be a stupid idea?

The big problem with RYO is the unknown unknowns. With popular implementations, there are fewer unknowns, more opportunities to find and fix flaws (more eyes on the code), and more guidance if something bad happens.
Think of it like an Ikea dresser; fine in the design studio, fine in the factory, fine in the store, deadly in a toddler's room. Without widespread dice-rolling, you might not find out about a flaw until it's too late and something bad happens to you alone. Also consider that the Maginot Line held as intended, yet still completely failed it's original purpose.
With a "real" AES, there's almost certainly targets juicer than your online backups to fall first, buying you time to fix vulnerabilities. There's no compelling reason stated that mitigates these risks or makes an important trade off, eg: lower battery usage than existing solutions. All i see is risk, no reward, and that makes it a no-brainer.
That said, if your implementation is interoperable with common tools, that suggests that your attack profile for at-rest data is likely similar to those common tools. That is, as long as you don't have mistakes or weaknesses, but that again is something of an unknown at this point; is the reward worth the risk?


DSA: Authentication and assurance of authorized parties When dealing with Asymmetric cryptographic algorithms, usually the sender of the critical data asks the listener for a Public Key for encrypting the data and sending them. This is while the private key remains only known to the listener so that it can decrypt the data. The problem in this scenario is that, the eavesdropper can eavesdrop on the Public Key and send "Falsified" data to the listener. In an abstract level, I know that this problem can be solved by making use of DSA to authorize the parties.

In Microsoft .Net Frameworks, the DSACryptoServiceProvider, very much like the RSA, I see that DSA is also a asymmetric algorithm consisting of a public and private key. And I assumed that with different Keys, I will come up with different signatures for the same data. So I also assume that I have to send the public key to the sender of the data for the purpose of verification ( the padlock concept). But in this case it will not work for the reason I explained.

My question is that, how do I have to use the DSA to assure that the stream is coming from the authorized party.

If I'm understanding things correctly, you want to make sure that the public key you receive actually belongs to the person you want to communicate with.

Thus you want to avoid MITM attacks, which is non-easy.
Standard (TLS/S/MIME/...) solution would be to create a certificate signed by someone you trust to assure you that the particular public key belongs to the entity you expect.

Another solution would be to exchange some data over a second (trusted) channel containing a hash of the public key assuring you that the key belongs to this person. It is sufficient to do this once for the life-time of a key.

The last method of defense I'm aware of is identity-based systems or implicitly-signed systems. This is highly complex and I'd rather go with certificates in large scale and with second channel in smale-scale.


Inclusion and Exclusion proofs in RSA accumulators I am reading about RSA accumulators from this video and few other sources. I had a confusion whether the complete set is needed to construct a proof of inclusion/exclusion in an RSA accumulator or is it possible to create the proof of inclusion/exclusion just by knowing the accumulator root and the value for which membership/non-membership proof has to be provided. Can someone please clarify this?

No and Yes! For the inclusion proof you either need the trapdoor or the accumulated set. However, it is possible to generate exclusion proofs without knowing the trapdoor, i.e. the factorization of the modulus, $N=p\cdot q$, or the size of the group, i.e. $\phi(N)$.
Let $A$ denote the accumulator's current value, $x$ an item, $g$, a generator of the group and $\pi$ the inclusion/exclusion proofs. All arithmetics are done $\mod N$. Also note, that all items (accumulated elements) are primes.
$inclusionProof(A,x): \pi =A^{\frac{1}{x}}$.
Note, that this is only computable if you know the order of the group or the accumulated set as computing $x$th root $\mod N$ is assumed to be hard without knowing the factorization of $N$.
Verifying inclusion proofs is easy, one just need to check whether $\pi^x=A$. Once the item is accumulated, one can easily update her inclusion witnesses.
Let $A=g^u$ be, then,
$exclusionProof(A,x):$ Since $x$ is not accumulated this implies that $gcd(u,x)=1,$ therefore one can compute $a,b$, so-called Bezout-coefficients, such that $ax+bu=gcd(x,u)=1$. Hence $\pi=(g^a,b).$ Verifying the proof is done by checking $(g^a)^x\cdot A^b=g^{ax+ub}=g$.
Batching inclusion/exclusion proofs is also achievable. See this recent result.


PBKDF2 with SHA-256/512 for low entropy input? Is there any reason to use something stronger than SHA-1 with PBKDF2 if my input is fairly low entropy?  I.e. if the passwords being hashed are only about 30-bits of entropy.

I can't find it now, but someone stated if you want to preserve the entropy of high entropy intput, then use PBKDF2 with a higher SHA.  So I'm wondering if the inverse is true, that there is no real gain to using SHA-512 if your input is low entropy.

I've seen one case mention that using SHA-512 would increase the memory requirements for attackers.  In some cases, I know that increasing memory requirements will make GPU hashing less effective.  Not sure if that's true in this case.  https://cryptosense.com/blog/parameter-choice-for-pbkdf2/

There is not much of a substantive difference between using SHA-1 or SHA-256 with PBKDF2 to hash a password: they use nearly the same amount of memory (20 bytes vs. 32 bytes of state, plus 8 bytes of message length and 64 bytes of input buffer), and SHA-512 uses only double what SHA-256 uses (64 bytes state, 16 bytes length, 128 bytes buffer).

If you can, forget PBKDF2 and consider using Argon2id instead, so that if you have (say) 128 MB free for password hashing—and perhaps a few extra CPU cores—you can use it all to drive up an adversary's costs.


ZK due to rewinds, why we need poly number of rewinds? I've been looking into rewinding techniques for proving ZK and got a bit confused.

This answer is good, but I still have questions about challenge size and the number of rewinds.

Consider an interactive sigma protocol, for which Simulator can always produce an indistinguishable transcript if he guessed the challenge. Since the probability of guessing is 1 over challenge space, Simulator would not be very useful, unless he has special rewinding powers.

A) If Verifier is honest, he would use only his tape to chose the challenge, thus after rewinding, he will select the same challenge. Simulator needs to rewind just once for obtaining the challenge.

B) If verifier is malicious, then it's a bit tricky. First of all, sigma is honest verifier zero knowledge and doesn't deal well with malicious Verifiers. For one thing, malicious Verifier can always select a challenge based on Simulator's first message. No poly number of rewinds would help in such case.

Still, if we modify sigma protocol a bit and ask Verifier to commit to the challenge first, we avoid the whole dependency thing. Though commitment should be a perfectly binding one aka one-way function, otherwise Verifier still may change his response and no way Simulator guesses it in poly time.

Now after rewinding, Simulator would get the same challenge and thus can finally create a transcript. Thus, again just one rewind.

Where poly number of rewinds is coming from? Why challenge space is important? How the existence of Simulator with super powers in unrealistic settings helps to claim simulatability in real ones? I've got why it's handy for proving extractability, but ZK?

Well, I mixed up everything. The answers to this question helped me figure it out.

Short answer: A polynomial number of rewinds and reduced challenge space are needed when we deal with the malicious verifier and don't ask for commitments. Rewinds are handy, cause they allow us to prove honest verifier ZK for interactive protocols (ZK as well but either for protocols with commitments or small challenge space).

Long answer:  An interactive sigma protocol is an honest-verifier zero knowledge. This means there exists a simulator, that can falsify the transcript between Prover and Verifier without knowing a Prover's secret. The intuition behind simulation is the following: if verifier can't distinguish between a fake transcript that was generated by the simulator that knows nothing about Prover's secret at all and a real one produced by a Prover, no information about the Prover's secret is leaked. Ironically, in settings where Prover by default is not honest, zero-knowledge property aims to protect Prover's privacy.

Proving honest-verifier zero knowledge is a bit tricky. We know how to simulate the transcript but can't predict verifier's challenge. We can try to guess the challenge, but even for an honest verifier (who behaves and for sure selects it randomly), the probability of guessing is one over the challenge space. If challenge space is large, this probability is next to none.

So, challenge space is a problem. On the one hand, to make sure that a malicious prover's chance to win is exponentially small, challenge space should be reasonably large (soundness). On the other, if challenge space is large, our simulator has almost no chances to guess the challenge right.

The solution is to rewind Verifier - it's an equivalent of having a time machine. We guessed wrongly, went back in time and now we don't need to guess, we know an honest Verifier's challenge. The reason is simple: if Verifier is honest, he would use only his tape to chose the challenge, thus after rewinding, he will select the same challenge.

However, a classic interactive sigma protocol is an honest-verifier zero-knowledge and not just zero-knowledge for a reason. It's not secure against malicious verifier, because even with time-machine we can't guess a malicious verifier's challenge in the polynomial time.

The problem that even rewinds can't solve is a possible dependency on Prover's reply. No matter how many times the Simulator would rewind Verifier, he will not be able to guess the challenge right, cause (a) challenge space is big and (b) challenge depends on what Simulator sends.

There are several ways to solve this problem:

Forget about interactive proofs and switch to non-interactive.
Reduce challenge space (this is where a polynomial number of rewinds appear)
Make Verifier commit to the challenge first

Reduction of the challenge space is not very practical. DrLecter explained it in details here. To sum it up: after each rewind, Verifier computes a new challenge based on what Simulator sent, but since challenge space is small several Simulator's first messages correspond to one challenge, so he will guess it eventually. The book "Modern Cryptography: theory and practice" by Wenbo Mao did the math and conclude that for a simulator to run in poly time a challenge ideally should be from $[0, \log_2 p)$. The only drawback, it's not enough for soundness. To make sure that a malicious prover's chance to win is exponentially small, we have to run many protocols sequentially.

Using commitments as a guarantee is an option too. It adds interactions but requires just one rewind. There are two types of commitments we can use: perfectly hiding and computationally hiding. The former gives ZK, same soundness as before, but require 2 additional interactions: Prover sends $h$, Verifier replies with $g^r h^e$ (Pedersen commitment - perfectly hiding).  For the computationally hiding commitments, ZK and computational soundness can't be achieved. Both claims were proven by professor Yehuda Lindell. The first proof (Theorem 6.5.2)  can be found in "Efficient Secure Two-Party Protocols" by C. Hazay and Y. Lindell (The proof has an error that was later corrected in An Erratum). The second claim is stated here with a sketch of a proof.


New to cryptology, studying Message Authentication Codes I understand the basic operational theory behind MAC, but I'm getting tripped up on some of the finer details.  Also the differences between MAC, HMAC and MIC are getting lost on me, including the different utilizations between them, the benefits of using one over the other in a given situation, etc.  As such, I'm hoping I can get an overview on MACs, covering a few specific points.

Firstly, I get how a MAC verifies that the message is unaltered, but I don't get how that translates to verifying the message originator.  Just because the message is unaltered doesn't mean it came from a specific host.  To me that sounds like there is an assumption that the session key has not been compromised.  So this would protect against message tampering but not eavesdropping?

Secondly, is the MAC based on the plain-text or the cipher-text?  Also, how is the key selected?  Is it unique to the MAC or is it related to the session key?

As far as I understand MAC vs HMAC vs MIC, HMACs are keyed hash functions which use the message and a key to produce a digest used in the verification process, MACs do the same but can be based on universal hashes or even algorithms which are not hashes, and MICs can be based on any algorithm that can be used as a MAC, but do not utilize keys, and so can only be used to provide message integrity, and not authentication.  If I'm mistaken on any of that, I'd appreciate some clarification.

As with my previous post, I know this is probably an extremely basic question to be asking in this forum, so I'll apologise if this is irksome to anybody.  But I'm only just getting my feet wet in cryptology.  I'm not even sure that my understanding on this topic is incorrect, I'm just not 100% sure that it is correct.

First, terms: A MAC is a generic term for a class of cryptographic primitives. It's in the same category as "hash" or "PRNG." HMAC is a particular construction that, combined with a suitable cryptographic hash, gives a secure MAC function (it can also be used to generically refer to any HMAC algorithm, since HMAC is secure with pretty much any standard hash, even MD5). A similar term in symmetric encryption is "CBC mode;" it's a way to take a certain kind of primitive (hashes for HMAC, block ciphers for CBC) that does one thing and get it to do something else. MIC is a term used rarely, but basically means is a synonym for MAC; MIC is what some standards (like WPA) call their MAC, because the term "MAC" already has a meaning in those contexts (in WPA's case, this is MAC addresses). "Integrity" implies "authentication" in security-land; MICs need keys as well.

To your first question: MACs verify that the message did come from a specific source (someone with the MAC key). What they don't verify is that it hasn't been intercepted and passively eavesdropped. They're meant to protect integrity, not confidentiality; you use encryption to protect confidentiality. In general, you have to keep your MACs confidential; a MAC can leak information about what was MACed. Privacy-protecting MACs don't themselves leak info about what was MACed, but you still need to encrypt the plaintext.

To your second: It's complicated. Encrypt-then-MAC is generally considered the best (the MAC then can't leak info about the plaintext, and protects against tampering of the ciphertext; all an attacker can do is mess with the ciphertext, they can't touch the plaintext directly); however, Encrypt-and-MAC (MAC the plaintext and do not encrypt the MAC when you encrypt the message) and MAC-then-Encrypt (MAC the plaintext, then encrypt everything) can work.

You also have to think about how the MAC algorithm works with the encryption algorithm, and here be dragons. The best practices are to use a different key for your MAC and your encryption (which normally rules out negative interactions between them), or to use a known-secure construction like GCM to provide both. If you're combining a MAC and an encryption scheme, it's common to use a key-based key derivation function to create the MAC and the encryption keys from a single session key; HMAC is also a pretty good KBKDF (it has a lot of nice properties that aren't really needed for a MAC role).


Universal forgery based on mathematical problem It is known that DSA admits universal forgery under assumption that the Attacker can solve the equation $x\equiv R^x\pmod p.$ Are there any other protocols admitting universal forgery based on non-trivial mathematical problem?

Elliptic Curve Digital Signature Algorithm admits universal forgery if the Attacker can solve the equation
$$z=\frac{\psi_{k-1}(x,y)\psi_{k+1}(x,y)}{\psi_{k}(x,y)^2},$$ where $k$ is unknown, $\psi_{k}(x,y)$ are Division polynomials  and $(x,y)$ are the coordinates of a point $P$ on the elliptic curve $ E:y^{2}=x^{3}+Ax+B$. This UF is based on the formula for the coordinates of the nth multiple of $ P(x,y)$:
$$kP=\left(x-\frac{\psi_{k-1}(x,y)\psi_{k+1}(x,y)}{\psi_{k}(x,y)^2},\ldots\right).$$

The question Elliptic curve sequences needed for universal forgery about hardness of this UF was asked at MathOverflow separately.


By what modulo calculations with discrete logarithms are performed? For odd prime $p$, I have been given a group $\mathbb{Z}_p^*$ of all invertible elements from $\mathbb{Z}_p$. Basically, $\mathbb{Z}_p^* = \{1,2,\ldots , p-1 \}$. I also have $a$ and $b$, which are two generators of $\mathbb{Z}_p^*$. My question is, by what modulo calculations with the discrete logarithm are performed for $\mathbb{Z}_p^*$? Or in other words, does it hold:
$$ a^k \equiv b \pmod p$$
$$k \equiv \log_a b \pmod{p}$$
Or does it hold:
$$ a^k \equiv b \pmod{p-1}$$
$$k \equiv \log_a b \pmod{p-1}$$
And also, a followed up question:
If $\mathbb{Z}_p^*$, $a$ and $b$ are as described above, does it holds, that if $k=\log_a b$ then $k\in \mathbb{Z}_p^*$?

Neither of the question's alternative hold.
For any $n>1$, and any $a$ with $\gcd(a,n)=1$,
$$a^k \equiv b \pmod n\quad\iff\quad k \equiv \log_a b \pmod{\text{ord}_n(a)}$$
where $\text{ord}_n(a)$ is the order of $a$ in the multiplicative group $\mathbb Z_n^*$, that is the smallest $r\ge1$ with $a^r\equiv1\pmod n$.
The order of an element divides the order of the group, which is $\varphi(n)$ for group $\mathbb Z_n^*$, where $\varphi$ is Euler's totient function. Therefore
$$k\equiv\log_a b \pmod{\varphi(n)}\quad\implies\quad a^k \equiv b \pmod n$$
When $a$ is a generator of $\mathbb Z_n^*$, which is testable as $a^{\varphi(n)/q}\not\equiv1\bmod p$ for every prime $q$ dividing $\varphi(n)$, we simply have
$$a^k \equiv b \pmod n\quad\iff\quad k \equiv \log_a b \pmod{\varphi(n)}$$

Restating this for prime $p$, and any $a$ with $a\not\equiv0\pmod p$,
$$k\equiv\log_a b \pmod{(p-1)}\quad\implies\quad a^k \equiv b \pmod p$$
and, for the lowest $r\ge1$ dividing $p-1$ such that $a^r\equiv1\pmod p$,
$$a^k \equiv b \pmod p\quad\iff\quad k \equiv \log_a b \pmod{r}$$
When $a$ is a generator of $\mathbb Z_p^*$, which is testable as $a^{(p-1)/q}\not\equiv1\bmod p$ for every prime $q$ dividing $(p-1)$, we simply have
$$a^k \equiv b \pmod p\quad\iff\quad k \equiv \log_a b \pmod{(p-1)}$$


What is the keyspace of ROT-13? Today I was having a discussion with my cryptography lecturer about the keyspace of a ROT-13 cipher. He argues that the keyspace is 0 because it doesn't have a key.

Could anyone explain to me why the keyspace is 0 and not 1? I could understand if he said that it doesn't have a keyspace but I don't understand why it could have a keyspace of 0.

I was further confused when he said that it was possible for a cryptographic function to have a keyspace of 1. Could someone give me an example of a cryptographic function with a keyspace of 1 and explain how it is different to one with a keyspace of 0?

I feel fairly confused about something that seems like a pretty basic concept.

Thanks for any help.

I think it's better to define the  keyspace of an unkeyed function as having one element.

Some advantages:

Computing the key size as $log_2 1$ correctly tells you it's a 0 bit key
For encryption you pick one key from the set. You can pick an element of a single element set, but can't pick from an empty set
Functions with multiple inputs are often defined to take the Cartesian product of their inputs. For example for encryption this could be $M \times K \to C$ where $M$ is the space of messages, $K$ the key space, and $C$ the ciphertext space. One again, this only works correctly if you use a single element set as key space.


Find out a set of values without sharing my own I have the following problem which i am trying to find a reasonable protocol to solve it.

This is a simplified version of the problem.

Alice has a set of values $\{a_1,a_2,...,a_n\}$.

Bob has a set of values $\{b_1,b_2,...,b_n\}$.

Alice wants to learn which values Bob has that are equal to her values but without Bob learning any of the inputs she gives him, Alice is also not allowed to learn any other values bob has.

I appreciate an efficient solution but any solution at the moment is better than nothing.

You are looking for a private set intersection protocol.

For the semi-honest (passive adversary that follows the protocol) setting, go to Benny Pinkas's homepage and read the papers there, e.g.

Scalable Private Set Intersection Based on OT Extension

Efficient Circuit-based PSI via Cuckoo Hashing

For the malicious (active adversary that behaves arbitrarily) setting, go to Mike Rosulek's homepage and read the papers there, e.g.

Malicious-Secure Private Set Intersection via Dual Execution

Improved Private Set Intersection against Malicious Adversaries


Is TEA suitable for encrypting/authenticating many short messages? I know that TEA has its weaknesses, but is easy to implement. My question is whether it would be suitable for my use case: The main reason for using encryption is not so much secrecy, but authentication and protection against interference.

I have a number (max 20-30) of GPS trackers, which send their location by radio in intervals to a base station.
Each message consists of a tracker ID, a timestamp, the location, and a checksum, so max 16 bytes, but in a fixed format.
Each message will be similar to the previous one, as the time increment will be constant, and the location will not change very much between two subsequent messages.
The time frame is about three hours, with probably about 800 messages sent per device during that period. So roughly 20k messages in total.
the code of the system will probably be public (so security through obscurity will definitely not work)

What I want to avoid from happening is anyone sending fake messages that are mistaken for real positions; decoding the message content is not a problem, as anyone can observe the trackers moving around anyway if they wanted to. So if it takes more than three hours to crack the key and enable sending fake messages, that would not be an issue, as that means the window in which a single key is used would be over.
I guess what I really need to know is:

Is TEA (or XTEA, or XXTEA) at all suitable for this use case? And if so, vanilla or X/XX? Or is there another algorithm that would be better suited? For example, just a hash checksum?
Are there any other ways I could improve security (eg use a different key for each tracker, randomly vary the format of the message (location first vs timestamp first), compress the message (only store difference to previous location, eg, to remove some redundancy))

My main design goals are reasonable security (it's competitive sports, not secret missile plans), simplicity of use and implementation (I am a developer, not a cryptography expert), and low computational overhead (this will run on an ESP32 micro-controller).
I have some basic thoughts on this, but would appreciate some expert advice!
UPDATE: Since this was asked in one of the answers: the trackers will be initialised in close proximity on power-up, and the base station can transmit a 'secret' key via Bluetooth Low Energy to each tracker. I do realise that Bluetooth is not really secure, but given the proximity this is in my view a negligible risk.

The main reason for using encryption is not so much secrecy, but authentication and protection against interference.

In that case, what you want is an authenticated encryption scheme.  While TEA, as a block cipher, may be used to implement such a scheme by using it in some suitable AE mode (such as SIV), there are also a number of dedicated lightweight authenticated encryption schemes that you may wish to look into.
In particular, I'd suggest taking a look at Ascon, which was selected as the primary choice for the use case 1 (lightweight authenticated encryption) in the final round of the CAESAR competition last year.  While not quite as simple as TEA, the reference implementation isn't all that complicated.

Since your message length is fixed and very short, you could obtain a simple authenticated encryption scheme just by using a block cipher with a block size longer than your message length, padding your messages up to the block size e.g. with zero bytes, encrypting the padded message directly with the raw block cipher (i.e. in "ECB mode") and verifying the correctness of the padding after decryption.
However, for this you'd want a block cipher with a block size of (at least) 128 bits (= 16 bytes), which TEA doesn't have.  XXTEA could work, though.
With 4 bytes of padding, the odds of an attacker randomly guessing a valid ciphertext would be 1/232 per attempt, which seems likely to be low enough for your purposes.  This would be a deterministic encryption scheme, so it would leak whether or not two plaintexts are equal, but that shouldn't be an issue for you since your messages include presumably unique timestamps anyway.

As for the security of TEA or other crypto primitives for your purposes, the first thing I'd like to note is that it seems extremely unlikely that anyone would develop and implement a novel cryptanalytic attack just to interfere with your system.  Thus, you should be fine as long as the scheme you're using:

has withstood any serious cryptanalysis at all (i.e. it's not just some random homebrew cipher kludged together by someone with no crypto experience),
has no known practical attacks (i.e. with complexity well under 264 or so operations) with published attack code that someone could just download and run, and
the way you're using it isn't broken in some way that would allow someone to bypass the actual cipher entirely.

In fact, you might be fine even if one or more of the above happened to be false, as long as none of your potential opponents has the skills or motivation to analyze your scheme and develop an attack against it.  But as long as you're using a cipher with no simple practical attacks, and use it correctly, you should be safe even if someone with some crypto skills does decide to try to attack your system.
Honestly, your biggest weakness is likely to be the last point.  That's how most cryptosystems get broken in practice — not by breaking the underlying ciphers or other crypto primitives, but by finding bugs or design flaws in the way they're used.
To give a simple analogy, the strongest lock on your door won't help if you leave a window open or leave the key under your doormat.  With crypto, as with physical security, the whole system is only as secure as its weakest link.  And the weakest link in your system is almost certainly not the block cipher, whether it's TEA or AES.


How is overflow handled in word addition steps in Salsa20? I feel like I'm completely missing something there. The quarter-round proceeds as follows:

b ^= (a + d) <<< 7;
c ^= (b + a) <<< 9;
d ^= (c + b) <<< 13;
a ^= (d + c) <<< 18;

So at each step, we're adding words a, b, c, d together. And at the end of 20 quarter-rounds, we add the current state matrix with the previous state.

What I don't see is how overflows are handled. If two words added exceed the value of a word, does it simply wrap around?

Per the Salsa20 page -

  Each modification involves xor'ing into one word a rotated version of the sum of two other words modulo 232.

Adding two uint32s and ignoring the carry / overflow is equivalent to performing addition modulo 232.


Does anyone sell a proprietary symmetric encryption alogirthm? I know that the majority of people use standardized encryption ciphers such as AES-256, and for good reason.  But what I want to know is if anyone has come across a company or organization that is selling their own proprietary symmetric encryption algorithm.  I'm doing research on this specific use case and would appreciate some help.

Yes. One prominent commercial example is Cypto AG, a company in switzerland. Its clients include some nation states. Of course most major nation states have their own proprietary diplomatic and military symmetric key algorithms.

See the Crypto AG website here.

Historically, they have been involved in some controversies. See one example report here.

Googling will yield much more on Crypto AG and its history, usual caveats apply. The main objection is lack of open peer review.

Edit: References to Crypto AG's proprietary algorithms are given below. I am not claiming these are secure algorithms, FWIW.

The link here has a company document from 2007:

"For encryption, the proprietary HCA-480 crypto algorithm is used in combination with Customer Managed Profiling (CMP), offering a variety of over 10506. The Communication Key (CK) is 128 bits long and is used to generate a key stream with a period of more than 1028 years."

A newer link is here:

"All systems are based on the sophisticated Crypto Security Architecture, which comprises elements such as a tamper-proof hardware module, customer-controlled and proprietary algorithm [..] emanation-proof hardware (COMPREM) and a flexible security and network management."


Is it possible take a piece of data in secret? I want something like this, but in a digital sense:

  You and others walk into a room. Everyone knows who each of you are and everyone is doing their best to figure out what piece of paper each person is taking. Fortunately the all the paper is in a box. You bring your own envelope, shuffle the papers blindly and put one in your envelope, then walk out.

Since no one can see the inside of your envelope you're fine. The problem is the box.

If a website generates a thousand GUIDs and has to give you one of them, but isn't allowed to know who you are, how would it be done? The website must know you are eligible for a GUID, but how does it give you something to prove you may have a GUID and not know which you take?

I know you can sign something blindly, but can you take something blindly?

As Ricky Demer points out, you can take something blindly. It is called oblivious transfer. There are ways to add access control. See this paper as an example.


Playfair Cipher Confusion with one column encryption Recently I decided to learn "Playfair Cipher", and I have hit a road block.
what do i substitute the letters for if they are on the same column? Here is an example:

CIADX
BEFGH
KLMNO
PQRST
UVWYZ

With the Key being CIAD  (Random Text)

I want to spell the word "trust" but I do not know what rule to follow for the T & R. I would really appreciate help on this. TIA

TR would be replaced using rule 2 of the Wikipedia description:

  If the letters appear on the same row of your table, replace them with the letters to their immediate right respectively (wrapping around to the left side of the row if a letter in the original pair was on the right side of the row).

So TR would become PS. See also step 10 of the example there.

Note that T and R are on the same row, not the same column.

You may want to use a larger key (i.e. one that includes more characters of the alphabet).


On what basis are block sizes chosen? Sha1/0 (160 bits output), md5(128 bits output) has block size of 512 bits.
Gost has 256 bits.

What is the reason behind having it specifically  512/256/1024 bits?

What are the various factors which are considered while choosing a specific block size for an algorithm ?

Sorry for the naive question !! :-)

Let $N$ be the block size in bits, used in the Merkle–Damgård construction of the given hash function.

The smaller $N$ is, the more iterations have to be executed to yield the hash value, hence the algorithm becomes more (computationally) expensive.

The larger $N$ is, the more inefficient it becomes for messages of length $M$, where $M<N$, since the input message would have to be padded out until it fills at least one block of size $N$. It would not be desirable having to add 1013 bits of data if you only need to hash 10-bit inputs. (in fact, you would have to pad out a bit less since there is a field-length field at the end of the block)

Finding a trade-off lies with the developers - I guess 512-bit blocks have been established as a consensus as MD5, and most SHA-2 members work on this length.


Origin of the Chi-Squared test statistic for serial test (two bit test) On page 181 of Handbook of Applied Cryptography Chapter Five, it states the following:

  The purpose of this test is to determine whether the number of occurrences of 00, 01, 10,
  and 11 as subsequences of s are approximately the same, as would be expected for a random
  sequence. Let $n_0$, $n_1$ denote the number of 0’s and 1’s in s, respectively, and let $n_{00}$,$n_{01}$,$n_{10}$,$n_{11}$ denote the number of occurrences of 00, 01, 10, 11 in s, respectively. Note that
  $n_{00} + n_{01} + n_{10} + n_{11} = (n − 1)$ since the subsequences are allowed to overlap. The
  statistic used is
  $$ X_2 = \frac{4}{n-1}(n_{00}^2+n_{01}^2+n_{10}^2+n_{11}^2)-\frac2n (n_0^2 +n_1^2) +1$$

Where does this statistic come from? I'm not entirely sure, and the book doesn't explain it's derivation. Normally, $ X=\frac{(Z-\mu)^2}{n^2}$ for Chi-Squared test ( if i recall correctly), but I don't see how this can result in the expression above. For each $n_{ij}$, the approximate value is $\frac{n_i+n_j-1}{4}$, and the expected value would be $\frac{n_i+n_j}2$, but how do we combine them in such a way that we get the expression for $X_2$?

If this belongs in Math, rather than Cryptography, I can happily delete and move it. I just figured since the question is cryptography related, it may receive better attention here.

This is an interesting question. According to page 3-18 of  available at NIST here it is a common mistake to think the variance statistic is a traditional chi squared statistic. It is not, due to dependence of the overlapping length 2 windows, so a differential statistic is used.

This statistic has been shown to converge to chi squared by I.J. Good, see the reference on the following page of the linked document, who was involved in the enigma decryption effort with Turing. Thus one must take at least a bitstring of 21 bits.

Here is the discussion


What about using AES-ECB with random IV? Let P1P2...Pn be n blocks plaintext, and M0 be a random IV. Then a n+1 blocks message M0M1...Mn can be constructed by setting Mi+1 = Mi xor Pi+1. Finally, we use AES-ECB to encrypt this message. Is it as secure as using AES-CBC?

No, this is not a secure way of encrypting.  Specifically, it does not meet the requirements for indistinguishability under chosen plaintext attack (IND-CPA), a basic security definition for encryption.

According to IND-CPA, no attacker should be able to win the following game:

The attacker selects two equal-length plaintext messages.
The defender picks one of those plaintexts at random
The defender encrypts that plaintext and provides the ciphertext to the attacker
The attacker wins if it can determine which of the plaintexts was used

Here's a winning strategy for an attacker facing your scheme:

Let plaintext message 1 consist of a single block containing only zero bits.
Let plaintext message 2 be any other single-block message.
If the defender returns a ciphertext where the two ciphertext blocks are equal, then the attacker knows that plaintext message 1 was selected; else, the attacker knows that plaintext message 2 was selected.

Here's why this works:

In plaintext message 1, $P_1 = 0^n$ (i.e. $n$ zero bits), where $n$ is the number of bits in a block.
This means that $M_1 = M_0 \oplus P_1 = M_0 \oplus 0^n = M_0$,
so $M_1 = M_0$.
ECB mode produces ciphertext blocks $C_i = E_k(M_i)$, and $E_k$ is deterministic, so the ciphertext blocks will also match ($C_1 = C_0$).

In plaintext message 2, this equality will not hold: $P_1$ has at least one non-zero bit, so $M_1$ and $M_0$ will differ in at least one bit, resulting in different ciphertext blocks ($C_1 \neq C_0$).


Which elements of private RSA file are really constitutive of private key? I have used openssl rsa to generate a RSA key of 2048 bits and as expected output belongs to a file beginning with BEGIN RSA PRIVATE KEY pattern.
However this file size is ways larger than 2048 bits.
In order to extract the key, i have used the following openssl command:

openssl rsa -in key.txt -text

which returns data for the following items:

modulus
publicExponent
privateExponent (size is 2048 bits)
prime1
prime2
exponent1
exponent2

So which parts of this file are constitutive of the private key? Which are the only sufficient parts to be understood by a cryptographic system? Can I just strip all data except privateExponent and would it still be interpreted as private key?

EDIT

I seems that the couple (modulus, publicExponent) is the public key. However, as mentionned in your answer, puboicExponent is always 65537? Or have I misunderstood it?

It looks like all i need to perform private key operation is d=privateExponent. however, tools such as openssl would need a formated file with all informations, is there a simple way to make it understand that d (and n retrieved from certificate) is all i have and is sufficient for cryptographic operations ?

This is a harder question than that it looks.

To perform "plain" RSA modular exponentiation you can simply use the private exponent and the modulus. However, for faster RSA calculations that use the Chinese Remainder Theorem (CRT) you need the prime values, exponents and modulus. For RSA CRT you don't need the private exponent.

In principle you can calculate all private values from the primes: that's just RSA key pair generation after all: you find primes and then you perform calculations on them. So just storing the primes is a space efficient option. However, it does mean you have to recreate the modulus and private exponent or the CRT parameters before every RSA calculation, which will take time.

There is one even more space efficient option: store the random seed from which the prime search starts from, but it comes with a large set of problems (such as having to find the primes for each calculation, which is a terribly inefficient operation). However, it does mean you can store just 128 bits.

To get back the CRT parameters from just the private exponent and modulus is possible, but it takes time and thus negates any advantage to use CRT in the first place. So that kind of calculation should just be performed once, if at all. It can make sense if you first did choose plain RSA and then decide to go for CRT calculations. This is hard to do - tools will generally not include this option - so I would try and avoid having to ever use it.

The public exponent you don't need for private key operations. Sometimes the public key is used to verify that the operation concluded successfully (e.g. by verifying a signature right after generating it). This is of course a fully optional operation and usually only performed to make sure nobody messed with the generation in the first place.

You can say that the public exponent is mainly included because it may be easily / efficiently calculated / guessed from the private exponent, so including it makes sense for PKCS#1, where the structure in the question is defined.

Note that the public exponent is often simply set to a single small value, 65537 or F4, the fifth prime of Fermat. This is what OpenSSL (currently) uses by default.

EDIT: I don't think you can leave too much out if you're required to deal with OpenSSL. OpenSSL uses PKCS#1 or PKCS#8 private RSA keys. PKCS#8 simply includes the PKCS#1 private key, so that representation is just ever so slightly larger.

In turn, PKCS#1 is defined as follows (from the ASN.1 module in Appendix C of RFC 3447 that defines PKCS#1):

--
-- Representation of RSA private key with information for the CRT
-- algorithm.
--
RSAPrivateKey ::= SEQUENCE {
    version           Version,
    modulus           INTEGER,  -- n
    publicExponent    INTEGER,  -- e
    privateExponent   INTEGER,  -- d
    prime1            INTEGER,  -- p
    prime2            INTEGER,  -- q
    exponent1         INTEGER,  -- d mod (p-1)
    exponent2         INTEGER,  -- d mod (q-1)
    coefficient       INTEGER,  -- (inverse of q) mod p
    otherPrimeInfos   OtherPrimeInfos OPTIONAL
}

as you can see, most of the stuff in there is non-optional. Only otherPrimeInfos can - and usually will already - be empty as it is used for CRT multi-prime computations.


Is random.org truly reliable? Can someone help me in gaining an understanding of the reliability of random.org being used by a University to select student applicants to extend invitations to?

Yes, using random.org to randomly select students is appropriate, since random.org creates truly random numbers from atmospheric noise.
But for cryptographic purposes you shouldn't rely on random.org as this post explains.


Do key collisions for symmetric ciphers exist? I'm not sure if I'm calling the thing (key collisions) correctly, and that's probably why I couldn't find any information about it on Google. Still, my question is as follows. Note that I don't work with encryption right now and I'm not going to implement anything based on this knowledge; this is a purely theoretical question which I found very interesting.

Suppose that you have a key K and a plain text P. Then you use some symmetric algorithm A like one of AES variants to obtain a ciphertext C = A_encrypt(P, K). Is it possible that some key K* != K exists which can be used to get back the plain text out of the same ciphertext, i.e. P = A_decrypt(C, K*)? How it depends, if it does, on the type of the cipher (block vs stream), on the exact algorithm and on the size of the key and the size of the plain text? My intuition suggests that impossibility or, at least, improbability of such thing is the reason of existence of symmetric ciphers, but still this is not stated explicitly anywhere I could find.

What surprises me that I couldn't find anything which answers such question directly; moreover, I couldn't find anyone asking such question. All I could find are questions like this which seem to be related but not exactly the same as my question, and questions like "how to generate two keys to decipher the same data" which are somewhat opposite to my question.

The number of possible permutations of a block cipher are $2^n!$ where $n$ is the block size. A permutation maps all $2^n$ possible input blocks to $2^n$ possible output blocks. A key, with key space $2^k$ selects one of them. Although that's a huge number of keys, it is dwarfed by the amount of possible permutations.

Now it's not by definition impossible that the same permutation can be chosen by a key, but it is pretty unlikely. Such a key would be considered an equivalent key or - less specifically - a weak key. Many algorithms are designed to disallow weak keys. If it is possible to have the same permutation then it is likely to be present by design; you won't find one by chance alone.

Finding two keys that map a single specific plaintext to identical ciphertext or vice versa is much more likely. It depends on the block cipher details if this is anywhere near possible see this discussion on AES for more information.

For stream ciphers the question is somewhat more difficult. It probably suffices to say that the output of the stream cipher is determined by a key and an IV (sometimes fused into one, for instance in RC4). If the size of the key, IV and internal state of the stream cipher are large enough, you should not be able to find a large amount of repetition in the key streams generated for separate key / IV pairs.

It will be possible to find keys that generate small amounts of identical key streams. This is easy to see; about half of the keys should decrypt a single bit correctly. It may be impossible to determine if you'd have generated the correct plaintext though; you'd have to determine the two keys in advance.

The idea expressed above would also work for a block cipher in a streaming mode of operation such as CTR (counter mode).

These kind of questions have been asked, but they are tricky to find if you don't know the right terms - and probably even if you do.

Related is the question if algorithms contain back doors. In that case the attacker should be able to decrypt whatever the key value is though.

Deniable encryption is another somewhat related term.


Selection of rotation constants in ARX design My question is about choosing the rotation values in ARX design such as SIMON-like or SPECK-like ciphers to provide optimal differential and linear immunity. According to this, the selection of $a$ and $b$ values (shown in SIMON-like figure below) must comply with the condition $\text{gcd}(n, a-b) = 1$ where $n$ is the size. Attached ARX structures with $2/4$ branches of SPECK and Marx (Mix + arx).

How have the rotation values been selected? Was the selection it ad-hoc (then tested against common cryptanalysis such as differential/linear or rotational) or systematic such as the selection of $a$ and $b$ in SIMON-like? does the size of plaintext size (32/64/128 bit) influence the round constants?

Leaving besides that the designers (NSA) of Simon and Speck did not provide an initial design rational for their ciphers/parameter choices, they added some notes later after pressure from the cryptographic community/ISO. There they mention that they selected the round constants to be

  ... optimal with respect to resistance against 8-round differential and linear attacks...

and

  ...many of these led to poor performance on software devices (especially
  8-bit microcontrollers) and so were rejected...

There are some other ARX ciphers like for example Chaskey and MergeMAC who argument the choice of the round constants with

  ... our choice of constants, implementation on 8- and 16-bit
  microcontrollers will be more efficient than had these constants been
  chosen at random ...

and

  The rotation constants in our permutation are chosen to be optimal for
  microcontrollers which often only allows efficient rotations/shifts by
  one or two bits, and byte-permutations by 8-bits.

So one of the reasons for the choice of rotation parameters is that they are optimal for implementations.

Another point for choosing the rotation parameters comes from a security point of view regarding differential/linear attacks. The non-linearity of ARX ciphers only comes from the modular addition. If we look closer into modular addition, we can see that the non-linearity actually just stems from the carry propagation (more details i.e. here), as the sum is simply just an XOR (which is linear).
In general, for ARX ciphers the best rotation constants would shift a
difference to a position where it reaches the msb last (as a difference
in the msb is not counted in the calculation for the probability).
Therefore, one can ensure that the differences quickly build up and are
not canceled out.

Moreover, regarding the rotation constants for Speck, the designers of the block cipher Sparx mention in their paper

  While it is possible to choose the rotations used in Speckey in such a
  way as to slightly decrease the differential and linear bounds, such
  rotations are more expensive on small microcontrollers which only have
  instructions implementing rotations by 1 and by 8 (in both directions)

and they also provide the different rotation constants that actually would improve the differential/linear bounds of Speck (for the cost of less efficiency):

  Both can be lowered by a factor of 2 if we choose rotations
  (9,2),(9,5),(11,7) or (7,11) instead of (7,2).

The size of the plaintext influences the choice of round constants indirectly, as one would have to choose a constant such that it is obviously between 1 and the wordsize = plaintext size/number of branches. This is because a rotation of 0 won't change anything and a rotation large then the wordsize would just be the same as a rotation modulo the wordsize.


Can I combine two of SHA-3 candidates cryptography hash functions and obtain more secure Algorithm? For example, Is possible to combine (Concatenate or Chain or XOR) Skein SHA-3 candidate with Grostl SHA-3 candidate to increase security?

Note: I just want more secure output and CPU cycles does not matter

The basic problem with combining primitives in a hashing or encryption function is that when doing so, you have to be sure that the combination doesn't expose some weakness. When talking about hashing, the three main desirable qualities are one-way transformation (absolutely critical), even distribution (after hashing a sufficiently large number of messages and plotting a histogram of the hash values, you would expect all buckets of the histogram to be equal), and high avalanche effect (related to randomness, adding or changing a single bit in the message should produce a massive and theoretically unpredictable change to the hash value).

When coming up with a hash algorithm, designers combine primitives in such a way that they can mathematically or empirically demonstrate the relative level of strength in these three areas. Conversely, third parties can demonstrate weaknesses in these areas. For a simple example, take the original FNV-1 checksum hash; for each byte of input, the working hash is multiplied by the FNV prime and then XORed with the input byte. People using it found that while it worked well for checksums, if these two operations were reversed, the algorithm exhibited much better avalanche characteristics and more even distribution, leading to the commonly-used "FNV-1a" variant described in the whitepaper.

By combining hash algorithms in a particular order, you may or may not create a stronger algorithm. You may increase the one-wayness of the algorithm, but conversely you may at the same time reduce the set of possible hashes (either by hashing a hash into a lower-bit output or reducing the distribution of hash values within an absolute range). The same applies to performing primitives of a hashing function in differing order, as evidenced by the above example.

Lastly, the combination of primitives you chose may induce a weakness; neither FNV-1 nor 1a are crypto hashes for many reasons, one of them being that regardless of which way you perform the primitives, the least significant byte is always the XOR of all input bytes each XORed with 1. That reduces the set of all possible collisions with a particular hash by half; a cracking algorithm could very quickly spin through this "carry XOR (lsb XOR 1)" sequence to determine that a candidate message won't work. By doing so you effectively reduce the complexity of brute-forcing a collision with the given hash by a power of 2, thus breaking "strong collision resistance". If a crypto hash had this weakness it would be considered broken.

If you want a secure hash, consider bcrypt. First off, bcrypts are relatively small to store as strings since they're Base64-encoded (60 chars/bytes, vs 64 for a hex-encoded 256-bit hash), but they store as much entropy as a 256-bit hash. Second, not only is bcrypt slow, it's configurably slow, by increasing the number of steps for a key initial stage of hash generation by powers of two. Thus, the algorithm can easily be adapted to keep up with Moore's law; every year and a half, you just increment the complexity of the hash and presto, it takes twice as long to brute-force the hash, offsetting the empirical doubling of processing power during that time.


What is the private key in RSA? I'm new to cryptography and I have a doubt: I read some pages a bit different definition for the RSA private key:

In 1 - (n, d)

In 2 - (d)

In 3 - (n, p, q)

Should I consider all these answers as correct? I know that if you have d and the public key, you have n (and e), and I know pq = n too.

For private key operations you need at least $n$ (the modulus) and $d$ (the private exponent). The primes $p$ and $q$ let you calculate those – or use some shortcuts for quicker computation – so they also suffice.

In practice RSA keys often include all of those values, to avoid having to compute them as needed and to allow for optimized and unoptimized implementations.

  In 2 - (d)

This would not be enough on its own, but the page actually says that the private key includes the modulus.


Is there any open-source white-box implementation of AES or DES? I googled it, but got no result.  There is a binary executable of a white-box implementation of DES (scroll down), but no source code is provided.

The same page also links various papers about white-box cryptography, but these don't contain the implementation.

I want to study such an implementation to learn about the techniques used there.

I add my whitebox AES implementation on GitHub in:

C++
Java

C++ version implements both Chow's (mixing bijections, input/output encodings, external encodings) and Karroumi's (dual AES in each column) whitebox AES scheme plus Billet's key recovery attack on both schemes.
Java implements Chow's scheme only.
PS: Due to low reputation I post links to schemes to the comment below.


Can you change an AES encrypted message if you control the IV? Let's say that an attacker has the plaintext, the ciphertext and the IV of a specific message. If the attacker can control the ciphertext and the IV, could he forge valid plaintext? Let's say that the message is shorter than the block size, just a few bytes. Could the attacker change the value of the plaintext by changing the IV?

Consider the case where you encrypt the plaintext message attack at noon!! using AES-CBC-256, with the key 7ac01f50605b8fcebd1c82ea6a6aacd6b112e8c9675b84cd77054b2f49668301 and the iv f822ee7b8c0a8ba40daa773b01d9485a:
echo -n 'attack at noon!!' | openssl aes-256-cbc -e -nopad -K 7ac01f50605b8fcebd1c82ea6a6aacd6b112e8c9675b84cd77054b2f49668301 -iv f822ee7b8c0a8ba40daa773b01d9485a | xxd -p

The plaintext message is one block in length (16 bytes), and no padding is used, so this produces one block of cipher text:
8b2f9ede941cb6f3958d809510f579a5

Naturally, if you decrypt the ciphertext above using the same key and iv, you get the original plaintext:
echo -n '8b2f9ede941cb6f3958d809510f579a5' | xxd -p -r |  openssl aes-256-cbc -d -nopad -K 7ac01f50605b8fcebd1c82ea6a6aacd6b112e8c9675b84cd77054b2f49668301 -iv f822ee7b8c0a8ba40daa773b01d9485a

produces:
attack at noon!!

Now, an attacker who knows the original plaintext (attack at noon!!), the ciphertext, and the iv wishes to modify the iv, so that upon decryption, the plaintext produced is attack at dawn!!.
To see how this is done, refer to the diagram below (copied from https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation):

Consider point labeled E.  E is the AES decryption of the first block (in the case, the only block) of ciphertext, using the key.  We don't know the key, so we can't compute E...
Or, can we?  Looking further, the first block of ciphertext is E XOR IV.  The XOR function is unique in that: if A XOR B = C, then you can re-arrange A, B, and C in any order, and the expression still holds true - i.e. A XOR C = B, and B XOR C = A.  So:
Plaintext = E XOR IV
E = Plaintext XOR IV
IV = E XOR Plaintext

So, knowing the original plaintext (attack at noon!!) and the IV (f822ee7b8c0a8ba40daa773b01d9485a), we can compute E.  To do this, we use E = Plaintext XOR IV (above).  First, use the following command to get the hex representation of the underlying ascii-decoded bytes of the plaintext:
echo -n 'attack at noon!!' | xxd -p

This produces:
61747461636b206174206e6f6f6e2121

Now, XOR the plaintext and the IV to get E like so:
python3 -c "print (hex(0x61747461636b206174206e6f6f6e2121 ^ 0xf822ee7b8c0a8ba40daa773b01d9485a))"

This produces:
0x99569a1aef61abc5798a19546eb7697b

So, E is 99569a1aef61abc5798a19546eb7697b.
Now, we can compute what the IV should be, so that when the ciphertext is decrypted by AES-CBC with our specially crafted IV, and E gets XOR'd with this IV, the plaintext produced will be our wanted plaintext 'attack at dawn!!'.  To do this, we use IV = E XOR Plaintext (above).  First, get the hex representation of the underlying ascii-decoded bytes of the wanted plaintext, like we did before:
echo -n 'attack at dawn!!' | xxd -p

this produces:
61747461636b206174206461776e2121

Now, XOR the the wanted plaintext with E to get the IV that we need, like so:
python3 -c "print (hex(0x61747461636b206174206461776e2121 ^ 0x99569a1aef61abc5798a19546eb7697b))"

This produces:
0xf822ee7b8c0a8ba40daa7d3519d9485a

Let's see if it worked.  Let's use the decryption command above to decypt the ciphertext, using iv f822ee7b8c0a8ba40daa7d3519d9485a in place of f822ee7b8c0a8ba40daa773b01d9485a:
echo -n '8b2f9ede941cb6f3958d809510f579a5' | xxd -p -r |  openssl aes-256-cbc -d -nopad -K 7ac01f50605b8fcebd1c82ea6a6aacd6b112e8c9675b84cd77054b2f49668301 -iv f822ee7b8c0a8ba40daa7d3519d9485a

Sure enough, the plaintext produced is:
attack at dawn!!

***Special thanks to Ángel for helping me work through this in the comments under the question.


Relations between RSA and Generalized Diffie-Hellman (GDH), factoring and GDH Definition: (The generalized Diffie-Hellman problem)
Let $n=pq$ for two large primes $p,q$. Given $x, x^a, x^b,n$, find $x^{ab}\pmod{n}$.

(1) Is there a known reduction from the GDH problem to the RSA problem (i.e. finding $m$ from $m^e\pmod{n}$)?
(2) Is there a known reduction from the GDH problem to integer factorization?
(That is, given an oracle which solves the second problem mentioned in (1)/(2), can you find an efficient algorithm which solves the GDH problem?)
Side-notes:

There is of course a reduction from GDH to DLOG, but I do not know of a reduction from DLOG to integer factorization or to the RSA problem.

It is known that the RSA problem limited to $e=2$ (i.e. finding square roots modulo $p$) can be reduced to integer factorization, but this is a non-interesting case. For a general $e$, AFAIK such reduction is not known.

Also, I am just as interested to hear about DH instead of GDH. (The DH problem is the same as GDH, but with a prime $p$ instead of semiprime $n$.)

Breaking the Generalized Diffie-Hellman (GDH) assumption is known to imply Factoring for Blum-integers. This is a result by Biham et al.
Since the (non)-equivalence of the RSA and Factoring assumptions is one of the biggest open questions in the RSA literature, it would be really surprising if there was a reduction from GDH to the RSA assumption, because then we would have the equivalence of the RSA and Factoring assumptions for Blum-integers given the result of Biham et al.


Fast attack on approximate GCD problem? This question is about the approximate GCD problem which is defined as follows: Given any number of the approximate multiples $a_i = p \cdot q_i + r_i$ of $p$, where $p$, $q_i$ and $r_i$ are integers, the problem is to find the hidden common divisor $p$. Note that $q_i$ and $r_i$ change in each $a_i$.

I've recently read “Practical Fully Homomorphic Encryption without Noise Reduction” by Liu, about a fast symmetric FHE scheme, which is based on the approximate GCD problem. Now the paper claims that it reaches 128-bit security by increasing the linear search space's size to $>2^{128}$.

Is there any attack on the approximate GCD problem, that is faster than brute-force (trying out all possible approximate GCDs)?

As an example set of (brute-force secure?) parameters, I'd say that $\log_2q_i\approx64\approx\log_2r_i$ and $\log_2p\approx 128$ should be secure against brute force as one would need $2^{128}$ tries for retrieving $p$ or would have to try more than $2^{64}*2^{64}=2^{128}$ values for $q_i$ and $r_i$.

This doesn't address your question; however the algorithm in the paper is broken.  The paper does show that recovering the key requires you to solve the approximate GCD problem (which may be difficult); what they don't show is whether recoverying the plaintext requires solving a hard problem.  It turns out that it isn't that difficult at all (a bit of linear algebra), and hence the attacker can get at what he really wants (after all, the only reason we're interested in the private key is because the key would give us access to the data).

The insight behind this is that the decryption process for a fixed private key is entirely linear; the system attempts to make decryption without the key infeasible by restricting all plaintexts to be within an $N-1$ dimension subspace (where the ciphertexts are vectors of size $N$); however if the attacker knows $N-1$ linearly independent ciphertexts, and the values they correspond to, then he can, for any ciphertext within that $N-1$ dimension subspace, find the linear combination of the known ciphertexts that make it up (and hence deduce the plaintext that corresponds to it).  Since any valid ciphertext will be within that linear subspace (that's inherent in the system), that means that we can decrypt anything.

This doesn't address the question of "is approximate GCD a hard problem"; however it does break that specific cryptosystem.


How to perform a parallel hash over a large file without changing the sequential hash result? I want to use parallel hash for a large file. I want final result equal to single hash from this file. What techniques would be best suitable to solving this problem?

If you want to produce a hash compatible with an existing sequential hash, like SHA-2, you're out of luck. But when you choose a parallel mode, you can always compute the same output using a single thread.

The two most important parallel constructions are:

Interleaved

You initialize a fixed number of sequential hashes. Then you feed them one block in turn. At the end of the file you take the outputs of the individual hashes and hash it down into a single hash.

The biggest downside of this approach is that you need to choose the maximal parallelism at design time and changing it breaks compatibility. It still needs to process the file start to finish, it can only take advantage of multi-core CPUs but can't parallelize IO by hashing different parts of the file at the same time.
A (deep) Merkle-Tree.

For example the Tiger-Tree-Hash splits the file into 1 KiB and computes an unlimited depth binary hash tree over it. (Don't forget tagging leaves and inner nodes differently, or an equivalent mechanism to avoid ambiguities)

This has slightly higher CPU (a few percent) and memory (a few KB) overhead. It can only parallelize hashing files larger than the leaf size.

In exchange you can hash pieces independently in any order and the maximal parallelism grows with the file size.

Personally I prefer the tree approach due to its flexibility.

If you can use a key, you can use a PRF/MAC instead of a collision resistant hash. For example GHash (the MAC part of GCM) is very flexible in how it allows you to partition and parallelize the computation. It's also much cheaper to compute than collision resistant hashes.