Can a QR code be scanned if split using visual cryptography?

A typical problem with the images regenerated by visual cryptography is that they have low contrast: when using superposed transparency, the white in the original image tends to become grey (or more precisely, 50% dithering of black and white, which is even worse from a 2D-code scanner's perspective); and there might be some white that creep in the black areas due to misalignment. This will be tolerated by some scanners, but will mess others. Scanning will be more difficult that with the original.

The classical scheme in figure 2 there will I guess not work reliably if each block on the original QR-code is split in two rectangles, as shown in that figure.

What would work better is to subdivide each block of the QR-code into a finer matrix, e.g 8x8: each block of the QR-code is turned to either X= or Y=, where white is actually transparent:

A black block in the QR-code is, with odds 50%, turned to X in the first transparency and Y in the second transparency, or Y in the first and X in the second; so that the superposition of the transparencies will be essentially black.
A white block in the QR-code is, with odds 50%, turned to X in both transparencies, or Y in both transparencies; so that the superposition of the transparencies will be essentially grey (50% dithering of black and transparent).

No information can be extracted from a single transparency.

It might help to encode specially the blocks that convey only structure: Finder Pattern, Separator, Quiet Zone, Timing Pattern (if any), Alignment Pattern (if any). For these I suggest, in order to help determining orientation and putting the transparencies with the same side up:

A black block in the QR-code is represented as black in both transparencies.
A white block in the QR-code is represented as X or Y in both transparencies, according to $(h+\lfloor v/2\rfloor)\bmod 2$ where $h$ and $v$ are the block's coordinate as integers.

The above does not solve determining from which side the transparencies shall be scanned: not all scanners accept mirror images. But it would not be a good idea to solve this by replacing one transparency by a white sheet, as it could tend to worsen alignment problems: different materials react differently to humidity and aging. This side up probably will do (and be the simplest for orientation).

Choice of the appropriate block subdivision is a compromise: too coarse, and the scanner might consider the pixels of the block as the grid of the 2D barcode; too fine, and alignment of transparencies will become infeasible.

If one used polarizing filters with orientation of X and Y different by 90°, there would be no need for subdivision of QR-code blocks into smaller pixels, truer white (assuming a non-polarized light source behind the aligned transparencies), and no dithering for grey, thus easier reading. However, I know no automated way to prepare the transparencies; closest to a workable idea is to start from transparent polarized squares the size of a QR-code block, and glue them in the appropriate orientation on some grid.


Is this protocol for masking DB ids sound?

What you are looking for is a randomized authenticated cipher of short bit strings, 64 bits long.  You seem to be willing to accept between 64 and 256 bits of ciphertext expansion.

With an $r$-bit randomization string, the probability of a collision after $n$ ciphertexts—which would, at the very least, reveal equality of masked ids—is at best bounded by about $n^2/2^r$.
With $t$-bit authentication expansion, the probability of forgery after $f$ attempts is at best bounded by about $f/2^t$.

You could use any randomized authenticated cipher you like, e.g. NaCl crypto_secretbox_xsalsa20poly1305, which has a 192-bit nonce and a 128-bit authentication tag; if you use a 128-bit nonce chosen uniformly at random (padded with zeros up to 192 bits), you're safe as long as you limit yourself to well below $2^{64}$ ids, e.g. limit yourself to a billion ids.  You could use AES-GCM, but the limits are even smaller because the nonce is 96 bits, so you need to limit yourself to well below $2^{48}$ ids.  A nonce collision here is catastrophic, of course.

If you want to build it out of AES and SHA-256, you could just use AES-CBC with encrypt-then-MAC and the 128-bit truncation of HMAC-SHA256.  Since the input is fixed-length, there's no need for padding; effectively, it would just be $$E_{k_1,k_2}(\rho, m) := c \mathbin\| \operatorname{HMAC-SHA256-128}_{k_2}(c), \quad \text{where} \quad c = \rho \mathbin\| \operatorname{AES}_{k_1}(\rho \oplus m).$$  In the case of a collision in $\rho$, this still leaks only equality of masked ids.  Obviously, you can derive $k_1$ and $k_2$ from a single 32-byte master key $k$ with HKDF-SHA256.

Here's a very simple approach that uses a single call to AES with a single key, to encrypt a 64-bit id $m$ with 64-bit randomization $\rho$ under key $k$: $$E_k(\rho, m) := \rho \mathbin\| \operatorname{AES}_k(\rho \mathbin\| m).$$  Here $r = t = 64$, so we're using 192 bits to encrypt a 64-bit id.  Let $\pi$ be a uniform random permutation; for any forgery attempts $\rho_1 \mathbin\| c_1, \dots, \rho_f \mathbin\| c_f$, the probability that there is any $i$ such that $\pi^{-1}_{64}(c_i) = \rho_i$ is bounded by $f/2^{64}$, where $\pi^{-1}_{64}(c_i)$ is the first 64 bits of $\pi^{-1}(c_i)$.  Consequently, the distinguisher and forgery advantage of any algorithm against $E_k$ is bounded by $(n^2 + f)/2^{64} + \varepsilon$ where $\varepsilon$ is the best advantage at AES from a uniform random permutation.  If you mask a million ids and your bandwidth limits the adversary to a trillion forgery attempts, the odds are less than one in eight thousand that the adversary will win.  Even if there is a collision in $\rho$, again this only leaks equality of masked ids, although forgery might be a bigger issue.

What about the scheme you described?  It's more complicated than necessary: you could do away with the IV, for example, and always use zero instead.  If you use a 32-bit randomization string like you suggested, then you'll see a collision with high probability after only a few tens of thousands of ids, and when this happens, this leaks not only equality of two masked ids, but the xor of the two masked ids.


Strength of block ciphers under attack [by government level attackers]

Obligatory XKCD: coercion (or/and bribery) works. Other usual strategies are

Rigging the particular machine used by the data owner.
Otherwise spying key-presses on that machine to obtain the password.
Password search (including by compromising this user's other passwords and trying variations); that's an industry that has several professional-looking offers, targeting at least law-enforcement budgets (your guess of other users is as good as mine). It works for encrypted data at rest, as in the question.
Finding the desired data (or the password) in a non-encrypted area, such as swap space, sidestepping the question's problem.

Directly breaking AES (even AES-128) by brute force is so hopelessly hard that it is unreasonable to even attempt that.

Side channel attacks (like timing attack and DPA) are entirely useless for encrypted data at rest, because the key is not there to be extracted.

AES implemented with AES-NI or other hardware is immune to timing attack, and I believe is immune to DPA on today's mainstream CPUs, except perhaps with most direct access to the CPU using the key (as feasible in Smart Cards); that's a risk, but a manageable one.


Alter plaintext in block cipher AES in CBC mode

So if you consider ASCII encoding you have two plain text blocks: "SEND ME THE DATA" and " ENCRYPTED" + padding (which we will ignore). Note the space before "ENCRYPTED".

Now if you change the IV you will indeed only change the first block. What you should however do is to change the first block of the ciphertext. That is used as vector (not the initialization vector, but the next vector) for the CBC decryption of the next block.

As you can see, each bit or byte that you change will be directly reflected in the plaintext. So if you want to flip a single bit in the plaintext you simply flip the bit at the same position in the previous ciphertext block.

So in the end you may want to end up with something like:

IV: 8f6f27b5dbfa2ba8367262bda7154d95
CT: 798f04f8b06cc27c1591a4088531a64a9b76a9be87a3e944c6e7000f24f5b9f9


Is there a method of encryption where you can't work out the key even with the encrypted and decrypted message?

The point of "modern" cryptography is that "the strength" relies solely on the key.
What you are describing is called a known-plaintext attack and state of the art algorithms (like AES) should not be prone to it.


Making a secure file sharing scheme usable

Here's one obvious problem that you don't mention:

Users register and set their username and password. From this password, a public/private key pair is deterministically generated and the pk is published to the server.

That means if someone downloads the password list from the server, he can go through his list of weak passwords, convert them all into a key pair (using the deterministic process) and see if that public key is listed as anyone's public key.  Given how often weak passwords are used, that's bad.
Even if the username is stirred into the algorithm, it's still bad (the attacker needs to work on each public key separately, that increases his work effort somewhat).
Here's a modification that might make it not so bad; we have the end users generate their public/private keypairs randomly, and then store the private key on the server in an Opaque-type protocol (and the public key in the clear).
That is, the user would take his password $p$ (hashed along with his user name using Argon-2), selects a random value $r$, and computes the EC point $rpG$ over an elliptic curve (where $G$ is the point generator, and the curve may be Curve25519), and sends that to the server, which computes $s(rpG)$ (where $s$ is the server private key) and sends that back to the client; he then computes $r^{-1}s(rpG) = spG$; he then sends that through a KDF, generating a symmetric key $k$, and uses that key to encrypt his private key, and sends that off to the server.
Then, when it comes time to log in, the user enters the password $p$, and repeats the above process, obtaining $k$; the server also gives him the encrypted private key, which he then decrypts.
The disadvantage of this is that the user must interact with the server every time he logs in.
The advantage of this is that an attacker must interact with the server for each password for each user he wants to test; the server can easily notice that it is being queried literally thousands of times for a particular user, and take appropriate action.
And the server never learns the user's private key (it has the encrypted version; however he doesn't learn the symmetric key to decrypt it)


Let's take the definition from Wikipedia:

  Diffusion means that if we change a single bit of the plaintext, then (statistically) half of the bits in the ciphertext should change, and similarly, if we change one bit of the ciphertext, then approximately one half of the plaintext bits should change.

Now, what ever the XOR operation does, it works on 2 bits, 1 bit of the key and one bit of the plaintext. So no, XOR cannot provide diffusion by itself.

In your example, if you change a single bit of plaintext then then the output will only change with a single bit as well. If you applied the output to another bit then you'd still have the same situation (as the two bits flip at the same time).

If the Feistel function itself provides diffusion used with XOR in the steps is a different matter, of course. But XOR won't have provided the diffusion.


Forging RSA1024 signature with e=3 where hash is right justified

When $\gcd(e, \phi(n)) = 1$, integers modulo $n$ coprime to $n$ have a unique $e$th root modulo $n$.  This is the basis of RSA.  Unlike for an unfactored RSA modulus, $\phi(2^{160})$ is easy to compute: it's $2^{159}$.

You can calculate this cube root the same way that you do RSA, essentially.  Treat $2^{160}$ as if it were an RSA modulus, with $e = 3$.  Calculate $d = e^{-1} \pmod {2^{159}}$, which is the value:

$d = 243583606221817153033947472119380503275988757163$.

Now, for numbers $h$ coprime to $2^{160}$--that is, odd numbers--you can calculate the cube root as:

$x \equiv \sqrt[3]h \equiv h^d \pmod {2^{160}}$.

Because $x < 2^{160}$, $x^3$ cannot exceed $2^{480}$, so it will not wrap modulo a 1024-bit RSA modulus $n$.  $x^3 \mod n$ as calculated by a signature verifier would retain the property that $x^3 \equiv h \pmod {2^{160}}$, and your forgery is complete.

Assuming that your hash's low bit is $1$, anyway.


Distributing shares in a particular monotone access structure

Well, the easiest way I can see to represent this access structure is:

Select three random values $r_1, r_2, r_3$
Generate a threshold-2 secret sharing scheme with the secret $S$ (where $S$ is the ultimate secret), and whose shares are $\alpha_1, \alpha_2, \alpha_3$
Generate an independent threshold-2 secret sharing scheme with the secret $r_3$, and whose shares are $\beta_1, \beta_2, \beta_3$.

Then,

$A$ gets $\alpha_1$, $r_3 \oplus S$
$B$ gets $r_1$, $\beta_1$
$C$ gets $r_2$, $\beta_2$
$D$ gets $r_1 \oplus r_2 \oplus S$, $\beta_3$
$E$ gets $\alpha_2$, $r_3 \oplus S$
$F$ gets $\alpha_3$, $r_3 \oplus S$

It's easy to see that any of the allowed subsets can recover $S$ (e.g. for the subset $A, B, C$, they jointly know $\beta_1$ and $\beta_2$, that allows them to recover $r_3$; and with $r_3 \oplus S$ gives them $S$).  It should be fairly clear that any subset not within the access structure gets no information about $S$.

This doesn't give an answer to the precise question to raised; it does appear to solve the problem you were trying to address.


Is there a way to slow down collision attacks using iteration?

As others have pointed out in the comments, using the message in the hash iteration can dissolve collisions in the inner hash again. Additionally, the round number can also be used, in case you have collisions over different rounds. But concatentation is just one possible way to combine these values as input.

If your assumption is just a general hash function, you should have a function $f$, and then set:

$h_1 = H(m)$
$h_{i+1} = H(f(h_i,m,i))$

Concatenation might be one possibility for $f$, but it could be problematic in Merkle-Damgard constructions. You could also use a hash function for $f$, but that wouldn't adress this problem. Alternatively, you could use an MAC instead, where you use the hash of the previous round and $i$  to derive the key, and you can choose from the various MAC algorithms. Alternatively, you could also use a block cipher directly as $f$, just like the MAC algorithms (well, some MACs are based on block ciphers). But you will have to keep in mind, that $m$ itself might be a lot longer. A more general way might be the assumption of a PRF.

On a similar note: Alternatively, you could use a  CSPRNG based on a hash function, seed it with the message, and then iterate just "far enough", that it matches your wanted number of iterations, and use that as output.

For your consideration of 128 bit, I would say CMAC/OMAC with AES could be used, e.g.$f:= CMAC_{h_i}(m||i)$


We want a non-trivial factorization of a moderate odd integer $n$ into positive integers $p$ and $q$, knowing that such factorization with $|p-q|$ suitably small exists.

Perhaps the most elementary method answering the question is trial division by integers starting at $\lfloor\sqrt n\rfloor$, going down. This succeeds after checking divisibility of $n$ by at most (very slightly less than) $|p-q|\over2$ candidates. Some easy speedups are possible (skipping even candidates, generalizable to candidates divisible by the first few small primes).

The method described in this comment, and equivalently in this answer, also work. They succeed after testing at most $|p-q|\over2$ candidates. Depending on implementation (of the squareness test in particular), speed can be slower or faster than trial division.

I'll describe a method that avoids any trial and error under the assumption that $|p-q|<(64n)^{1/4}$. With the given $n=2189284635403183$, that translates to $|p-q|<19348$, which very comfortably holds since $|p−q|<20$ is given.

Theorem: Given any odd integer $n$, if there exist unknown integers $p$ and $q$ with $n=p\times q$ and $(p-q)^2<8\sqrt n$, the following non-iterative algorithm outputs these $p$ and $q$:

compute $a=\lceil\sqrt n\rceil$ (that is, the smallest non-negative integer which square is at least $n$)
compute $s=a^2-n$, which amazingly will be the square of some integer
compute $b=\sqrt s$ (that is, the non-negative number which square is $s$)
output $a+b$ and $a-b$.

Proof:

Without loss of generality we reorder $p$ and $q$ so that $p\ge q$. We know $p$ and $q$ are odd, since their product is. Thus, when we define $c={p+q\over2}$ and $d={p-q\over2}$, these are non-negative integers. Further, $c^2-n=d^2$ holds.
In step 1 of our algorithm, $a$ is computed as the only non-negative integer $x$ satisfying $x^2-n\ge 0$ and $(x-1)^2-n<0$. From $c^2-n=d^2$ it follows that $x=c$ satisfies the first of these conditions. The second condition is $(x-1)^2<n$, which is satisfied if $0\le x-1<\sqrt n$, that is $1\le x<\sqrt n+1$. $x=c$ satisfies $1\le x$, since $c={p+q\over2}$ with $p\ge1$ and $q\ge1$. Thus $c<\sqrt n+1$ would imply $a=c$.
Since $c\ge0$, we can equivalently prove $c^2<(\sqrt n+1)^2$, that is $n+d^2<(\sqrt n+1)^2$, that is $({p-q\over2})^2<(\sqrt n+1)^2-n$, that is $(p-q)^2<4((\sqrt n+1)^2-(\sqrt n)^2))$, that is $(p-q)^2<4(2\sqrt n+1)$. It follows from our hypothesis $(p-q)^2<8\sqrt n$.
We have shown that step 1 produces $a=c$; thus step 2 produces $s=a^2-n$ equal to $d^2$; thus step 3 produces $b$ equal to $d$; thus step 4 outputs $p$ (for $a+b$) and $q$ (for $a-b$), Q.E.D.

The above is the basic Fermat factorization method, but reduced to its first step and without any test (because we can do without it in the question, and that simplifies our algorithm and proof). The full basic Fermat method performs $\Big\lceil{(p-q)^2\over8\sqrt n}\Big\rceil$ tests, and thus requires less computing effort than trial division from $\sqrt n$ by a factor of $O\big({\sqrt n\over|p-q|}\big)$ as a first-order approximation; this can be huge, but only when $|p-q|$ is much smaller than likely under random selection of $p$ and $q$ in an interval of width a sizable fraction of $\sqrt n$. Description of Fermat's methods, classic improvements, and computing cost, would be the subject of a different question.


Diffie-Hellman when $p$ and $g$ are pre-agreed and hidden from Eve

For the moment assume $g$ is a secret (uniformly random) generator, but that $p$ may be known to the adversary. Then given only $g^a, g^b$, the Diffie-Hellman key $g^{ab}$ is information-theoretically uniform (up to small statistical error), i.e., it cannot even be found by brute force because the adversary does not have enough information to determine it. This is because every generator $h=g^c$ for all $c$ (coprime to the group order) is equally likely to be the "real" one, so the "real" key is equally likely to be $g^{ab/c^2}$. Such values essentially cover all group elements (up to rare degeneracies). So essentially, Alice and Bob have a true one-time pad value.

However, this is not really interesting, because Alice and Bob were able to set up a secret generator $g$ in the first place, which is just as good as (or better than) a one-time pad value.

If Alice and Bob use the same $g$ for two or more runs of the protocol, then there is only one "degree of freedom" in the derived keys. That is, knowing one key (and the public messages) information-theoretically determines all the others. So any hope that the keys would look uniform and independent would have to depend on a computational assumption.

This all assumed that $p$ was known. It's much harder to analyze what happens when $p$ is unknown, because revealing group elements reveals some information about $p$, but it's hard to say what.


Is there a way to systematically calculate the public exponent $e$ in RSA?

The question asks how to systematically pick the public exponent $e$ in RSA. I'll stick to public modulus $N$ that is the product of exactly two distinct odd primes $p$ and $q$, but the choice of $e$ is not fundamentally different in multiprime RSA.

What's an acceptable public exponent $e$?

The public exponent in RSA should be an integer $e>1$ with $\gcd(e,p-1)=\gcd(e,q-1)=1$, so that $e$ will have an inverse both $\pmod{p-1}$ and $\pmod{q-1}$; or, equivalently, such that $e$ will have an inverse $\pmod{\phi(p\cdot q)}$. This insures that $e$ is odd, for we have assumed that $p$ and $q$ are.

Also, $e$ must not reveal so much information (about $p$ or $q$, or $\phi(p\cdot q)$) that it significantly simplifies factorization of $N$. This rules out some non-iterative constructive methods like $e=\max(p,q)$, or $e=(p-1)(q-1)+1$, or $e=(p-1)(q-1)-1$ (which do insure that $\gcd(e,p-1)=\gcd(e,q-1)=1$, assuming $\min(p,q)>3$ for the last formula).

Some RSA definitions, most notably PKCS#1, require $e<N$. There is no stated rationale for that requirement.

An old, straightforward (but non standard) method to chose $e$

If we ignore the requirement that $e<N$, one straightforward method is to set $e=N$, which satisfies all other requirements provided that $\min(p,q)$ does not divide $\max(p,q)-1$ (which does not hold in the example in the question, but is extremely likely for large random primes $p$ and $q$; and is certain if $2\min(p,q)>\max(p,q)$, or if $p$ and $q$ have exactly the same bit size, or if $2^{k-1/2}<p<2^k$ and $2^{k-1/2}<q<2^k$ for some integer $k$; all of which are common requirements for $p$ and $q$, listed by increasing selectivity).

This choice of $N$ as the public exponent historically is the first method that was considered, before RSA got named (C. Cocks, A Note on "non-secret encryption", classified GCHQ note dated 20 November 1973, re-typeset here). It is demonstrably as safe as can be with respect to attacks factoring $N$ (or equivalent to that), since we do not reveal anything beyond $N$, which we make public anyway; however, as noted by Chris Peikert, the RSA problem (of finding $x$ knowing $x^e\bmod N$) might be easier for this choice of $e$ (we have no indication of that).

A PKCS#1-conformant (if not standard) method to chose $e$ from $N$

An idea is to select $e$ as a prime with $N/3\le e<N$; such $e$ is acceptable, since it is a prime at least $\max(p,q)$, thus co-prime to $p-1$ and $q-1$. We can pick the smallest prime at least $N/3$, or the highest prime less than $N$. For small $N$ we can restrict to $e$ in a table of pre-computed primes: $7$, $17$, $41$, $97$, $257$, $769$, $1153$, $2113$, $4129$, $12289$, $18433$, $40961$, $65537$, $163841$, $270337$, $786433$.. (I have picked values with at most 3 bits set in their binary representation, which slightly simplifies raising to the $e$th power). Since these choices of $e$ do not depend on the factorization of $N$, they can't help factorize $N$ (but we have no idea if that's a bad or good choice w.r.t. the RSA problem).

The above methods are uncommon, for reasons explained below. To my knowledge, standard and safe methods to chose $e$ somewhat use trial an error in the choice of $e$ from $p$ and $q$, or the choice of $p$ and $q$ from $e$; and most such methods have additional objectives.

Should $e$ have other characteristics?

There is incentive not to chose $e$ too large, for a large $e$ slows down the public-key operation (about proportionally to the bit size of $e$) with no tangible benefit provided proper padding is used. That's one good reason not to use any of the above methods. FIPS 186-4, appendix B.3.1 puts the limit at $e<2^{256}$. In fact, $e\ge2^{32}$ has become uncommon, for it has caused interoperability hurdles with some RSA implementations (formerly including that bundled in Windows); and unduly long waits for users of Smart Cards.

Some standards/security authorities set a lower bound on $e$, typically $e>2^{16}$. That's of debated rationality when using a proper padding scheme.

It is common to choose $e$ prime, because this decreases the amount of trial and error, for odds that a prime $e$ and much larger prime $p$ meet $\gcd(e,p-1)=1$ are $(e-2)/(e-1)$ (thus quickly converging to $1$ when $e$ grows) if either $e$ or $p$ is random; while odds are lower if we remove the condition that $e$ is prime (the odds become mostly independent of the magnitude of $e$; as a hint to that, odds that two large integers each uniformly chosen below some limit $m$ are coprime converges to $6/\pi^2\approx60.8\%$ when $m$ grows). As an aside, if $e$ is composite, revealing it as part of the public key arguably reveals even so slightly more information about $p$ and $q$ (or about $\phi(N)$ or $\lambda(N)$) than if $e$ was a large prime, for there are less possible $p$ and $q$ knowing $e$.

There is also incentive to choose $e$ of the form $2^i+1$, because that's allowing the fastest computation of $x^e\bmod N$ for a given size of $e$ (only $i$ modular squaring and one modular multiplication are required). If we combine with $e$ prime, that leaves the Fermat primes $F_j=2^{(2^j)}+1$ with $0\le j\le4$ as the only candidates (it is conjectured that there exists no other Fermat prime, and known that there are none of manipulable size).

Choice of $p$ and $q$ before search of $e$ by trial and error

RSA key generation as in a textbook typically choose $p$ and $q$ first. An unobjectionable method to then chose $e$ is to try values of $e$ that are moderate random primes in some suitably large interval, until one $e$ is found such that $e$ does not divide $p-1$ or $q-1$. Such $e$ is acceptable w.r.t. both $p$ and $q$ (assumed much larger, random and independent primes) with odds $(e-2)^2/(e-1)^2$, thus high for all but very small $e$. If we specify a large enough interval for $e$ (e.g. $2^{16}<e<2^{17}$) and the choice of $p$ and $q$ is without relations to the primes in that interval, it is not even necessary to insure that the $e$ tested are distinct to find a suitable $e$ quickly, with overwhelming odds.

Some (including the teacher in the question) select $e$ as the lowest prime at least some fixed minimum (chosen no less than $3$) dividing neither $p-1$ nor $q-1$ (or not dividing $\phi(N)$). Notice that doing so often reveals some information about $\phi(N)$: if in a large collection of public keys known to have been generated by the same device we see keys where $1/4$ of the $e$ are $3$ (thus $25\%$ of $e$), $9/16$ of the other $e$ are $5$ (thus about $42.2\%$ of $e$), $25/36$ of the other $e$ are $7$ (thus about $22.8\%$ of $e$), and generally $(r-2)^2/(r-1)^2$ of the other $e$ are $r$ for $r$ the successive primes starting from $11$, we have reverse-engineered the choice of $e$, and know that for the few public keys of the form $(N,23)$, $\phi(N)$ and $\lambda(N)$ are a multiple of $3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19$, which can be used to speed-up a straight brute-force search of these quantities (it is likely that there is at least one such public key if we gathered $27600$ of these). It might give a feeling of discomfort, although we do not know that such knowledge can significantly improve one's ability to find $\phi(N)$ or $\lambda(N)$ knowing the public key, or otherwise derive a working private key, or factor $N$ (rationale: these goals are equivalent, factorization of $N$ is by far the most efficient avenue known to reach any of these goals, and we do not know how to use a known moderate divisor of $\phi(N)$ or $\lambda(N)$ to speed up that factorization).

We can also choose $e$ as an (odd) random integer (not necessarily prime) in some similar interval until $\gcd(e,p-1)=\gcd(e,q-1)=1$. It will require significantly more trials, but success is also virtually insured; and by the same reasoning as above, whatever little extra information we leak is not a worrying security issue.

Hand computation of small $e$ for moderate $p$ and $q$ expressed in decimal

We can easily test divisibility by the primes $5$, $3$, $11$, $37$, $101$. We'll pick the first $e$ in this list that is suitable. Odds that none is suitable are only $0.0068\%$.

If neither of $p$ and $q$ has a $1$ or $6$ as its rightmost decimal digit, then neither $p-1$ nor $q-1$ is divisible by $5$, and we select $e=5$. That won't do for the example in the question (because $q=11$ ends in $1$), but is enough for $p=14627$, $q=15959$ (because neither $7$ nor $9$ are $1$ or $6$).

Otherwise, we sum the digits in $p$; subtract $1$; recursively sum the digits in the result, until the result is single-digit; if that digit is not divisible by $3$, $p-1$ is not, and we do the same test for $q$; if we find that $q-1$ is not divisible by $3$, we select $e=3$. That's the case for $p=5$, $q=11$ in the question (because neither $4$, nor $1$, are divisible by $3$).

Otherwise, we use similar techniques for $e=11$, $37$, and $101$; the divisibility rules are explained here.

Choice of $e$ before search for $p$ and $q$ by trial and error

Real-world RSA implementations tend to choose $e$ first, typically because

very commonly, $e=2^{16}+1=65537$ is required, because that's the minimum value recognized as acceptable by all security authorities, thus unobjectionable and well-supported;
sometime $e=3$ is required, because that gives the best speed of the public-key RSA operation, with no known drawback if proper padding methods are used;
having a fixed $e$ simplifies the transmission of the public key; in that case, one of the Fermat primes $F_j=2^{(2^j)}+1$ is typical.

With $e$ prime, we can pick a prime $p$ such that $p-1$ is not a multiple of $e$, and it insures $\gcd(e,p-1)=1$. The contrary has odds only $1/(e-1)$ for random prime $p$, and that's rare enough to be mildly hard to test for the very popular $e=2^{16}+1$.

An unobjectionable method reducing guesswork (especially for the smaller $e$ like $3$) is to chose $e$ prime, then when it comes to the choice of $p$ chose a secret $f$ uniformly random with $0<f<e-1$, then only explore candidate primes of the form $p=(2k+(f\bmod 2))\cdot e+f+1$, which insure $p$ is odd and $\gcd(e,p-1)=1$. $f$ should be randomly drawn again when it comes to the choice of $q$.


How to break AES/CBC/PKCS5 when key and IV are reused?

Well, there is no really good way; the encryption of the plaintext is $E_k( Plaintext \oplus IV)$ (followed by 16 bytes which are a deterministic function of the first ciphertext block). The AES function $E_k$ is designed to be totally unpredictable if you don't know the key, there's nothing to leverage there. The only thing that allows you to gain any advantage is that the encryption function itself is deterministic; that is, about the best you have available is:

Make a guess as to what the plaintext might be
Ask that be encrypted
Check to see if that ciphertext happens to match anything on your list
Rinse and repeat

Not by any means an ideal solution; however it's the best option you have available.

Now, if the plaintext had been longer than 16 bytes, you could use the above procedure to confirm a guess on the first 16 bytes of the plaintext, and then work on the next 16 bytes -- with your specified parameters, that's not an option.


Block ciphers as secure as AES but immune against cache timing attacks?

There are no efficient attacks against AES that I know of (not counting the related key attacks on AES-256). The minimum security offered for AES-128 is still around 126 bits, and that's with pretty inefficient attacks. Furthermore it is studied very well, so nobody is going to present a cipher that has seen so much cryptanalysis (other than its predecessor DES). So yeah, "as secure" is going to present a problem I guess.

If you look at a cipher that doesn't use a Feistel network you might want to have a look at Threefish. It is a tweakable block cipher with a larger block size, a large number of rounds and large key sizes. As it is part of Skein, a SHA-3 finalist, it did receive some cryptanalysis. The main attack against it is a key distinguishing attack, which is not practical for the full round version and is not applicable when Threefish is used solely as a cipher. Oh, yeah, and it doesn't use tables :)


(moved from comment, expanded slightly)

(AES) Key Wrap is not the same as normal data encryption like CBC or GCM; it does quite a bit of remixing, and adds exactly 64 bits to any AES "plain key" (here 256 + 64 = 320 = 40 bytes) even though it uses the AES algorithm which has a 128-bit data block. See http://tools.ietf.org/html/rfc3394 and the relevant example in section 4.6.

The KEK is indeed 256 bits in this case, determined by the algorithm id-aes256-wrap, but that key doesn't appear in the message; it is derived from ECDH key agreement, using the originatorkey in the message (in the BITSTRING at offset 54) and the key in the recipient cert identified in the message.

The ECDH key(s) here appear to be on a 521-bit curve, presumably secp521p1, although on looking closer I notice it is not encoded in the AlgorithmIdentifier for originatorkey as is normally the case for encoded public keys. If the ECDH curve were substantially smaller, then the key-agreement strength would be less than 256, which would make the use of a 256-bit CEK in a sense wasted.


Is this SHA-256 modification still valid?

We typically model a hash function (in particular $\mathrm{SHA}$-$256$) as a function $H:\{0,1\}^{2^{64}-1} \to \{0,1\}^{256}$ with some special properties that makes them useful in practice.

Well, that definition is indeed rather particular to SHA-256. The output size is of course depending on the hash function, and e.g. SHA-3-256 has an infinite input space.

In this case, the probability for a collision is around $2^{-256}$ which is assumed to be infeasible in practice.

No, for the function the probability for creating a collision using many tries is closer to $2^{-128}$ because of the birthday bound. You're showing the chance of a pre-image happening, and that only for a single try. Discussing collision resistance for hashes over any two distinct messages doesn't make much sense.

Where could I find when (and why) a probability is "low enough" in practice? I assume it is something related with computer's limits...

Depends on how the hash function is used and the threat model of the particular use case. If you'd ask me about a generic minimal security limit then I'd go for 128 bits (presuming only attacks using classical computers). That would mean a 256 bit hash when it comes to collision resistance - and not pruning any bits.
Now for particular use cases you may go lower. You may want to keep in mind that generating $2^{128}$ hashes is not practical; the birthday bound assumes you compare many hashes after all. So there is probably some leeway when it comes to memory requirements for any attack.
Keyed hashes (HMAC) are a different matter entirely. There you would only need 128 bits to achieve 128 bit security.


CONIKS Prefix Merkle Tree - is it necessary to change tree-wide constant for each update

As Gary Belvin from Trillian replied:

  In Trillian we use a tree wide constant for computing hashes (See
  MapHasher) in order to achieve as close to l bit security as possibe
  and prevent attacks between trees and between different locations
  inside of a tree.

  As you've noted, the map does not update the tree nonce for each
  revision of the map. Recomputing the entire map tree for each update
  would be prohibitively expensive and would prevent the Trillian Map
  from being a system that supports near-realtime updates. This tradeoff
  is described in the CONIKS paper, section 3.1

  To attack multiple revisions of the same tree, an attacker searches
  for a collision, and then hopes that a future version of the tree
  contains a node that matches the collision. If every leaf node changed
  at every revision, this would be a lot of new nodes to hope for a
  match against. However, in the map, the number of new nodes is < tree
  depth * updates, which grows linearly, not exponentially.

  Even if every node of the map changed at each revision, we should
  still be safe. If I'm reading Katz correctly, in order to maintain l
  bit security in a multi-instance setting we need l + log(N) bits in
  the hash function, where N is the total number of map revisions. 256
  bits of hash output should be sufficient to maintain 128 bits of
  security for 2^128 revisions.


X.509 ECDSA signature field in DER format includes '00' between bit string and sequence of r and s

No, the 00 simply indicates how many least significant bits are not used in the last octet of the BIT STRING.

As the bit string contains an octet string (consisting of the sequence of two integers) it will always be zero, as all the bits in the BIT STRING are used. This is defined for the BER/DER encoding of BIT STRING itself.

As for why the signature is not specified as an OCTET STRING itself, well, beats me, as most signatures are defines as OCTET STRING anyway, even if they are not constructed such as RSA signatures.


You need a key stretching function, not a mere key derivation function. A key stretching function is technically a kind of key derivation function, but most key derivation functions are not key stretching functions. A key stretching function is intrinsically slow to reduce the possibility of brute force guessing, and includes a salt input to make precomputations useless when attacking many accounts. See How to securely hash passwords? for more explanations: hashing a password and deriving a key from a password are very similar cryptographic problems with basically the same solution.
SP800-108 and SP800-56A are families of ordinary (non-stretching) key derivation functions. They are not suitable here. I don't know what CAPI_KDF is but according to the Windows API documentation it doesn't take a salt or a difficulty parameter so it can't be a key stretching function.
PBKDF2 is a key stretching function. It's designed precisely for what you want to do. It has weaknesses, but that's compared to more modern key stretching functions. Specifically, PBKDF2 intrinsically requires a lot of computing power, but very little memory, so it can be executed more cheaply on GPU or ASIC (which an attacker would typically use) than on a CPU (which the legitimate server is using). Scrypt and Argon require a lot of RAM (comparatively) which can only be realistically available on the same kind of hardware that a typical server is using, so the attacker doesn't have an advantage in terms of computing power. So PBKDF2 is not the best choice if you have a choice. But you don't have a choice: you don't have access to bcrypt, scrypt or Argon2. (Note that “bcrypt” here is the algorithm, it's unrelated to “bcrypt” as in bcrypt.h in the Windows API.) So use PBKDF2.
PBKDF2 for hashing passwords (or deriving keys from passwords) is ok. It isn't ideal, but it's ok. All of your other options would be catastrophically wrong.
Generally you should only use the key obtained with PBKDF2 to wrap (encrypt) another key. This way, when the user updates her password, you only need to update this wrapped key.
If you're both authenticating the password and deriving a key from it, see Is it safe to split the output of PBKDF2?
Note that a key stretching function can't do miracles. If the password space is too small, it's realistic for an attacker to try them all. For example, at 1 attempt per second (which is on the high side), it only takes a few hours to break a 4-digit PIN (13.3 bits of entropy). A case-insensitive 4-letter password with random letters has 18.8 bits of entropy and would only last a few days without parallelization. You really should make the minimum length higher.


Can Hill Cipher be considered as Asymmetric?

No, because matrix inversion can be done efficiently. Namely, if encryption is multiplication by a matrix $A$, then you can define decryption with $A$ as first computing the inverse of $A$ and then multiplying.

An essential property of public-key cryptosystems is that it should not be possible to efficiently derive the (private) decryption key from the (public) encryption key. In the Hill cipher, the matrix must be kept secret.


The equivalence of SIS and ISIS(Inhomogeneous SIS)

Write $A = [A_1 ~~ A_2]$ with
$A_1 \in \mathbb{Z}_q^{n\times m'}$
and
$A_2 \in \mathbb{Z}_q^{n\times (m-m')}$.
Likewise, $e = (e_1 ~~ e_2)$ with
$e_1 \in \mathbb{Z}_q^{m'}$
and
$e_2 \in \mathbb{Z}_q^{m-m'}$.
Then,
$$Ae = 0 \bmod q \iff A_2e_2 = -A_1e_1 \bmod q.$$
So, given an instance of SIS, that is, an $n\times m$ matrix $A$,
if you have an oracle to solve ISIS, then you can write $A$ per blocks as above, sample a short $e_1$, define $y := -A_1e_1 \bmod q$, and use the oracle to obtain a short $e_2$ such that $A_2e_2 = y \bmod q$.
Your SIS solution will then be
$e = (e_1 ~~ e_2)$.


With all well-regarded hash functions, the bits of the hash all have equal worth: as far as anyone knows (unless they aren't telling), the bits are not correlated. If you take $k$ bits of an $n$-bit hash, you get a $k$-bit hash function. Truncating SHA-256 to 255 bits gives you a hash that's almost as good as SHA-256: it has $2^{255}$ strength against preimage attacks and $2^{127.5}$ strength against collision attacks.

There are precedents for taking certain bits of a hash. SHA-224 and SHA-384 are obtained with calculations that are essentially the same as SHA-256 and SHA-512 respectively, just with different initial values (which shouldn't matter to the strength of the algorithm) and with the output truncated to the smaller size. Another precedent is that UUID can be constructed from 122 bits of MD5 or SHA-1 hashes (out of 128 or 160 respectively).

For SHA3, there's a cleaner construction. Instead of taking SHA3-256 and cutting off one bit, take the SHAKE256 255-bit or 248-bit output. SHAKE256 is exactly the same as SHA3-256 except for two bits near the beginning of the calculation, so it has the same security properties, but it's explicitly designed to have variable-length output. You can even use SHAKE128 instead of SHAKE256, which is slightly cheaper to compute with no meaningful security loss.

It's unlikely that there's an actual security problem with truncating a hash, but using SHAKE gives you greater confidence that nothing will go wrong. Even better, to avoid domain collisions (where two parts of the system calculate the hash of the same string for different reasons), calculate the cSHAKE output with a unique string as the customization string.


You won't find the answer in the RFC; instead, here's what your SSL implementation is doing: when you send a single byte of data, it actually generates two records.

The first record is empty; so it consists of the 5 byte record header, and the encryption of the 20 byte HMAC tag (which, after encryption padding, is 32 bytes long); this is a total of 37 bytes.

The second record consists of the actual data; so it consists of the 5 byte record header, and the encryption of the data (1 byte) and the 20 byte HMAC tag (which after encryption padding, is 32 bytes long); this is a total of 37 bytes.

This totals to 74 bytes, which is exactly what you're seeing.

Also note that if you send more than 11 characters (and less than 28) of data, then the data along with the 20 byte HMAC data would require 64 bytes; this would extend the total data sent to 90 bytes (again, exactly what you see)

Now, why might an implementation choose to do this?  Well, it's a defense against the BEAST attack.  By including a dummy record up front, it makes the IV used to encrypt the actual data unpredictable (and hence foiling that attack); because the dummy record isn't sent until we actually have the data, the attacker cannot use it's IV value to select the data to encrypt.


Why don't we have 256-bit security level digital signature schemes (in common use)?

The trivial answer is that there doesn't exist any relevant security threats that entail a requirement for long term authentication. There do however exist relevant security threats that warrant long term confidentiality.

Assume you have a document and need to prove its authenticity. If you apply a digital signature to the document, but the digital signature scheme you use is later broken, it might still be possible for you to later reestablish the authenticity of the document using other means. For instance, there might be external witnesses that can vouch for the authenticity, the document might be recorded in multiple locations, making forgeries reasonably unlikely, etc.

However, if you encrypt the document for confidentiality and the encryption scheme is broken, there is no way for you to ever reestablish reasonable confidentiality guarantees. If the document is no longer confidential, re-encrypting it obviously won't restore confidentiality.


Is it possible to recover the seed value from a Mersenne Twister PRNG state?

I was wondering if you could be able to recover the actual seed value used or if an attempt would yield an equivalent at best?

Yes (and it turns out to be not that expensive computationally).

The Mersenne twister state is an invertible linear function of the seed, hence recovering the unique seed is possible.

  Also, closely related, let's say we use a 32-bit seed value. Does this mean that a mersenne twister generator could yield $2^{32}$ different sequences for each unique seed value or are there seeds which produce the same sequence?

Every seed will generate a unique sequence.  This is a stronger statement than what I just previously made (it would be conceivable that two different states would generate the same sequence - however, that doesn't happen with Mersenne).


LED (AES like) algorithm Decryption-Mixcolumn

The inverse of LED MDS matrix is :

$$\left[
\begin{array}{c c c c}
12 & 12 & 13 & 4 \\
3 & 8 & 4 & 5\\
7 & 6 & 2 & 14\\
13 & 9 & 9 & 13\\
\end{array}\right]$$

you can verify it.

this is sage code that generates the inverse MDS matrix.

f=x^4+x^1+1  # irrudiciable polynomial
L.<z>= GF(2^4,modulus=f)
R=PolynomialRing(L,'x')
N=16
m=[(4,  1, 2, 2),(8,  6, 5, 6),(11,14,10, 9),(2,  2,15,11)]
T= matrix(m)
#print S.inverse()
print m
print T
P=matrix(L,4,4)
P_1=matrix(L,4,4)
for i in range(0,4):
    for j in range(0,4):
        P[i,j]= (T[i][j]) + z^1*(T[i][j]>>1) + z^2*(T[i][j]>>2) + z^3*(T[i][j]>>3)

print P
P_1=P.inverse()
print P_1
# print the matrix with clear distance
for i in range(0,4):
    for j in range(0,4):
        print P_1[i,j]
    print ""


Think about this: what does it mean that $\gcd(e_B, e_C)=1$. Formally that means there exist some $s_1, s_2$ such that $e_Bs_1 + e_Cs_2=1$.

Say you have two ciphertexts (the following math is all done modulo the shared modulus), $C_B=M^{e_B}$ and $C_C=M^{e_C}$. You can do the following:

$$\begin{align}
C_B^{s_1}*C_C^{s_2}&=(M^{e_B})^{s_1}*(M^{e_C})^{s_2}\\
&=M^{e_Bs_1}*M^{e_Cs_2}\\
&=M^{e_Bs_1+e_Cs_2}\\
&=M^1\\
&=M
\end{align}$$


comparison of security for identity based signature and Hashing (SHA-1) the identities

Of the two, identity based is more secure. In fact, unless you have left details out of the question, a SHA-1 hash (or any hash for that matter) of the sender's identity and the message content provides no source authentication (or data integrity check).

According to your comment, the way you would use SHA-1 to authenticate this is to concatenate the senders identity and the message, and compute the SHA-1 hash of that value. The problem is, anyone who knows your identifier can do this for any message. To illustrate this, consider the message I, SARA, give all my money to mikeazo.. Surely you wouldn't send this message, but, as proof that you sent it, here is the "authentication" tag: 92a7904e083e41d8667b92b7100d9d970eb0e84c.

You can check that SHA-1(SARA I, SARA, give all my money to mikeazo.) == 92a7904e083e41d8667b92b7100d9d970eb0e84c. So that message must have come from you, so where is my money?


Why is Boneh-Franklin IBE scheme secure? What should an adversary do to break it?

The proposed scheme is IND-ID-CPA secure and is semantically secure in a random-oracle model.
From the paper:

The proof of security for our IBE system makes
use of a weaker notion of security known as semantic security (also known as semantic security against
a chosen plaintext attack). Semantic security is similar to chosen ciphertext security (IND-IDCCA) except that the adversary is more limited;

And detailing IND-ID-CPA:

We say that an identity-based encryption scheme $E$ is semantically
secure (IND-ID-CPA) if no polynomially bounded adversary $A$ has a non-negligible advantage against
the Challenger in the following IND-ID-CPA game:

The paper then goes into detail (which I suppose you've read).  But basically the game involves the adversary not being able to better than guess the value of an encrypted bit for a chosen public key.  The adversary has access as to as many other public/private keys as it wants.
The scheme is not IND-CCA secure.  As per this answer here one way to attack the scheme would be to gain access to a "decryption oracle".


There is not much special about near field communication here - it is just like any insecure transport medium, which can be evesdropped on (with external antennas up to several meters in distance).

Because of the low distance limit, there is no way for a man-in-the-middle attack if you (the human operator) are sure that your device is communicating with the right reader, but there is the relaying attack (your blackberry communicates to a reader, which forwards the data to another device which communicates to the real reader), which also might including the replay problem.

I would recommend not to build a new protocol (especially if you are new to cryptography), but to reuse existing, generally known, protocols. In this case, the usual TLS (Transport Layer Security) protocol seems like a good fit, if you can provide your "server" with a private key which is kept secret, and whose corresponding public key could be certified by some certificate agency whose key (or root key of some chain) would be known to the "client".

In the usual way of SSL/TLS operating, client and server negotiate a shared secret, from which the session keys are then derived.

(I suppose it would be easier to let the Blackberry be the client and your windows machine the server, but it would work the other way around, too.)

I don't know anything about Blackberry programming (nor .NET), but I suppose that there are SSL/TLS libraries available for both.

Note that while this avoids replay attacks (the keys are individually creating depending for each session, and won't work later), this doesn't really help against the relaying attack - so make sure to only transmit your payment details to sellers you trust.


Proof that LFSR (with XOR feedback and nonzero seed) will never hit state of all 0s

Any linear map (as used in the LFSR next bit computation) gives zero output when loaded by the all zero state, by definition of linearity. So one can never leave the all zero state, which maps onto itself. As @poncho points out the LFSR state mapping is reversible so one can never enter that isolated all zero state from any of the remaining states.


Why doesn't the GCM spec use a more efficient multiplication algorithm?

My question is... why?

There are a number of different algorithms that perform $GF(2^{128})$ multiplication, all with different trade-offs (speed on specific platforms, program size, memory usage, complexity, side channel resistance, etc).  NIST doesn't care which one you use, as long as you get the expected result at the end.

As for why NIST decided to put that specific algorithm as an example in the spec, well, I didn't write the spec, so I can't be certain.  My guess is that they decided on the goals of simplicity and clarity, and that algorithm was the best they could find that would meet those goals (whether it is actually simpler or clearer than algorithm 2.40 is, of course, debatable...)


Encrypt a file for multiple persons with different keys?

Now the condition is, that each employee has different key material
solve the above problem, without the overhead for the additional headers

Based on your requirements - you must have the different key material for each user... which obviously has to be stored somewhere.  You don't want it in headers ... so it either needs to be in a different file / database, or in the meta-data.
We had a similar problem which we solved using Extended File Attributes instead of additional headers.  The symmetric file key was encrypted for each authorized recipient using the recipients RSA Public Key and the result was stored in the file meta-data.
https://en.wikipedia.org/wiki/Extended_file_attributes
Some filesystems have default limits on the amount of meta-data you can store. You may need to configure those.


Correct integer input value for keccak 256

Define 'correct'

That is less silly of an answer than you might think; SHA-3-256 is a function from bitstrings (or bytestrings) to 256 bit hashes; it has no predefined ideas about a mapping of an integer to those bitstrings; it'll work for any of them.

Now, the application which is using SHA-3 might have such a predefined idea, and hence might define a 'correct' way.  However, there is nothing in the code segment above would define it, and we have no idea what application you are attempting to be compatible with.

If you have no predefined application, and are just looking for a plausible way, might I suggest converting the integer into a little-endian 4 byte string (or 8 byte, if the integer value might be above 4 billion).  That's as good as any...


Sensitivity of probability measure in differential privacy

Do you need local differential privacy (i.e. no central server knows the real data of individuals) or global differential privacy (where you have all the real data, and want to generate differentially private statistics out of it)?

In the former case, you need to add a significant amount of noise (typically Laplace noise) to each probability, and there's basically no better way of doing it. This will mean that every data point will be very noisy, but if you have enough of them, you might be able to retrieve some information. The "amount of noise" will be similar to the randomized response mechanism described here or here.

In the latter case, it depends on what you're computing. If you're computing the average probability, the noise you add can be scaled by $1/n$, where $n$ is the total number of users. See for example the methods presented here, in the "summing or averaging numbers" section.


In both mathematics and cryptography, given a function $H$ from set $A$ to set $B$, and an element $b$ in $B$, a preimage of $b$ by $H$ is any $a$ in $A$ such that $H(a)=b$.

In cryptography, a public function $H$ from set $A$ to finite set $B$ is:

First-preimage-resistant when for a given random $b$ in $B$, it is hard to exhibit a preimage of $b$, that is, $a$ in $A$ with $H(a)=b$.
Second-preimage-resistant when for a given random $a_0$ in $A$, it is hard to exhibit another preimage of $b=H(a_0)$, that is, $a$ in $A$ with $a\ne a_0$ and $H(a)=H(a_0)$.

A preimage can in principle be found by trying various values of $a$ in $A$ (other that $a_0$ for second-preimage), and computing $H(a)$ until it matches $b$ (the given $b$ for first-preimage, or $b=H(a_0)$ computed from the given $a_0$ for second-preimage). Depending on the definition of $H$, there can be better methods.

A common design goal of practical cryptographic hash functions is that the expected effort to find a preimage (of either kind) is not much less than $|B|/2$ times the effort for computing $H(a)$ once, where the notation $|B|$ designates the number of elements in the set $B$. When $B$ is the set of exactly $n$-bit bitstrings $\{0,1\}^n$ (as is common for cryptographic hashes) the quantity $|B|/2$ becomes $2^{n-1}$.


Figure 2 in the Verifiable Computation - Pinocchio

Yes, this is correct. The $r_i$ are arbitrary elements of the base field, their values are unimportant as long as they are all distinct.


Avoid decrypting every password in a password manager

I understand your design goal, but I see an issue in that you propose to encrypt the metadata alongside the passwords.  Searching is made more complicated because you have to decrypt the database to expose the metadata to search for the associated password.

Instead, consider storing only encrypted, unique passwords in your database, indexed by a secure hash of the site/username metadata.  For any new site that requires a password, locate a slot indexed by $H(meta)$. Generate a unique password for that site, encrypt it with the master, and store it at the hash slot. Give the plaintext to the website.

To access the password later, reverse the steps.  This lets you encrypt only the passwords, and uses a strong hash function to protect the mapping between the site and the password even in the event of a disclosure of the master password.

[A few edits later,] Here is a protocol that might work.  It assumes you have a secure hash function $H$, a wallet $W$ indexable as a dictionary with no entries to start, and a secure master password $m$.  Assume $E_p(data)$ means to encrypt data with key $p$, and $D_p(data)$ means to decrypt.  Let $meta$ be a tuple representing the site name, user name, cookie, or anything else that makes sense to include for retrieving a password.

When visiting a site $s$:

Let $i \leftarrow H(meta)$.
If $i \not \in W$, then this is the first visit to the site (with this meta tuple); generate unique password $p_s$ (conforming to the policy at $s$) and encrypt with $E_m(p_s)$ and store at $W[i]$.
If $i \in W$, then site has been visited before, therefore retrieve site password $p_s \leftarrow D_m(W[i])$.

The benefits are that you decrypt only a single password for each site $s$.  The master password $m$ is used only for site password protection, not for the metadata.  The identity of the sites and meta information are protected with a hash function.  With a fast implementation of $W$, lookup can be as fast as $O(1)$.  A dictionary indexed by a hash can grow dynamically, better than my previous edit.

On the downside, if the adversary has access to $W$ and meta information on $s$, he can tell that you have an account on that site.  By encrypting the entire database including metadata, your original design is secure against this threat.

I haven't thought more than a day on this, so there may be a weakness - hopefully someone will comment and I'll continue to revise it.


Why are in asymmetric cryptography as many keys as people involved needed?

Actually you are both wrong, assuming that each user wants to authenticate themselves individually and / or establish private conversations between pairs. Unfortunately this is assumption is missing from the question. If everybody is using (EC)DH then they need a key pair each to setup communication by establishing a session key. That means 10 times 2 keys = 20 keys. However, quite often key and key pair are confused, so the professor is really talking about the latter, only counting the private keys / key pairs, making 10 the correct answer.

If you establish a "master" user that you trust, and no entity authentication is required then you are correct. You need just one private key pair known to all, initially distributed by the master setting up the group. Then you can e.g. encrypt a session key with the public key and only those that have the private key can decrypt. Arguably this is not a good example of asymmetric cryptography though: the private key is now a shared secret, something that is common for symmetric cryptography rather than asymmetric cryptography. The sharing of the private key is required in this scheme, otherwise an adversary can join by identifying as one of your friends.

Note that just having 10 key pairs is not enough to authenticate all the users and setup 1:1 communication. It is also required to trust the public keys. Authentication is about proving you have (access to) a private key that belongs to a public key known to belong to you by the other user.

Note that I've talked about (EC)DH rather than RSA in the first section. It is common to setup (multiple) session keys in transport protocols rather than encrypting directly with the public key and decrypt with the private key. Of course, this requires a set of temporary keys in addition to the asymmetric keys.

It is possible to perform encryption / signature generation with just 10 key pairs, so session keys are not necessary. However, that's really not following good cryptographic practice. So I decided simply not to count the symmetric session keys.


Probability of guessing random 128-bit AES key

To randomly guess a single key from a 128-bit key space has a chance of 1 divided by the number of elements or $\frac{1} {2^{128}}$ where $2^{128}$ is the number of keys possible.

To get ballpark figures to convert between base 2 exponents and base 10 exponents you can use the following trick:

Because $2^{10} = 1024 \approx 10^3$ you can easily count the number of decimal digits, then divide by 3 and multiply with 10. To go from the number of bits to the number of decimal digits multiply by 3 and divide by 10.

If you want to be more precise: you can divide or multiply with the constant value $\log_2(10) = \frac1{\log_{10}(2)} = \ln(10) / \ln(2) = 3.321928094\ldots$

(easy to remember in your pocket calculator or phone).

So as an AES key is 128 bits you can easily see that it represents about $10^{\frac {128 * 3}  {10}} = 10^{38.4}$ possible values. The bigger the possible value the less likely it is to guess (or brute force) one.

To get to the possibility of winning the lottery you have to calculate $\frac1n$ where $n$ is the number of contestants. To calculate the chance of winning it x times in a row you have to calculate $(\frac1n)^{x}$ which is equal to $\frac1{n^x}$.

As you can see that one million is $10^6$ you can then see that winning it 5 times in a row would be identical to pick one value out of $10^{6^5} = 10^{30}$ values. So you have a significantly better chance of winning the lottery 5 times: $\frac1{10^{30}}$ than picking a random 128 bit AES key: $\approx \frac1{10^{38.4}}$


Are common cryptographic hashes bijective when hashing a single block of the same size as the output?

It would be very freakish if it turned out to be true. It is not an expected property of SHA-512 to have such bijectivity. It would be worrisome, even, because that's a kind of structure that should not appear in a proper cryptographic hash function.

Actually proving that SHA-512, for 512-bit blocks, is not bijective, would already be a kind of a problem. We do not expect to be able to prove such things without breaking the function.

One "simple" way to prove this would be a single collision (on short inputs), which in theory could be found by chance. But for finding such, we expect to have to calculate about $2^{256}$ hashes (and store/compare them to the other values) to have a non-neglible probability to find a collision.

For example, if I have one zettabyte of fast accessible storage (which would be more than half of humanity's currently stored data), I can store about $2^{62}$ SHA-512 hashes. The probability that between these is at least one duplicate would be about $2^{-389} \approx 10^{-117}$. If every human (around $2^{33}$ in some years) repeats this experiment about once a week (i.e. $2^6$ times a year) with $2^{62}$ new hashes, humanity each year has a chance of $2^{-351}$ of finding a collision. Assuming that humanity  will work on this for 10 times as long as the universe already existed (i.e. 130 billions of years), we get a chance of $2^{-314} \approx 10^{-94}$. For comparison, the probability that a ticket wins the main prize in the German weekly lottery (6/49) is around $2^{-27}$, so the probability that humanity will ever find a collision (in the scenario outlined above) is lower than the probability of me winning the main prize each week, for 11 weeks in sequence (with one ticket per week).

So we can expect collisions to stay hidden until the end of times.


No, it's not so simple. In particular, you have to be much more precise about what do you mean by combine.
if you want a good example about how to combine insecure things could become secure you can read :
Let's consider the following one-time-signature scheme $\Sigma_1, \Sigma_2$ both which are equal to
https://eprint.iacr.org/2010/446.pdf . with message space $\{0, 1\}^4$.
Remark that these two schemes are proven secure (the fact they are the same is not relevant in the hypothesis you made).
Now let's consider the Signature scheme $\Sigma_3$ over $\{0, 1\}^8$, which is the concatenation of $\Sigma_1$ and $\Sigma_2$. i.e :
$\Sigma_3.\texttt{KeyGen} = \Sigma_1.\texttt{KeyGen}$, and $\Sigma_3.\texttt{Sign} ( sk, m_1 || m_2) =\Sigma_1.\texttt{Sign} (sk, m_1)||\Sigma_2.\texttt{Sign} (sk, m_2)$. $\Sigma_3.\texttt{Verify} ( vk, \sigma_1 || \sigma_2) =\Sigma_1.\texttt{Verify} (vk, \sigma_1)\wedge\Sigma_2.\texttt{Verify} (vk, \sigma_2)$.
Then, if you obtain the signature of $00001111$, you can sign every message in $\{0, 1\}^8$ which contradicts the one-time-unforgeability.QED
To "combine schemes" people are using universable-composability :
https://en.wikipedia.org/wiki/Universal_composability
What is universal composability guaranteeing, specifically? Where does it apply, and where does it not?
But :
1)It's not enough for your schemes to be secure, they have to be UC-secure.
2)You have to be sure your combination is captured by the formalism of UC.
To conclude, it's a little bit like cooking. It's not because two meals are good separately, that combining both would create a good meal.
About the error in your reasoning " Suppose an adversary A is able to break the security of CS by breaking the security of subscheme", you don't have to suppose how the adversary breaks your scheme, when you are doing a security proof.


Why is ethereum not using threshold signatures like dfinity for randomness? What's the drawback?

This post is a little old considering the current conversations going on about the various approaches to generate secure, safe, live and unbiased randomness in Ethereum 2.0. However for a better update on the ongoing conversations, please let me share the latest progress in this discussion.
Ethereum 2.0 is proposing a combination of RANDAO ( biased entropy) + VDF (unbiased entropy) now as a choice for the source of randomness in the beacon chain. Justin Drake has written the following construction in the Ethereum Research forum.

Assume a global clock and split time into contiguous 8-second blocks and 128-slot epochs. Each epoch produces 32 bytes of (biasable) entropy to which correspond 32 bytes of (unbiasable) randomness In a recursive fashion, the beacon chain proposers of epoch (one per slot) are sampled using past randomness for some suitable constant.

A few researchers in the discussion forum have opined that it will have the following advantages over the threshold signature scheme of DFNITY.

The threshold relay scheme from DFNITY stands out as not being
biasable. Unfortunately, the beacon can stall if even a minority (e.g.
15% 1) of honest players go offline.
As indicated by @denett this does not work because the sampling process will weaken your honesty assumption. (Dfinity’s sampling weakens the global 2/3 honesty to 1/2 local honesty.) Sampling is required because the Distributed Key Generation (DKG) scales quadratically with the number of participants, and in practice you can’t get much more than 1,000 participants.
Another thing to consider is that there are two ways in which the
Dfinity beacon can fail. Citing the whitepaper: “We treat the two
failures (predicting and aborting) equally”. By improving liveness you
make the readomness beacon easier to predict.
Finally, the RANDAO + VDF approach allows for arbitrarily low liveness
assumptions. (For example, we could have a 1% liveness assumption by
making the RANDAO epoch longer.)

I had relentless participated in the Starkware Veedo Streak hackathon and used the VDF based Randomness through Beacon contracts deployed in TestNet and MainNet. It looks like the VDF approach is gaining traction in the Ethereum Research community.


rsa_pss_rsae_sha256 is the signature scheme that defines to use of the SHA-256 during the RSA-PSS signature algorithm.
Since Rabin-Signature Scheme, which is the first true signature scheme, the security of the signature is a part of the hashing a message and that enables us to sign arbitrary long messages, too. The rsa_pss_rsae_sha256 will use SHA-256 to hash the message before signing.
The RSA-PSS also needs a hash function to use in its Message Generation Function 1 (MGF1). RSA-PSS defined in RFC 8017 also known as RSASSA-PSS. The SHA-256 will be used in MFG1, too.
TLS_AES_256_GCM_SHA384: AES-GCM doesn't need the SHA-384. The SHA-384 suffix;

In Pre TLS 1.3, the appending hash function SHA-384 defines PRF to use in key derivation and Finished and HMAC when the cipher suites required.

For cipher suites ending with _SHA384, the PRF is the TLS PRF
[RFC5246] with SHA-384 as the hash function.

In TLS 1.3: TLS 1.3 finally defined a KDF; HKDF that replaces PRF and there is no more need for HMAC since all modes are authenticated encryption modes that use CCM, GCM, and Poly1305 message authenticators.
The hash function in the cipher suite definition represents the hash function that is used to hash the handshake messages for the Finished message and HKDF.

What hash is concatenating with the data to be signed in TLS 1.3 CertificateVerify message?

Therefore it is SHA-384


How can we define division operation by using Fully homomorphic encryption

In case some assistance from plaintext holder is available:
(1) choose a random, multiply it with the plaintext and also homomoprhic-encrypt the random;
(2) calculate inverse of the product in clear (no encryption);
(3) multiply encrypted random by the inverse.
This is not exactly division, still it outputs the inverse.


Looking at just EC Public Key parameters, how can you tell if it is invalid?

The general rule for curves is given in;

2003 - Validation of Elliptic Curve Public Keys by Adrian Antipa,Daniel Brown, Alfred Menezes, and René StruikScott Vanstone
They defined a point is valid if

$P \neq \mathcal{O}$
The $x$ and $y$ coordinates of $P$, $x(P),y(P)$ are valid elements of the field.
$P$ satisfies the curve equation - against the twist attack
Check $[n]P = \mathcal{O}$ for prime curves ($h=1$) and check $[h]P \neq \mathcal{O}$ for non-prime curves ($h>1$) where $h$ is the cofactor $h = \#E(k)/n$

if 1,2, and 3 are verified and $h=1$ (i.e. prime curve) then the 4th is already satisfied.


Discussion about the importance of communication complexity for MPC?

It's safe to say that any Cryptographer would want his/her protocol to be implemented and used by the public. Ideas in MPC have been floating around for quite some time now and have been proven to be theoretically sound. The challenge now is to make them efficient enough that it is feasible to use them in practice. In the domain of MPC, sizes of the messages blow up very easily in most protocols as you may have already noticed.

Given that in most situations the network speed is a bottle neck compared to local execution times, it becomes very important to reduce communication complexity if one is serious about implementing the protocol.


In public key cryptography, how many keys are required for secure communication between n parties?

Asymmetric keys come in pairs. The public key of a pair can be used to encrypt data so that only the holder of the private key can decrypt it. If you had one private key, you'd also have exactly one public key that corresponds to it, so your answer of one public key and $n-1$ private keys per person cannot be entirely correct.

The question is somewhat ambiguous, but the answer that is probably expected is $n$ key-pairs, so $2n$ keys altogether. Each person has a single key-pair and knows all the public keys of others' key-pairs. They can encrypt data using any public key to be decrypted using that person's (single) private key.

The number of keys each person knows is about $n$ (one private key and $n-1$ public keys, plus their own public key if you want to count that). However, the total number is not $n*n$, because the public keys are all the same $n$ keys.

However, in the real world you would use hybrid encryption. In addition to the long term key-pairs there would also be a symmetric key for either every message sent or every session (in an interactive protocol like chat). Further, depending on the symmetric primitives used, you could need a second short term key for message authentication/integrity.


Symmetric cipher key size vs number of rounds. Longer key = more secure cipher?

With enough plaintext/ciphertext available (sizably more plaintext than keysize), any cipher can be attacked by trying all the keys; that's brute force. Therefore, for any cipher, too short key ⟹ insecure cipher.

A common symmetric cipher design goal is that the best attack is brute force as limited by key size, within a small factor. Therefore, for a symmetric cipher meeting that design goal, longer key ⟺ more secure cipher.

A common block cipher design goal is that it is as fast as possible while meeting its security level (matching its keysize per the previous goal). Increasing the number of rounds can make a cipher more secure, but does make it slower. Hence, for a cipher design meeting its security and speed design goals, more secure cipher ⟺ more rounds.

There is no definitive method to find the adequate number of rounds. A typical approach is to examine known attacks; try to make conservative estimate of how many rounds they can break for some security level and extrapolate to the desired security level (perhaps much higher); then take the largest number of rounds found for all attacks, and then some as a design margin.

I pass at the Threefish aspect of the question.


PKCS #11 – Deriving a Key where MSB perform encryption and LSB perform CMAC operation?

OK so your problem is the following: You have a secure key and want to / can use it only for AES-ECB. You want to extend the security of this key to derived keying material which deterministically depends on some context material. Finally you need to derive a 32-byte key.

Now, one could use NIST SP800-108 (PDF) as guidance and use the counter-based construction. Here you would take the variable parts of your input, put them into the "fixed part" and run a counter for two blocks. So you would take the 8 variable bytes as the 8 most significant bytes to the ECB input and use the lower 8 bytes as a counter. So your input would be WW XX YY ZZ ww xx yy zz 00 00 00 00 00 00 00 00 and WW XX YY ZZ ww xx yy zz 00 00 00 00 00 00 00 01 and the first output block could be used for the encryption and the second for the MAC of the scheme.


Multivariate cryptography - easily invertible quadratic map

Normally a multivariate scheme has a central private polynomial map that transforms linear multivariate polynomials into non-linear multivariate polys. This map has to be (easily) invertible, this is, it must allow the owner of the map to recover the original input linear polynomials.

Then define the composition of maps found in a scheme based on MPKC as following:

$$P(p_1(x_1,\ldots,x_n),\ldots, p_n(x_1,\ldots,x_n)) = T \circ \mathcal{F} \circ S(x_1,\ldots,x_n) $$

Or in a simplified version where $X$ denotes the $n$ variables on $x$ and $\varphi : \mathbb{F_p^n} \to \mathbb{F_{p^n}}$:

$$P(p_1(X),\ldots, p_n(X) )= P(X) = T \circ \varphi^{-1} \circ \mathcal{F} \circ \varphi \circ S(X) $$

As you may know, the public key $P$ consists of $n$ multivariate non-linear polys so when Bob substitutes for $x$ and sends the output $Y$ of $P$ to Alice, she inverts the composition of maps, then:

$$P^{-1}(p_1(X),\ldots, p_n(X) )=P^{-1}(Y) =S^{-1} \circ \varphi^{-1} \circ \mathcal{F}^{-1} \circ \varphi \circ T^{-1}(Y) $$

Obviously, both transormation matrices $T,S \in F_q^{n\times n}$ must be invertible , and the central private polynomial map must be too in some way (trapdoor or root-finding over $\mathbb{F_q}$), recovering the initial values for $X=(x_1,\ldots,x_n)$ that Bob had chosen.

I recommend you to check the Matsuomoto-Imai MV-scheme since it uses the Frobenious Automorphism over $F_2$. There you can learn the insight behind this kind of schemes and procceed to the original version of HFE wich uses the principles of Mat-Imai.


Why does AES-GCM need a hash/MAC in TLS?

From RFC 5246, section 6.2.3.3: AEAD Ciphers:

  AEAD ciphers take as input a single key, a nonce, a plaintext, and
     "additional data" to be included in the authentication check, as
     described in Section 2.1 of [AEAD].  The key is either the
     client_write_key or the server_write_key.  No MAC key is used.

However in RFC 5246, section 5: HMAC and the Pseudorandom Function:

  In addition, a construction is required to do expansion of secrets
     into blocks of data for the purposes of key generation or validation.
     This pseudorandom function (PRF) takes as input a secret, a seed, and
     an identifying label and produces an output of arbitrary length.

  In this section, we define one PRF, based on HMAC.  This PRF with the
     SHA-256 hash function is used for all cipher suites defined in this
     document and in TLS documents published prior to this document when
     TLS 1.2 is negotiated.  New cipher suites MUST explicitly specify a
     PRF and, in general, SHOULD use the TLS PRF with SHA-256 or a
     stronger standard hash function.

Finally, in  the hash function of the HMAC is also used to authenticate the handshake in the Finished message using the master key; see RFC 5246, section 7.4.9: Finished:

  Hash denotes a Hash of the handshake messages.  For the PRF
        defined in Section 5, the Hash MUST be the Hash used as the basis
        for the PRF.  Any cipher suite which defines a different PRF MUST
        also define the Hash to use in the Finished computation.

So it is used for key derivation and authentication and for a final confirmation that the handshake succeeded, not for generating the MAC over the data messages.


Cryptocurrency serving as hash breaking?

Maybe

First let's say what you got correct:

ASIC is indeed used to mine, and mining is more or less calculating SHA-256 over and over (password hashing schemes use some things to make it somewhat harder for ASICs, but this won't be problem here - miners will use whats best).
If large-enough mining community formed, breakage of passwords could be eased.

However, there would be some problems that could prevent acceptability of such cryptocurrency:

It won't be possible to make it really without knowledge of miners, or at least some suspicions: To claim that you found block X, you would need to publish what password it was. It would be highly suspicious that some solution would be "Password123" "admin1" etc.
You would need database of passwords to break. Normally, this is done by some kind of mathematical rule. You instead would publish a large database and claim it is random. This again would be suspicious. And if you allowed yourself to add more hashes to database, then it would be suspicious, as you had a way to easily mine any amount of this cryptocurrency for yourself (you can generate password, upload it and then immediately solve it yourself - you can however put that aside when you pay for blocks).

So in the end, it doesn't look that easy, but if people somehow didn't realize these red flags, it should be fairly easy to do (not including trust problems - only one cryptocurrency is widely-accepted so far - bitcoin).
Also, if some password was really strong, whole bitcoin mining processing power won't help you - it just will be far too hard.


Is it secure to use the hash of key as the IV in AES encryption?

No, it is not secure.

From NIST 800-38:

The OFB mode requires a unique IV for every message that is ever encrypted
under the given key. If, contrary to this requirement, the same IV is used
for the encryption of more than one message, then the confidentiality of
those messages may be compromised

Given your description, you are apparently safe, because at any one time you have one file only.

However:

A malicious user may store away an earlier version of the file and do a comparison after a change and learn which bits flipped in the first block where that happened.
In the future, you may add a second file and not remember the rule above.

A unique (not necessarily truly random) IV per message is still recommended.


Modular Reduction of polynomials in GF(2^m)

I don't know if this can help you, but did you know if in Binary Arithmetic, you have: $f(z)=z^m+r(z)$; then $z^m =f(z)+r(z)$.
NB: The addition here represents the bitwise XOR, that you can easily represent in hardware by appropriate gates.
Then Let's continue by examining the reduction algorithm you show us:
$c(z)=c_{2.m-2}.z^{2.m-2}+c_{2.m-1}.z^{2.m-1}+\cdots+c_{m}.z^{m}+c_{m-1}.z^{m-1}+\cdots+c_1.z+c_0$
We factorize by $z^m$; then, we obtain:
$c(z)=(c_{2.m-2}.z^{m-2}+c_{2.m-1}.z^{m-1}+\cdots+c_{m}).z^{m}+c_{m-1}.z^{m-1}+\cdots+c_1.z+c_0$
And replacing $z^m=f(z)+r(z)$ and performing the reduction mod f(z): the remaining is:
$c(z)=(c_{2.m-2}.z^{m-2}+c_{2.m-1}.z^{m-1}+\cdots+c_{m}).r(z)+c_{m-1}.z^{m-1}+\cdots+c_1.z+c_0$
Which can be computed, with the precomputed table!

Another interpretation of $r(z)$ from $z^m =1.f(z)+r(z)$ shows that $r(z)$ is the remainder of the division of $z^m$ by  $f(z)$ while the quotient is the constant polynomial 1.


PKCS12 password of container and private key

Now that the Qs have been clarified (and yes this isn't really about cryptography, and would be more appropriate on security.SX = application of crypto in systems or superuser = use of programs including security programs like OpenSSL or maybe even stackoverflow)

  ... Given the example ... 1. Is it correct that EXPPW is the p12 container password and KEYPW is the pass phrase to protect the private key?

No. KEYPW was the passphrase on the PEM-format input file. If the input privatekey file is unencrypted (which OpenSSL supports, although it in many situations it is insecure and thus a Bad Idea) the input password is not even prompted for. It is not used in the P12; only EXPPW is used for the P12.

  Is it possible to get the unencrypted private key with only EXPPW? In other words, is KEYPW not used inside the p12 container?

Yes. That's exactly what your openssl pkcs12 -nodes (with EXPPW) does. (Again OpenSSL supports it, but the caveat above about using an unencrypted privatekey file applies.)

  If the private key is stored encrypted inside the p12 using EXPPW, why does openssl pkcs12  -info -in test.p12 not accept a new pass phrase for outputting the new encrypted private key? If you don't use the original KEYPW it fails with Error outputting keys and certificates

Try again. It should work (to use a different password on the output of the 'parse') and does for me. Note the new password must be at least 4 characters, a limit that OpenSSL does not enforce in other places, although even 4 is not nearly enough for actual security. (That area -- length and other characteristics of a good password -- is ontopic for crypto.SX and has been discussed numerous times at length.)

  Is it possible to protect the whole p12 container with password X and the private key with password Y? So that if you know X, you can still get the public certificate yet you can't get the private key?

Yes, or nearly. There are actually three operations normally done:

the whole P12 is MACed using a password,
the 'shrouded keybag' is encrypted using a password, and usually a strong or at least strong-ish algorithm like 3DES
the 'cert bag' is (separately) encrypted using a password, and usually a deliberately weak algorithm namely RC2-40

(The latter two are shown by the -info option on the parse subcommand, although you
omitted part from your post.)

OpenSSL commandline does not support using different passwords for 2 and 3, but it does support changing the algorithm(s) and in particular it supports making the certbag unencrypted which allows access to it without the password, using -certpbe NONE. This is a crossdupe of https://superuser.com/questions/1507936/openssl-encrypts-public-key-after-conversion-to-pfx . Commandline does support the -twopass option to make the MAC password for 1 different from 3 (or 2 and 3), or you can simply ignore the password for 1 on reading using -nomacver.

Caveat: software other than OpenSSL may not handle PKCS12 files with other than the usual algorithm settings and a single password.

  my goal is to understand the pkcs12 structure.

You might want to look directly at the file structure with asn1parse, rather than the interpretation given by the pkcs12 command. See an example at
https://stackoverflow.com/questions/51242721/openssl-debugging-how-to-dump-intermediate-asn-1-inside-openssl


“Well-typed” relates to a type system. This is a general concept in computer science, the usage here is an example of the general concept and is not specific to cryptography. “Well-typed” does not refer to a cryptographic protocol, but to a theory (model) in which a protocol is described.

A type system is a way to assign properties (called types) to components of programs. For example, a type system might make stipulations like the following:

The program fragment int x; declares a variable called x whose type is “integer”.
Integer literals such as 3 and 42 are expressions of the type “integer”.
String literals such as "hello" and "42" are expressions of the type “string”.
If x is a variable with the type “integer”, then x is an expression of the type “integer”.
If E_1 and E_2 are expressions of the type “integer”, then E_1 + E_2 is an expression of the type “integer”.
If x is a variable which has the type “integer” and E is an expression of the type “integer”, then x := E is a valid (well-typed) program. If E does not have the type “integer”, then x := E is an invalid (ill-typed) program.

The ultimate goal of most type systems is to declare that certain programs are well-typed, i.e. that they're correct (with respect to this type system). They achieve this by assigning types to program fragments, to variables, to functions, etc. and detecting conflicts (e.g. trying to assign a string value to an integer variable, trying to apply a function to an argument which is not of a type that it can handle). Most programming languages have a type system, such that ill-typed programs are rejected, either at run time (dynamic typing) or at compile time (static typing).

Type systems can encompass a wide variety of properties. The most common class of property has to do with the structure of data, such as:

“this is an integer“
“this is an integer modulo $2^{32}$ using the smallest nonnegative representative”
“this is a list of integers”
“this is a function that takes an integer as argument and returns an integer”

But type systems can describe arbitrarily complex properties. That makes it harder to decide whether a program has a correct type, but makes the type system provide more useful information. Here are some example properties that a sufficiently sophisticated type system might model:

“this is a prime integer”
“this is a list of integers whose length is the value of the expression x + y”
“this is a terminating function that takes an integer as argument and returns an integer”
“this function $f$ takes two arguments $(p,s)$ and returns two values $(p',s')$, such that the value of $p'$ depends only on $p$ and not on $s$”

In that last example, you can see a security property emerging: if we think of $p$ and $p'$ as public values and $s$ and $s'$ as secret values, the property states that public values do not depend on secret values. In other words, the function $f$ preserves the confidentiality of secret values.

Soundness relates a type system with execution rules (an execution semantics) for the programming language. It is a formal property that states that if a program is well-typed, then all runtime states of the program (as modeled in the semantics) are also well-typed. Most type systems are designed to be sound for the usual semantics of the language. This way, information given by the type system about the program translates into information about the program's execution.

The paper that you're reading defines a type system for processes (describing communication protocols) that classifies messages according to which principals know their content. The execution rules describe the propagation of messages. The soundness of the type system means that the initial classification of who knows what is preserved during the execution of the protocol. This holds for well-typed processes, i.e. processes for which the classification (typing) rules give a result. Thus processes that are classified as valid by the type system will not reveal secret data during their execution.


The main pitfall is possibly thinking that it provides authentication.

The result is still a public key scheme.

It won't help to include the IV in the associated data, since

that is already covered by the authenticated part of AEAD.

Including the RSA-encrypted symmetric key in the associated data would help by making the

resulting hybrid encryption CCA2 secure even if the core public key scheme is only RCCA secure.

RCCA: Relaxing Chosen-Ciphertext Security


Is XSalsa20-Poly1305-SIV a reasonable choice for nonce-misuse-resistant authenticated encryption?

This can be a secure construction, if by MAC you mean universal hash family, like Poly1305.  Call this hash family $H_r$ and the short pseudorandom function family $F_k$.  Rough justification for why this is secure:

The function $m \mapsto F_k(H_r(m))$ is a long-input, short-output PRF.
A good PRF makes a good MAC.
A good PRF has birthday-bounded collision probability, so the probability of nonce reuse for the stream cipher is small.

In a bit more detail: Let $\varepsilon_F$ be a bound on the PRF-distinguisher advantage of any algorithm making $q$ queries against $F$, and let $\varepsilon_H$ be a bound on the collision probability $\Pr[H_r(x) = H_r(y)]$ of $H$ for any $x \ne y$ and uniform random $r$.

The PRF-distinguisher advantage for a $q$-query attack against $m \mapsto F_k(H_r(m))$ is bounded by $\varepsilon_F + \binom{q}{2} \varepsilon_H$ (proof).
For fixed-size keys, the collision probability $\varepsilon_H$ grows linearly with the maximum message length.  So this figures into the concrete numbers.
The probability of a synthetic nonce collision (i.e., a collision in $m \mapsto F_k(H_r(m))$) is higher than the probability of a collision in $H$, because either a collision in $H$ or a collision in $F$ means there's a nonce collision—whether this matters depends on how large the output of $F$ is, and in particular on the birthday bound for $F$ which may be much smaller than the collision probability of $H$.

There's some practical details to work out.

Here $q$ represents the number of messages that you are willing to send or receive in your application.  For example, if $\varepsilon \approx 2^{-100}$, the bound above means nothing unless your application's total bandwidth is limited to $q \lll 2^{50}$ messages.  (And you don't want to mess with collisions in $H$.)

Is the Poly1305 collision probability bound $\varepsilon_{\operatorname{Poly1305}} = 8\ell/2^{106}$ for $16\ell$-byte messages comfortable enough for trillions of megabyte-long messages?  Maybe it is, maybe it isn't—for now I leave it as an exercise for the reader to compute specific bounds for specific data volumes.  (See a similar table for AES-GCM.)

What should you choose for $F_k$?  If you're already using XSalsa20, the obvious choice is XSalsa20 truncated to 128 bits or similar.  Of course, you'll have to quantify the probability of a collision between the XSalsa20 nonce used for encryption and the XSalsa20 input from $H$.  But maybe you can do better than multiple the HSalsa20 invocations this would imply, each of which adds overhead to small packets.  Maybe you should use a 192-bit or 256-bit hash $H$, and a 192-bit authentication tag, so that the probability of a synthetic nonce collision is negligible even for extremely large volumes of data.


Secure multiparty computation guarantees the nothing whatsoever is revealed by the process of computation. It does not say anything about the function. As you correctly point out, there are some functions that reveal a lot and shouldn't be computed, but this analysis is quite out of the scope of secure computation. The question of whether it's "recommended" depends on the application and the choices you may or may not have. You may, for example, want to use secure computation to compute a differentially private version of the function.


As @Cryptostatis commented, Kerckoff's principle dictates that we must consider that the adversary knows the function.

More fundamentally, although the word “adversary” naturally suggests it must be a sentient being such as a human, remember that an adversary is in fact just an algorithm. The algorithm $A$ which on input $x$ returns $x-123$ inverts your function with probability $1$, demonstrating that your function is not one-way. How a human attacker would actually be able to "come up" with this algorithm is irrelevant, what matters is that such an algorithm exists.


Diffie Hellman is not dependent on the difficulty of factorisation of large numbers (sort of*).

It relies on the fact that there is no efficient algorithm know to the human race as of today that can efficiently deduce the discrete logarithm of a number. That is given an element $y \in G$ where G is a cyclic group of prime order $q$ , it is not computationally feasible to find a number $x \in Z^*_q$ such that $y = g^x$.

They key point here is that the order of the group needs to be a prime number. This means that the group $Z^*_p$ is not secure for any prime $p$since its order is obviously not prime.

To deal with this trouble one can choose a prime $p$ such that $p= kq + 1$. This means that there exists a unique subgroup (called schnorr group) of $Z^*_p$ of order $q$ since there exists exactly one subgroup for each divisor of $φ(p) = p-1$.

To find a generator for that group is trivial. Choose a random value $1 <h < p$ such that $h^r \mod{p} \neq 1$. If you find such a number then this inequality means that the order of $h$ is greater than $r$. However the only possible order greater than $r$ is $q$. As a result $h$ has order $q$ and can generate a secure subgroup of $Z^*_p$. If $h^r \mod{p} = 1$ then simply generate another random $h$ and try again until you find a generator.

*One can show that if the order of the group has only small prime divisors then the discrete logarithm problem is much easier to solve than other groups. However by selecting a subgroup of a large prime order as we did above by selecting $p= kq + 1$ means that the subgroup we are generating only has one large factor (itself), which in turn means that you need not worry of these factorisation attacks.


The answer may depend on your exact definitions of "homomorphic" and "malleable", but I'll give it a shot.

Basically, homomorphic encryption denotes that, given encryptions $E_k(x)$ and $E_k(y)$ of some values $x$ and $y$, it is possible to obtain an encryption of $x\ast y$ under $k$ from $E_k(x)$ and $E_k(y)$, where $\ast$ is some binary operation, without knowledge of the key $k$. Typically, $\ast$ is the usual addition or multiplication on (bounded) integers, but the attack actually works for almost arbitrary operations (namely, there must be a pair $(x,y)$ such that $x\ast y\notin\{x,y\}$): Assume that an attacker knows $x$ and $y$ along with their encryptions $E_k(x)$ and $E_k(y)$. He may then compute $E_k(x)\mathbin{\hat\ast}E_k(y)$, where $\hat\ast$ denotes the "lifted" version of $\ast$, to obtain a ciphertext $\zeta$. By specification, $\zeta$ decrypts to $x\ast y$, which was assumed different from both $x$ and $y$. Hence, the attacker has obtained a ciphertext ($\zeta$) corresponding to a plaintext ($x\ast y$) he knows but whose ciphertext he has not observed before.

Therefore, any homomorphic encryption scheme is malleable.


Which one is correct probability formula for the same master secret value in identity-based encryption

Both are correct, you've just made an error calculating it.

Here is a simplification from my answer here:

$$\begin{eqnarray}
p(n) & = & 1 - \frac{q!}{q^n\left(q-n\right)!}\\
& = & 1 - \frac{\prod^q_{i=q-n+1}i}{q^n}\\
& = & 1 - \prod^q_{i=q-n+1}\frac{i}{q}
\end{eqnarray}$$

So,

$$\begin{eqnarray}
p(2) & = & 1 - \prod^q_{i=q-2+1}\frac{i}{q} \\
 & = & 1 - \prod^q_{i=q-1}\frac{i}{q} \\
 & = & 1 - \frac{q-1}{q}\cdot \frac{q}{q} \\
 & = & 1 - \frac{q-1}{q} \\
 & = & 1 - (\frac{q}{q} - \frac{1}{q}) \\
 & = & \frac{1}{q} \approx 0.
\end{eqnarray}$$