Can one use a reversible hash algorithm as a compression function? As we know any text, file, byte...in SHA-256 output will be returned as 64 hex length. Is it possible to create cryptography that can do the same thing as SHA-256 but can be reversed, so if we have the output of 64 length of hex number, we can reverse it and get started input like "i love programming"? This will be soo cool way to compress huge text. Is it possible?

Strictly speaking, all hash functions are compressing since the output can be smaller than the input, but I imagine you're asking about compressing data that can later be losslessly decompressed.
This is impossible due to the pigeonhole principle. The fact that the fixed output space of a hash algorithm is smaller than the input space means that there will always be multiple possible inputs for the same output. Even if you could find a preimage (i.e. "reverse" the hash), you would not know if it is the original preimage or just a preimage. If the input size was sufficiently small (smaller than the hash) then it may be possible since you can discard larger preimages and only keep the very finite number of small ones that make sense (e.g. only valid ASCII strings), but then it's not compression.
As an extreme example, imagine a "hash function" with a trivial preimage attack: a 1-bit CRC with the polynomial x + 1 (i.e. an even parity bit). If I give you the output of this function and the output is 1, you will have absolutely no idea what the input was. You can compute an input, but you can't find the input. For a 1-bit hash, half of all possible inputs in the input space map to that same output!

This impossibility is the basis of the popular joke from Schneier Facts:

For Bruce Schneier, SHA-1 is merely a compression algorithm.


If you encrypt an image (AES), is it still an image and can you view it? Can you encrypt an image (with AES) such that you can open it as a png/jpeg?

If you aim to show the effect of the encryption, meaning a scrabled image you have to encrypt only the "image data" and keep the file structure unchaned. A simple tutorial can be found here: https://blog.filippo.io/the-ecb-penguin/.
Author uses ppm files, but you can easily adapt to your file format.

# First convert the Tux to PPM with Gimp
# Then take the header apart
head -n 4 Tux.ppm > header.txt
tail -n +5 Tux.ppm > body.bin
# Then encrypt with ECB (experiment with some different keys)
openssl enc -aes-128-ecb -nosalt -pass pass:"ANNA" -in body.bin -out body.ecb.bin
# And finally put the result together and convert to some better format with Gimp
cat header.txt body.ecb.bin > Tux.ecb.ppm

Here’s an example (using the key “ECB”):

You actually can. You actually can do even more: encrypt a file format into an other. You need to play with key and IV to get that the message input is "well" transformed by the encryption. If you control the key and the IV and the initial and final file you ave enough freedom to achieve your aim.
Ange Albertini made a proof of concept.
Ablog post explaining the idea is available here: http://blog.fortinet.com/post/angecryption-at-insomni-hack

Roughly you want that the encryption of the file header (with the magic number, identifying the file type) is encrypted into a valid file header. Then you can play with data chunks and segment to get one image or the other.

The video explanation: https://www.youtube.com/watch?v=wbHkVZfCNuE

An example: https://code.google.com/p/corkami/source/detail?r=1906

Some slides: https://www.blackhat.com/docs/eu-14/materials/eu-14-Apvrille-Hide-Android-Applications-In-Images.pdf (not the same as the op asked but the idea is the very same)


ZKP: Proving knowledge of a variable length hash preimage I am currently trying to implement a proof of knowledge of the preimage to a public hash image using different zkp system implementations.

There are a lot of examples that do exactly this (see this question for some further reference). But: All of these have a fixed input size to the hash function (often two times 256-bits to do merkle tree proofs). Now while this is very convenient for examples, I would like to allow the preimage to be variable in length.

I have some questions on this:

Is a variable length input possible in zkSNARKs, where the verifier and prover keys have to be calculated beforehand? Can I create a prover key that permits arbitrary input lengths? To my understanding this is not possible and the prover would have to reveal the preimage length before the trusted setup.
In Bulletproofs I have to split up the preimage into 32 byte chunks, represent them as scalars and commit to each. Is there a way to avoid a linear amount of commitments to the size of the preimage?

(I'm writing this all with Bulletproofs in the back of my head)

Variable length inputs

As far as I know, it's not possible to achieve literal variable/secret-length inputs, except if I'm allowed to tweak your definition a bit. If you would allow input lengths up to a certain amount $n_{max}$, then you can vary the length below it. To achieve this, you can for example always commit to $n_{max}$ inputs, where you set the first $n$ inputs to your real inputs $v_1,\dots,v_n$, and the last $n_{max} - n$ to a semantically meaningless input. Then your proof protocol can be:

$$ \bigvee_{i=1}^{n_{max}} \text{statement when length = }i\text{ using } \{v_1,\dots,v_i\} $$

I.e., you write a proof that is the disjunction of the statements for proofs of length $i$. Of course, this makes your statement more complex, but a system like Bulletproofs compresses it well. You would need $n_{max}-1$ additional multipliers for the disjunction, thus if your statement for length $i$ needs $\text{poly}(i)$ multipliers, the total statement length would be something like $$\mathcal{O}(\log(n_{max}\cdot \text{poly}(n_{max}))) = \mathcal{O}(\log(n_{max}) + \log(\text{poly}(n_{max}))),$$ which gives you a constant overhead.

Constant-size commitments

Contrary to popular believe, Bulletproof witnesses don't necessarily need to be input commitments. The Bulletproofs paper actually does two main things to the original 2016 protocol of Bootle et al: reduce the complexity of the inner-product argument, and add support for Pedersen commitments. The latter just means that you don't have to implement Pedersen commitments inside the circuit (which would hurt the performance a lot). So, the way to avoid chunking and committing, is to avoid committing completely. After all, you could see your hash as a (imperfectly hiding) commitment already.

If you want to see how this works inside the main Bulletproofs equation ($W_L\cdot\vec a_L + W_R\cdot \vec a_R + W_O\cdot \vec a_O = W_V\cdot \vec v + \vec c$), notice that $\vec v$ is not the whole witness; $\vec a_L, \vec a_R \text{ and } \vec a_O$ are also part of the witness.

If you want an example of how this could work in practice, have a look at the excellent Rust-implementation of Bulletproofs arithmetic circuits. Their r1cs-integrated-range-proof test for example, decomposes a witness number in 64 different bit-variables, constrains the bits and only then binds it to the commitment. You could perfectly modify that code to bind the bits to a hash input gadget, and constrain the output of the hash gadget to your hash value.

This all of course requires knowledge of the input length, but the trick from above can then be used to hide the length up to a certain bound.

I hope this helps your case!


Is there a method of encryption where you can't work out the key even with the encrypted and decrypted message? I'm looking for a method of encryption that fulfills the following parameters:
To still be able to display a result even if decrypted with the wrong key.
If the encrypted and decrypted message is found, the key cannot be worked out.
Forgive me if I'm being stupid but I'm new to this area!
Thanks

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.


Is it possible to find a Mersenne Twister seed given only the first output? Suppose I have a Mersenne Twister seeded with some unknown value, and I’ve been given the first output. Given only this first output, and no other information, is it possible to derive the unknown seed?

I feel like the answer is no, but I want to be sure I’m not missing something.

Context: I’m looking at Matasano challenge 22. You seed an MT19937 RNG with the current Unix timestamp, wait a random number of seconds (40 ≤ T ≤ 1000), then get the first output from the RNG. The challenge is to find the original seed.

I started by trying to reverse the output process, essentially inverting the inner workings of the twister. But after some effort, it seems like doing so would be incredibly hard and involve lots of linear algebra – if indeed it’s even possible.

I feel like it’s probably impossible, but I’m not completely sure.

I suspect the intended solution is to take an entirely different approach, and

   use the fact that you have a rough idea of when it was seeded, and so a range for the seed values. If I know it was seeded in the last hour, there are only a few thousand possible values. I can check the first output for each possible seed value, and compare to the actual result.

(Spoiler block for anybody working through the Matasano challenges themselves)

But I’m curious whether my original approach would work. Is it impossible to go from the first output to the seed, or is there some trick that I’m missing?

Is it impossible to go from the first output to the seed, or is there some trick that I’m missing?

Yes, it is impossible, but not because the algorithm could not be reversed. If you had the whole state, you could go back to find the seed, but you need at least 624 32-bit outputs before you can uniquely find the state of MT19937 (due to the $k$-distribution property).

As @yyyyyyy mentions in the comments, seeding with a timestamp cannot produce all the possible states. However, due to collisions there will not always be a single 32-bit state that produces a particular 32-bit value as the first output, so even if you could work through the math to invert to the seed, you might not find a unique timestamp that way.

Your spoilered approach is much better.


Seeking clarification of OTP & MAC discussion I refer to the question for-a-one-time-pad-which-mac-method-is-information-theoretically-secure, and specifically the exchange between lightspeeder & kasperd.

I've found the discussion a little advanced, but can I infer that:-

Any hash can be used for message authentication, including MD5?
The MAC tag must be encrypted with the OTP?
The size of the hash only affects the probability of a successful forgery?
The inherent security proof of a OTP is maintained even by appending a MAC to the plain text, then encrypting?

Can anyone confirm (hopefully) my interpretation?

Taken in order:

  Any hash can be used for message authentication, including MD5?

No.  A message authentication code or tag is generated by using a keyed cryptographic hash function.  Raw MD5 is an [unkeyed] cryptographic hash function.  One of the goals of this type of primitive is that it should not be feasible to create a valid tag for a message without the key.  If you have no key, as with MD5, it's easy for anyone to compute a valid hash of the message. MD5 might be used internally within a MAC algorithm, but not as a MAC algorithm.

  The MAC tag must be encrypted with the OTP?

No.  In fact, you can see in the 2nd to last paragraph of kasperd's answer that when an appropriate (information theoretically secure) construction is chosen, it does not matter if the tag is encrypted with the OTP or not, though there is some additional cost for encrypting it with the OTP with no corresponding security gain.

  The size of the hash only affects the probability of a successful forgery?

Yes, that is the primary goal of the tag, which is the output of the MAC algorithm.

  The inherent security proof of a OTP is maintained even by appending a MAC to the plain text, then encrypting?

This is true if the MAC algorithm provides information theoretic security, such as Wegman-Carter authetication, as kasperd pointed out in his answer.  This is not true for other MACs, such as HMAC which was the original object of the question.


Is ECC over real numbers possible? Many elliptic-curve cryptosystems today use GF(p) or GF(2^m).
What if, say, we use big floating numbers with the classical point addition formulas - is a cryptosystem possible to build on that?

Summary: ECC over real numbers can be made to work, including for toy-sized security parameters and real numbers arithmetic as directly supported by typical CPUs and spreadsheets. But much more precision would be needed for private keys large enough to hope for security. That would be inefficient if secure; and perhaps just insecure.

We can mathematically define the infinite group of points on an elliptic curve on the continuous plane, e.g. with Cartesian representation in $\mathbb R^2$ under point addition (with an additional neutral element). We can define scalar multiplication on that. For any integers $k_A$ and $k_B$ and any point $g$ on the curve, it mathematically holds that $k_A\times(k_B\times g)=k_B\times(k_A\times g)$, as used by ECDH and ECIES.

However there is at least one huge problem facing a cryptosystem based on that line of thought: when using Floating Point to represent reals in $\mathbb R$ that are coordinates on the curve, $k_A\times(k_B\times g)=k_B\times(k_A\times g)$ no longer exactly holds due to round-off error, and that worsens with larger $k_A$ and $k_B$ for reasons of numerical stability.

The underlying problems are that

When using FP arithmetic, each point addition on the curve involves (among other operations) addition, and the FP version of that is not associative; otherwise said, there are exceptions, occasionally quite notable, to $(x+y)+z=x+(y+z)$.
Independent of FP arithmetic, the effect of a small variation of $g$ on $k\times g$ grows with $k$ (somewhat like the effect of a small variation of $x\in\mathbb R$ on $x^k$ grows about linearly with $k$).

With the $k_j$ in the hundreds of bits, there are many hundreds chained point additions in the computations of $k_A\times(k_B\times g)$ and $k_B\times(k_A\times g)$, so that discrepancies between the two values at each step (due to 1) will have many chances to appear and grow (due to 2) to the point where the results are extremely different (much like for evaluation of the logistic map in the chaotic region for large number of iterations).

Increasing FP precision will help, but it is hard to tell exactly how precise a FP representation of coordinates on the curve we shall use for $g$, and intermediary values including $k_A\times g$ and $k_B\times g$, so that $k_A\times(k_B\times g)$ and $k_B\times(k_A\times g)$ coincide well-enough to derive a shared secret.
Note: the practical issue of defining that well-enough and turning it into a consistent shared secret is non-trivial, but it can be solved by rounding to agreed-upon number of bits, combined with appropriate error correction like: detecting disagreement and, should that occur, retrying or trying nearby values; sending a small public additive correction, or other form of Forward Error Correction.

Floating Point arithmetic with direct hardware support on modern CPUs (that is typically at most 80-bit with 64-bit mantissa, or 64-bit with 53-bit mantissa) will not be precise enough that results coincide well-enough for realistic $k_j$; but it can be made to work most often for $k_j$ and shared key of a few bits. Making large shared keys from small ones is easy (just make multiple passes and concatenate); but I doubt we could make large private/public key pairs from small ones.

Arbitrary-precision FP arithmetic is possible, but inneficient. Typically it uses arbitrary-precision integer arithmetic, so we would be back to this.

Note: there are other serious numerical issues, including the risk of overflow, and how to extract the shared key from potentially very large coordinates.

I do not know if there is an additional issue with security.

The problem of solving for integer $k$ given $k\times g$ and $g$ (which breaks ECDH) might not be as hard with coordinates of givens in $\mathbb R$ (as approximated by FP arithmetic) as it is for coordinates in $GF(p)$ or $GF(2^m)$. As an illustration that it can't be ruled out summarily, solving for $k$ given $x^k$ and $x$ is believed hard with givens in $GF(p)$ for appropriate choice of $p$, but is easy with givens in $\mathbb R$ (as approximated by FP arithmetic, and assuming no overflow) because $k=\log(x^k)/\log(x)$ (computed with rounding to the nearest for FP).

Also, there are conflicting interactions between the precision used and security:

Too low a precision on $g$ or/and $k\times g$ restricts the size of $k$ for a unique solution $k$, and short $k$ makes finding $k$ easy; there's no solution to that in sight beyond increasing precision.
Overly increasing precision for $k\times g$ (for constant range of $k$) could conceivably make the problem of finding $k$ easier, as we are getting more information about $k$ from low-order bits/digits of $k\times g$.


ChaCha20 immune to timing attacks What are the reasons because of which ChaCha20 is immune to timing attacks ? Also why is not AES immune to timing attacks?

The obvious way of implementing ChaCha20 involves nothing but additions, fixed rotations, and XORs.  All of these are constant time, so the obvious way of implementing ChaCha20 is secure against timing attacks.  The main way that ChaCha20 is made faster -- SIMD -- does not change this.

On the other hand, the obvious way of implementing AES uses table lookups for the S-boxes.  These are not constant time because of caching.  Avoiding this requires either:

Naive approaches with massive performance penalties.
A technique called bitslicing.  This uses the unlimited parallelism available in CTR mode to emulate a hardware AES implementation, but operating on many bits in parallel.  This only works in CTR mode (because other modes don't have the requisite parallelism) and is not easy to implement.


Is there a simple hash function that one can compute without a computer? I am looking for a hash function that is computable by hand (in reasonable time). The function should be at least a little bit secure: There should be no trivial way to find a collision (by hand). For instance, a simple cross-sum is not meeting this criteria since one can easily construct a number with the same hash than another.

Is there a (simple) function? I am interested in this for a presentation about commitment schemes in my CS class at school.

Well, depending on what's reasonable and what you can compute reliably by hand, you MIGHT be able to compute modular exponents in a moderate-size group (like $Z_n$ for moderate $n$).  Exponentiation via repeated squaring is doable I think.

Probably more practical would be a MD5-like ad hoc confusion-diffusion primitive.  You'd need to make the input large enough to make exhaustive search impractical by hand (32 bits should do it I would think?) and then make a round-function that was simple enough to compute by hand but had empirically-good collision-resistance.  Finally apply Merkle-Damgaard for a "few" rounds.

I would expect this to work reasonable well with a random crypto classmate.  If you're playing against Adi Shamir, you're probably screwed.

Edit: For in-person commitment schemes, you can get rid of hash functions altogether.  Just write a string of random bits on a folded paper and hand it to your partner to commit those bits.  But the more interesting scenario is doing this through a prison wall, over a phone, or over the internet... then you really need something mathematical.

Let's take the prison-wall example: you want to commit to another inmate some integer $x$ and you have no computational resources but can communicate with tapping (no paper).  Here's what I would do: pick a 64-bit number $x$ that you want to commit.  Make sure you can't factor it (it might be prime, but verifying primality is going to be tedious by hand).  Then choose another, larger, 64-bit number $y$ that is also hard to factor by hand.

Now compute $p=xy$ (easy) and send $p$ to your buddy.  If $x$ and $y$ were both hard to factor, $p$ is as well, so he can't extract $x$ or $y$ from $p$.  Now for the reveal, you send $x$ and $y$; he verifies that $p = xy$ and that $x$ is the smaller integer.

It's important that both are 64-bits (or both the same size) to prevent you from changing to $x'$ after the commit where $p = x' (k y)$.  This doesn't happen if $x$ and $y$ are prime, of course, but large primes aren't easy to generate by hand.


Does a hash function in chaining mode or in counter mode make a better pseudo-random number generator? I have two pseudorandom generators:

$f_1$ takes a random seed $l_0||r_0$ $\in \{0,1\}^{160}$ as input and outputs $r_1||r_2|| \dots ||r_k$, where $l_i||r_i = \operatorname{SHA-1}(l_{i-1}||r_{i-1})$ and $l_i, r_i \in \{0,1\}^{80}$
$f_2$ takes a random seed $s \in \{0,1\}^{160}$ as input and outputs $t_1||t_2|| \dots ||t_{k/2}$, where $t_i = \operatorname{SHA-1}(s||s_i)$, where $s_i \in \{0,1\}^{80}$ is the binary representation of $i$.

($l||r$ denotes the concatenation of $l$ and $r$.)

I'm thinking that $f_1$ seems better in a "random" perspective because for each step we use the output from the previous step as input, whereas in $f_2$ we use the same seed together with the position, which seems very predictable. But maybe that doesn't matter since we hash it? Then I would prefer $f_2$ because we get a longer output (more pseudorandomness) from the same amount of random input.

Am I on the right track or have I totally missed something?

In cryptography, the standard we use when evaluating a cryptographically secure random number generator is "how much effort does it take to distinguish this generator from a truly random source".

By this criteria, we find that, as specified, your $f_2$ is considerably better than your $f_1$.

With $f_1$, we can distinguish the generator from random (and predict future outputs) by selecting a $r_i$, iterating through the possible values of $l_i$, and find if there is a $l_i$ value that successfully predicts the $r_{i+1}, r_{i+2}, \ldots$ values.  There are $2^{80}$ possible $l_i$ values, and hence this rng can be distinguished with approximately $2^{80}$ SHA-1 evaluations.

In contrast, with $f_2$, where is no known weakness in SHA1 where, given a long series of hashes of related equal-length plaintexts, we can deduce anything about the plaintexts (or, indeed, whether the hashes were from related plaintexts).  Hence, the best approach would be to iterate through the possible $s$ values, and try to find one that correctly predicts the outputs.  There are $2^{160}$ possible $s$ values, hence this approach would take approximately $2^{160}$ SHA-1 evaluations.

In addition, I would notice a practical advantage to $f_2$; it performs one SHA-1 evaluation for every 160 bits of output, while $f_1$ performs one SHA-1 evaluation for every 80 bits of output.  This means that, practically speaking, $f_2$ is likely to be twice as efficient.

On the other hand, while $f_2$ is distinctly better, I couldn't really recommend either; I would suggest you look at the NIST 800-90 random number generators, and in particular, the CTR_DRBG - this would be rather more efficient then either of your approaches.


SHA256 HMAC brute force with chosen plaintext attacks This is a follow up to Is It Possible To Reconstruct a Cryptographic Hash's Key

I am using a SHA-256 HMAC function on a single-word input: sha256hmac(privatekey,word) = output. The private key length is 128 bits, it does not change. The "word" is literally one short word.

Assuming an attacker knows "word" and "output" for multiple words (e.g., dog = "dsfwrw3r3r323211", cat = "3erwerwetwewer"):

Is it significantly easier for an attacker to identify the private key by brute force with the above word/output pairs, as compared to a situation where they do not have those pairs?
Is this brute force vulnerability (with word/output pair knowledge) an actual security concern?

I'll assume that "sha256hmac" designates HMAC using SHA-256 as the underlying hash function.

HMAC is used for its intended usage: the first parameter privatekey is a key, I assume random and secret, of fair length (128-bit); the second parameter word is a (possibly public) message; output is a (possibly public) cryptogram. Observing any number of (word, output) pairs, even for word of an adversary's choice, will not enable to recover privatekey or otherwise compute new result.

Its hard to tell if having (word, output) pairs makes the task significantly easier: it goes from impossible with no pair at all, to infeasible using any foreseeable technology with some pairs (unless we consider quantum computers practically applicable to cryptography as foreseeable, which requires some dose of optimism).

With one privatekey of 128-bit, I think we are good against brute force for two decades, with fair confidence. If there was billions privatekey and the adversary could obtain output for the same word for each of these privatekey, we would NOT be quite that safe with the 128-bit key size (the adversary has a remotely feasible task of finding one privatekey), and we would need more bits: 192 are fine, 256 aplenty.

The most practical danger is privatekey leaking, by organizational means, or side-channel attack.

The modern security argument for HMAC is Mihir Bellare's New Proofs for NMAC and HMAC: Security Without Collision-Resistance (full version), originally in proceedings of Crypto 2006.


Password to password mapping DISCLAIMER: I understand the question might be a bit amateurish due to my limited knowledge of cryptography but, please, bear with me for a minute.

QUESTION: Suppose a user Alice generates a pass phrase "hello", and a user Bob generates another pass phrase "world".

I need to create an encryption/hashing pipeline that would map Alice's pass phrase to Bob's pass phrase. I'll illustrate the basic idea of what I'm trying to achieve:

"hello" --> [encryption pipeline] -> "world"

The pipeline is unidirectional, as illustrated. The database of the server hosting the pipeline CANNOT store plain text pass phrases. It can store hashed or encrypted modifications of the pass phrases though, the basic goal is to make it impossible/immensely difficult to derive "world" without knowing that the original input is "hello" (say in a scenario where the database is compromised)

How could one securely implement such a pipeline and abide with common security principles? I've just started digging deeper into hashing/encryption algorithms, Levenshtein distance, etc. but I would really like to get an insight from someone who's a lot more knowledgeable in this area than myself.

The simplest solution to this would be to encrypt Bob's pass phrase under Alice's pass phrase.

In particular the following steps would be carried out for that:

Generate a salted password hash (using e.g. Argon2 or bcrypt) from Alice's pass phrase, call it $SK$
Use $SK$ to encrypt Bob's pass phrase symmetrically, e.g. using AES-GCM

If you want to be fancy and allow Bob to update his pass phrase you can also symmetrically encrypt a private asymmetric key in step 2 and use the corresponding public key to encrypt the new pass phrase whenever Bob updates it.

This can also be integrated into the standard password-hash based authentication flow by using a fast hash (like a SHA256) of $SK$ as the stored database hash value.


What is the reason to separate domains in the internal hash algorithm of a merkle tree hash? From rfc 6962 It is stated that:

  Note that the hash
     calculations for leaves and nodes differ.  This domain separation is
     required to give second preimage resistance.

That means that whenever the hash computes on leaves a distinct known element is preappend to the element $e$: $$H(0\mathbin\|e)$$ and whenever hash applied to parent nodes for leaves $h_0=H(0\mathbin\|e_0)$ $h_1=H(0\mathbin\|e_1)$ then $1$ is being put in the beggining:

$$h_2=H(1\mathbin\|h_0\mathbin\|h_1)$$

It is not clear what is the security implication if $0,1$ is not appended to the hash to separate the two domains. The authors state that this happens to prevent second-preimage attacks. But from Merkle tree hash we require from the hash function $H$ to be collision-resistant

The document you refer to describes a method for hashing lists of data entries. Assume you do not prepend $0$ or $1$. Then, the hash for the list $(e_1, e_2)$ is $H(h_1 \| h_2)$ for $h_1 = H(e_1)$ and $h_2 = H(e_2)$. It is now easy to find a second preimage of that, namely the "list" with the single entry $h_1 \| h_2$, which will be hashed to $H(h_1 \| h_2)$.

This attack does not work if you pretend $0$s and $1$s as suggested: The hash of the list $(e_1, e_2)$ is then $H(1 \| h_0 \| h_1)$ for $h_0 = H(0 \| e_0)$ and $h_1 = H(0 \| e_1)$. You now cannot easily find a preimage of that: The single entry list $h_1 \| h_2$ gets hashed to $H(0 \| h_0 \| h_1)$, and $1 \| h_0 \| h_1$ gets hashed to $H(0 \| 1 \| h_0 \| h_1)$.


Is PKCS7 a signature format or a certificate format? I always though PKCS7 was a signature format.

However, on the net I find several references to PKCS7 being a certificate format - for example, this talks about PKCS7 certificate: Extract raw certificate from PKCS#7 file in JAVA

Or: What's the difference between X.509 and PKCS#7 Certificate?

So is PKCS7 a signature format or a certificate format or both?

So is PKCS7 a signature format or a certificate format or both?

Neither. PKCS7 is now Cryptographic Message Syntax(CMS). From the RFC 5652:

  This
     syntax is used to digitally sign, digest, authenticate, or encrypt
     arbitrary message content.

CMS enables interoperability between different products which can operate on the same document without knowing anything about other product (implementation and such other specific info related to the product). CMS achieves this by defining specific message formats for each data type (signed data, enveloped data, authenticated enveloped data). Hence, each product which support CMS format can exchange files or messages defined in the CMS format with no trouble.

The second link you provided also talks about CMS format.

After comments from @Maarten:

It is also worth to mention that PKCS stands for "Public Key Cryptography Standards". These are a set of public key cryptography standards created by RSA Security Inc. Some of these standards handed over to standards organizations and they became industry standards after that.

Also, as @Maarten mentions, using CMS(PKCS7) format enables storing more than one certificate. (Check this answer)


What is the cryptography job market like these days? The security field seems to have jobs aplenty, but what about cryptography specifically? Is the field ridiculously difficult to break into, even with a relevant degree, or are industry/government/academia recruiting as heavily as industry is of software developers?

I already know of iacr.org/jobs. If that is an accurate representation of research jobs in cryptography, that particular area of cryptography doesn't look too good.

Is the government really the only game in town in terms of realistically getting a cryptography-related job, or is the job-to-competition ratio not too bad for industry jobs in cryptography?

(Sorry if I'm not supposed to post questions like this here, but I didn't see any mention of a ban on it. workplace.stackexchange just didn't seem specific enough to warrant good answers to this question. Also, I don't consider this an opinion-based question. The current supply and demand for cryptographers is a knowable, concrete fact, even if most people have only a vague sense of it rather than hard statistics.)

There is a no single variety of "cryptography job". iacr.jobs is very small representation

If you have an academic degree (like PhD in Crypto/Maths/TOC) then
very much your area of thesis might help finding a PostDoc/Asst Proff
types job for this you need to search for Universities that do work
in similar area.
You may get general faculty types position too in
their Security group if one exists usually in a Univ below your
Graduating Univ's ranking. This could be both theoretical
cryptography work or practical (systems level security) types work
depending upon your thesis etc.
Few industry associated research labs to hire crypto & security scientists they need academic qualifications like PhD too.
If you have industrial experience working on cryptographic libraries (open
source or proprietary) then you may get typical software engineering roles in C, CPP, Java with expertise in cryptography like projects that involve key management, PKI, Kerberos, SSL, Hashing, AES, protocol implementations etc.
There might be some jobs which are not explicitly advertised as cryptography jobs but may be part of larger projects that has security elements in it and you may get to work at API level calls to cryptography.
You could also be independent researcher/consultant types but you need street credentials there too like rockstar status those who found heartbleed type bugs, given blackhat/defcon type talks etc. Modern Ransomware research too needs good understanding of cryptography in order to breakupon those malware and provide decryption tools.

Note : By large it depends on what qualifications and work experience you have. Without both entry level jobs are almost rare in this niche field.


How can k3d3/ed25519-java's performance be improved? I tried asking this on stackoverflow because I thought it might be a simple coding question and didn't want to clutter up this amazing stack, but I received no responses.

CodesInChaos showed me that the proper implementation of Curve25519 for digital signatures is Ed25519 and also informed me that this implementation, the only implementation I can find, is very slow which I have now confirmed for myself.

I have essentially no experience with cryptography other than using the basic functions in that lib, so I'm afraid to touch it but would like higher performance.

To that end, how can the performance of k3d3/ed25519-java be improved?  Anything specific I can get, preferably code, would be immensely helpful!

PLEASE NOTE: The code I link to below has not yet been reviewed by anyone with professional cryptography experience. I expect that it contains bugs, and it is definitely not production-ready. I am still learning about the JCA; there are parts of the code I have not finished, and there are parts that I will most likely go back and redo. That said, the tests on example data are passing, so I think it is functional enough for testing.

I have been working on exactly this problem (I want to have a fast Ed25519 Java implementation for use in I2P). In our measurements, the original code was taking about 4 s s+v (one sign operation + one verify operation), which is much too slow for a router. I was able to speed up this implementation by a factor of twenty:

The implementation is a direct port of the slow Python implementation, which had its own expmod method. Using BigInteger.modPow() instead sped the code up by a factor of ten to 457 ms s+v.
I2P has a NativeBigInteger which provides access to libgmp's native modPow() implementation. Using NativeBigInteger.modPow() increased the speed to 289 ms s+v.

Neither of these changes have the constant-time property of the reference implementation of Ed25519 (I think - I am new to this), but then neither did the original.

After these changes, I decided to port DJB's ref10 C implementation from SUPERCOP to Java, to try and gain additional speed increases. (I also rewrote the entire thing to leverage the Java Cryptography Architecture.) The primary change here was in using extended coordinates for the twisted Edwards curve, which decreases the number of required operations.

The code in my branch takes about 20-22 ms s+v, which is about 190x faster than the original. There is no noticeable increase in speed when using NativeBigInteger; my hypothesis is that the use of extended coordinates has greatly decreased the number of modPow() calls, and the code is primarily limited by the speed of scalar multiplication.

I want to make the code even faster (to around 1-2 ms s+v). But I am not sure if there is much more that can be done to speed the code up without moving to a radix-2^51 representation of FieldElements and using tables precomputed from the base (as is done in ref10). I will test using libgmp for multiply() calls, and see if that helps. Another avenue would be to find a better algorithm for scalar multiplication.

(On a side note, I am also unsure if it is possible to use BigIntegers for constant-time operations on secrets. Then again, the only reason I stayed with BigIntegers was because I2P already packages native code in NativeBigInteger, and I would rather have a pure-Java implementation that could leverage libgmp than have to compile more native code for different platforms. If NativeBigInteger provides no speedup, then there is nothing stopping a move to something that does allow for constant-time operations on secrets.)

UPDATE (2014-04-28): I have now ported across the scalarmult and doublescalarmult methods from ref10 (including pre-computation), and it now takes ~2.1ms to run the signing code, and ~3ms to run the verifying code (on my laptop's 64-bit Core i7-U 1.9GHz; this falls directly between the sign and verify speeds for ECDSA_SHA384_P384 and ECDSA_SHA512_P521). But the results aren't correct yet, and I suspect the cause is hidden somewhere in my conversion from C's unsigned and signed bytes into Java's signed bytes and ints. I'm still working to understand the optimizations in ref10, and in particular which optimizations are necessary (like how ref10 uses bit arithmetic to execute cmov - I don't know Java or C intimately enough to know whether this is a) necessary over a switch() statement, and b) potentially where Java's lack of unsigned bytes could be causing bugs).

UPDATE (2014-05-05): The ported code was in fact correct, it was just being passed inputs that weren't correct. Additionally, I discovered two things:

My timing code was still including the creation of a PrivateKey from a seed. The actual signing time was half what I thought (both key extraction and signing are limited by the time to run scalarMultiply()).
The constant-time FieldElement.cmov() implementation (using XOR and AND) was taking 285ns to run, and scalarMultiply() calls it 1728 times. A huge speed increase is seen by changing GroupElement.cmov() to instead use return (b == 0) ? this : other.

Current timings:

1.0934 each sign, 3.0052 each verify, 4.0986 s+v (with constant-time cmov)
0.6006 each sign, 2.9454 each verify, 3.546 s+v (with simple cmov)

For us, this is excellent signing speed. Int comparison on 32-bit architecture is constant-time, so the only unknown here is whether boolean ? val : val is constant-time or not. Then again, much of the rest of the code is not constant-time yet...


In a specific Paillier implementation, why is r prime? I have a question about an implementation of the Paillier cryptosystem.

In the description of Paillier above, encryption of a plaintext message $m$ on $\mathbb {Z}_{n^{2}}$,  $0\leq m<n$, proceeds by choosing a random number $r$ such that  $0 < r < n$ and computing the ciphertext as $c=g^{m}\cdot r^{n}{\bmod n}^{2}$ for generator $g$.

However, in one open source Paillier implementation in Python, the encryption function creates $r$ as a prime number, making for slow encryptions.

I am curious about why $r$ is made prime in that implementation, when no such restriction exists in the public algorithm description.   Could it be that it is a mathematical shortcut, or a compensation for some other shortcut, perhaps as the generator g is "hard coded" to $n+1$, rather than chosen by random/trial testing?

Is there any risk in changing the implementation to make $r$ random but not necessarily prime?

I mean no discredit to the author of the code.  It is robust code and has served me quite well.  I want to understand the reasons why the restriction.  Thanks!

Is there any risk in changing the implementation to make $r$ random but not necessarily prime?

None [1].  Consider the case where you encrypt two values, forming the ciphertexts $g^m r^n$ and $g^{m'} {r'}^n$, and then you homomophically add them (by multiplying the two ciphertexts).

That results in the ciphertext $g^{m + m'} (r \cdot r')^n$.

As a result, $r \cdot r'$ may not be prime [2]; if this were a security risk, that means that you really couldn't use homomorphic addition (or, actually, Paillier at all, as an attacker could take your ciphertext, add an encrypted 0, and generate another ciphertext that encrypts the same plaintext, but with a likely composite $r$).

Hence, there is no drawback for choosing a composite $r$

[1]: Other than the risk inherent with modifying any cryptosoftware and accidentally breaking something you didn't intend...

[2]: Actually, it might happen to be, as it's actually $r \cdot r' \bmod n$, and that value just might happen to be a prime within $\mathbb{Z}$


Broadcast encryption not using symmetric keys Is there a common scheme for broadcast encryption that doesn't involve an exchange of a shared key? I'm aware that traditionally a common symmetrical key would be given to all parties and exchanged securely using the recipients' public keys.
I'm building an application on the Ethereum blockchain where I want to use one message to transmit information to all recipients involved securely. Unfortunately, this means revoking keys becomes an expensive process due to Ethereum transaction costs, as I would have to redistribute a new symmetric key to all recipients again.
Is there any way to encrypt a message using a set of public keys that could be decrypted by any of their respective private keys so that revocation is not so expensive? I would not include the revoked public key the next time I send an update. The message is quite a small amount of text, so size should also not be a problem.

Asynchronous Ratcheting Tree (ART) is an n-way Diffie-Hellman key exchange. The group initiator selects members and instantiates the tree, revealing only public information such that each other member may recompute the group shared key. Users may update their key-share as a measure to implement forward secrecy of a later compromise of their long-term static identity key.

As you're interested in at least revocation, you'll want to extend ART with dynamic groups which introduce the operations: join, leave, partition and merge.

Leaving is done willingly, however, partitioning and merging can enable selective revocation, computing partial tree updates without recomputing a whole new tree (which is not too expensive anyway).

With the group key you now use symmetric authenticated encryption.

Edit: You may additionally use the group key to derive a shared asymmetric identity such that anyone may encrypt messages to the group; but only group members (1-of-n) may decrypt the messages. As the group membership changes, the encrypting user is responsible for using the latest identity to encrypt for.


RSA cipher: ambiguous or break by eth root? Confused about RSA message cipher: $c = m^e (mod\ n)$

So if $m^e$ can be greater than n, then you can get duplicate ciphers for the same message.   Most postings I've read say that $m^e$ must always be smaller than n to counteract.

But if $m^e$ is smaller than n, then $c = m^e$ and can just be decrypted by $\sqrt[e]{c}$.  Most postings I've read said that $m^e$ should be greater than n to counteract.

So it seems like there are only 2, differently broken, options.  How is this reconciled in practice?
(My assumption is that "padding" reconciles this, but I'm not sure how.)

Due to poor use of notation, the question uses an incorrect (or at least incomplete) definition of textbook RSA encryption, which actually defines ciphertext $c$ for a given $m$ as:$$c=m^e\bmod n$$This can be read as: “ $c$ equals [pause] $m$ to the $e$th power reduced modulo $n$ ” where power or/and reduced can be left implied, and the pause emphasizes that $c$ is the result of the final modular reduction. It means that $c$ is the remainder of the Euclidean division of $m^e$ by $n$, which unambiguously defines $c$ for given $m\ge0$, $e>0$, and $n>0$. It equivalently means that $0\le c<n$ and $c\equiv m^e\pmod n$, as defined below.

The notation $c\equiv m^e\pmod n$ can be read as: “ $c$ is equivalent to $m$ to the $e$th power [pause] modulo $n$ ” where the pause emphasizes that modulo pairs with the earlier equivalent, rather than with an implied reduction. For non-zero $n$, it means that $m^e-c$ is a multiple of $n$. There are infinitely many $c$ matching this.

Notation rule: when $\mod\;$ is without an opening parenthesis immediately on its left, and without an $\;\equiv\;$ sign anywhere on its left, it means reduction modulo, or equivalently remainder. Otherwise, it tends to mean equivalence modulo. The later is unambiguous when $\mod\;$ is with an opening parenthesis immediately on its left, and with an $\;\equiv\;$ sign somewhere on its left.

Indeed, in order to avoid guess of $m$ as $\sqrt[e]c$, it is necessary that $m^e\ge n$ holds, at least with overwhelming odds. The recommendable method to ensure this is not to directly avoid small $m$; rather, it is to pick $m$ essentially as a random integer with $0\le m<n$. It is safer, and practiced, to choose $m$ in the later way, and then use $m$ as a key to a symmetric cipher protecting the confidentiality of the actual message. Other methods exist that allow conveying with $c$ a small message $M$ reversibly turned into an integer $m$ that is random enough, see PKCS#1 encryption schemes.


Is it necessary for the Rijndael polynomial to be primitive? I am working on selecting a S-box for my Cipher (Similar to AES). I found out there are 30 irreducible polynomials and over 16 primitive polynomials of degree 8. Is it necessary to choose a primitive polynomial for an S-Box? In other words, Is it necessary for the feild to be of full order(255) for a S-Box?

What are the consequences in the each case?

Is it necessary to choose a primitive polynomial for an S-Box?

Actually, it is not necessary (and, as the polynomial they actually use in AES, $x^8 + x^4+ x^3 + x + 1$, is not primitive, and so it's a good thing that it's not necessary).

The polynomial must be irreducible (if it isn't, the multiplication operation isn't invertible in general, and hence you don't get a field); however it can be shown that the selection of the polynomial doesn't actually affect the security of the cipher; for any irreducible polynomial, you can adjust the affine transformation within the sbox, the mix column transformation, and the rcon constants within the key schedule to come up with an equivalent cipher (equivalent in the sense that an attack on the modified cipher translates into an attack on the original AES).

  In other words, Is it necessary for the feild to be of full order(255) for a S-Box?

If you mean that there must be a field element with (multiplicative) order 255; well, yes, any representation of $GF(2^8)$ will have precisely 128 such elements.  However, a polynomial being primitive will imply that the element with representation 02 will have such an order; with the standard AES representation, it doesn't.


Understanding generation of IV in CBC encryption I am trying to understand CBC encryption and have a question in two parts:

When generating the next block for encryption I XOR the next plaintext block with the current ciphertext as the initialisation vector. The next plaintext block is 16 bytes, the current ciphertext is, say, 120 bytes. Which part of the ciphertext do I use? Is it implementation specific? Could I use 16 bytes from position 40?
What is the advantage of XORing the next plaintext block with current ciphertext over XORing the next plaintext block with the current XORed plaintext block? My guess is that the second option produces predictable patterns.

The next plaintext block is 16 bytes, the current ciphertext is, say,
  120 bytes

No. With CBC you consider a block cipher which transforms a plaintext block (say of size 16  bytes) to a ciphertext block (of the exact same size). So a 120 bytes ciphertext block for a 16 byte block is nonsense.

This also follows from the formula of CBC, which is
$$C_0=IV,C_i=E_K(P_i\oplus C_{i-1})$$
As you can see, each ciphertext is an output of a block cipher and thus must have exactly the same size as the input.

  What is the advantage of XORing the next plaintext block with current
  ciphertext over XORing the next plaintext block with the current XORed
  plaintext block?

So this would be $P_0=IV,C_i=E_K(P_i\oplus P_{i-1})$. Indeed, this mode doesn't hide patterns, and as such this mode is not secure against a chosen plaintext attack as you can distinguish $m=(m_1\parallel m_2 \parallel m_3 \parallel m_4)$ from $m'=(m_1\parallel m_1 \parallel m_2 \parallel m_2)$ because the latter has the same ciphertext blocks at position 2 and 4 (because the plaintexts cancel each other out) whereas the former does not.

Also see "Plaintext block chaining, bad idea why?".


Signing/verification between Java and the OpenSSL I'm trying to sign/verify data between a C application and a Java application.

In java for now I was using the built-in JCE provider with SHA256withRSA as algorithm. On the C part I'm using OpenSSL RSA_sign/RSA_verify methods with NID_sha256 as type.

With this configuration I can't verify in my java application data signed from the C one and vice versa. It seems that SHA256withRSA is using PKCS#1 v1.5 and openssl state that they use PKCS# 2.0 as padding (source).

This is why I think that the problem could come from this padding difference, but I can't find any JCE provider that support the v2.0 padding.

Is this correct? What is the difference between these paddings?

Your problem is not with the signature scheme, something else is wrong.

RSA is specified by the RSA cryptography standard, PKCS#1 (mirrored in various RFC's). The PKCS#1 v1.5 padding was introduced in version 1.5 but it persisted in 2.0, 2.1 and 2.2. Those did however introduce a more secure padding scheme called PSS.

Unfortunately nobody calls the signature generation schemes by their true name: RSASSA-PKCS1-v1_5. Both your C code and your Java code seem to use that signature scheme.


RSA Decryption from samples I am working on a project for a client which involves decryption of data which was encrypted using RSA.

The system in question retains three independent copies of each data-set, but each copy is encrypted with a different key. In this scenario, all of the private keys are gone and i want to know if anyone knows of a methodology to use the three encrypted copies of the data (which are identical - no padding) to determine the original data-set.

Any help/thoughts/comments would be appreciated.

Using the Chinese Remainder Theorem I can compute $M^3$, and then take the cube root. This is why multiple recipient RSA is insecure.


Zero Proof Knowledge for data set information I understand the Zero Proof Knowledge Protocol concept but find it tricky to implement sometimes for real world cases.

What I would need is, given a file with some key/value (numbers mainly) pairs, the verifier to verify that some values are within a certain range without knowing the information in the file.

Would that be possible with Zero the Proof Knowledge Protocol?

Thanks

Your question actually demonstrates a quite common misconception when it comes to zero knowledge. Unfortunately, you will need some basic complexity background to understand what I'm going to answer. Note: I am not going to talk here about practical and efficiency sides of zero knowledge, but rather the theoretical question of what can be proven.

The famous GMW theorem for zero knowledge is often quoted to say that "anything" can be proven in zero knowledge. However, this is a misconception: rather, it says that any language in $\cal NP$ can be proven in zero knowledge. (I am not going to relate to languages in $IP\setminus NP$ since they do not have efficient provers.) Now, this means that in order to apply zero knowledge, you have to make sure that the statement is in $\cal NP$.

Let's say that a prover $P$ holds a database, and wants to prove to the verifier that certain values are in a range. First, you need to define the $\cal NP$ statement. What would it be here? One option is to say "there exists a database $D$ such that it contains the values in the range...". Well, that's actually a trivial language since for a fixed definition of the values the answer is always yes (and irrespective of any input statement $x$). Basically, the problem here is that there is no statement of reference related to your database, and so this is meaningless.

Therefore, the way to solve this is to have the verifier hold a commitment to the file. This can come in many forms, but consider a public-key encryption scheme with key pairs $(pk,sk)$ and denote the database by $D$. Then, the statement is $c=Enc_{pk}(D)$ and the $\cal NP$-witness is the secret key $sk$. The language is all of the pairs $(pk,c)$ where $c$ is an encryption of $D$ under $pk$ (with the specified public key encryption scheme) and $D$ contains values in the range as defined. Note that $pk$ must be included in the statement since otherwise $c$ doesn't uniquely define $D$.


Higher-Order Side Channel Security and Mask Refreshing: linear function? I currently read about this paper:
https://eprint.iacr.org/2015/359.pdf

and I wanted to implement Algorithm 4 / Algorithm 5 on my own. There is one thing I cannot understand: where does function g come from (used in Algorithm 4)? It is said to be a $\mathbb{F}_2$-linear function.

Any ideas?

Actually, it's any $\mathbb{F}_2$-linear function you want it to be.

That is, those two algorithms are generic ways, given a linear $g$ and a threshld (secret-shared) value $x$, to compute a threshold version of $x \times g(x)$ (where $\times$ is $GF(2^n)$ field multiplication).


Is this a sensible cryptographic protocol intending to reduce the impact of compromised security? I'm in the process of designing a cryptographic protocol which will reduce the impact an attacker will have if they gained root access to a server storing data.

The basic crux of it is that keys which were used to encrypt data are not stored on the server and are only ever in memory for a short period of time.

The basic description is that:

a Public/Private Key pair is generated on both client and server.
The data is encrypted with both public keys by the client and transmitted to the server
The server's private key is used to decrypt the data by one level (Still encrypted using client's pub) and stored on the server
If the server needs to decrypt the data for ananlysis, this is initiated by the client who does this by sending their private key, encrypted by the server's public key (*This is the weakest point I think?)
The client's private key is decrypted and use to decrypt the data (Then thrown away)
Analysis results are then stored using client's public key (And optionally transmitted to the client)

A picture showing this can be seen :

Please be as brutal as you like - I'd like to try to get this right.

Also please note - I'm aware that if a baddie has root access to the box he'd be able to listen for the client's key transmission and decrypt that using the stored server private key and then compromise the data, but I'm trying to minimise the impact of server compromise, not remove it completely.  I want to work with the assumption, that a hack would be detected before they had time to wait for a client to send their key.

EDIT:
To Clarify - there's an assumption that the data can't be transmitted back tot he client for analysis - lets say because it's too large to make that efficient
There's also an assumption that network traffic is monitored so an attacker would only ever have limited time on the server to attempt to steal the data.

I don't think the approach you sketched helps very much.  If the server is compromised, the attacker can pretty easily modify the server-side software to log and record all the cryptographic keys, and then you haven't gained anything.  Therefore, I don't think the approach you sketch is likely to be a great way to spend your limited software development budget.

If you want to mitigate the risks of server compromise, let me suggest two alternative approaches that I think might actually be worth your time:

Privilege separation. Rather than have one server that does everything, split it up into two servers.  One server does just the crypto decryption, and the other does all of the other application functionality.  Install these on two separate servers, with separate passwords etc. so that if the latter is compromised, it won't compromise the former.  The former server is super security-sensitive, but if you also keep its functionality very simple and if you administer it carefully, you may be able to reduce the likelihood of compromise of that server.
Client-side cryptography. Don't ever allow the keys to be on the server.  Do all of the encryption purely on the client side.  The client generates the cryptographic keys, and never allows the secret key to leave the client (never shares it with the server); encryption or decryption with the private key is done entirely on the client side (not by the server).  However, it takes additional work to make this work, and make it secure, and address the resulting key management and usability challenges, so this is not a no-brainer: it comes with some non-trivial disadvantages.


Is the Keccak family of sponge constructions the same as SHA-3? I can't seem to come across a clear and to the point answer. Is SHA-3 in the same situation as ElGamal and DSA, where it is modified slightly, or is the original Keccak submission the exact same as NIST standardized SHA-3?

SHA-3 is defined by FIPS 202.
If you go to the team Keccak website you will read the following.

Keccak is a versatile cryptographic function. Best known as a hash function, it nevertheless can also be used for authentication, (authenticated) encryption and pseudo-random number generation. Its structure is the extremely simple sponge construction and internally it uses the innovative Keccak-f cryptographic permutation.
After its selection as the winner of the SHA-3 competition, Keccak has been standardized in 3GPP TS 35.231 for mobile telephony (TUAK), and in NIST standards FIPS 202 and SP 800-185. Consequently, it has received extensive public scrutiny and third-party cryptanalysis.
[source]

Thus Keccak[1600] is the exact same as NIST standardized in SHA-3.


Linear transformation proof Ok, so I have this question and I honestly have no idea how to prove it. I know that the function is linear and I know it works for every possible combination, I just don't know how to prove it in an arbitrary manner. Here is the question:

Suppose that instead of using those S-boxes, DES would just substitute a 6-bit string with its first 4 bits, that is T(b1 b2 b3 b4 b5 b6 ) = b1 b2 b3 b4. We have called this transformation T. Show that T is a linear transformation (Note: you need to prove that T(x xor y) = T(x) xor T(y), for all 6-bit strings x and y, not just for a particular pair x and y; so write down a proof that works for arbitrary x and y).

I have no idea where to start since this class isn't about writing proofs.

Well, we start with a small definition of XOR for bit strings larger than zero bits. $x$ and $y$ are bit strings with the lenght $n$ and $x_{k}$ denoting the $k^{th}$ bit (from $0$ to $lenght - 1$). $||$ represents concatenation and $\oplus$ means XOR. So we get:
  $$  x \oplus y = ((x_{0} \oplus y_{0}) || (x_{1} \oplus y_{1}) || ... || (x_{n-1} \oplus y_{n-1})) $$
Our function $T$ just returns the first 4 bits from a 6 bit string (or an arbitrarily large bit string longer or equal to 4 bits, it doesn't really matter), so we can write it as:
  $$ T(b) = (b_{0} || b_{1} || b_{2} || b_{3}) $$

Now we want to show that $T(x \oplus y) = T(x) \oplus T(y)$

How could we do that? Maybe we could insert the different definitions of our functions and see where it goes from there..?

(That's maybe not the most optimal way to answer this question, but (I think...) it works.)


Is there a definition of the pseudo-random sequences like PRG or PRF in cryptography? I have learned the definition of PRGs and PRFs. As I know the meaning of pseudoreandomness. I think that the pseudo-random sequence and the truly random sequence are indistinguishable.

I did not find a definition of the pseudo-random sequences. And I think the definition should describe some possible collections of "pseudo-random sequences" (e.g. M-sequence).
Follows are my approaches which may be helpful.

Let a sequence $\alpha = (a_{1}, a_{2}, \ldots, a_{n}, \ldots)$ is a sequence over a finite set $\Sigma$ ($|\Sigma| > 1$), where $a_{i} \in \Sigma$. It is truly random if $a_{i}$ is chosen uniformly in $\Sigma$.

Let $\beta= (b_{1}, b_{2}, \ldots, b_{n}, \ldots)$ be a sequence over $\Sigma$. It is pseudo-random sequence if for every PPT algorithm $A$, there is a negligible function $\varepsilon$ such that

$$\left\vert \Pr \left[ A(b_{1} \Vert b_{2} \Vert \cdots \Vert b_{n}) = 1 \right] - \Pr\left[ A(a_{1} \Vert a_{2} \Vert \cdots \Vert a_{n}) = 1 \right] \right\vert \leq \varepsilon(n)$$

Or can we consider that it is unpredictable? Let $\beta= (b_{1}, b_{2}, \ldots, b_{n}, \ldots)$ be a sequence over $\Sigma$. It is pseudo-random sequence if for every PPT algorithm $A$, there is a negligible function $\varepsilon$ such that

$$\left\vert \Pr \left[ A(b_{1} \Vert b_{2} \Vert \cdots \Vert b_{n}) = b_{n+1} \right] - \frac{1}{|\Sigma|} \right\vert \leq \varepsilon(n)$$

I think that the pseudo-random sequence and the truly random sequence are indistinguishable.
And I think the definition should describe some possible collections of "pseudo-random sequences" (e.g. M-sequence).

Congratulations, you have a very good intuition! You're almost there.
A key to understanding the definition of a pseudorandom sequence is that there is no such thing as a pseudorandom sequence. If you have a specific sequence, then there's no randomness involved! Instead, the useful concept is that of a pseudorandom sequence family, more usually called pseudorandom function family (but abbreviated PRF). In a nutshell, a pseudorandom sequence family is a family of sequences such that given some data that may or may not be part of a sequence in that family, and bounded computational power, there is no way to know whether the data is from a sequence in the family or was generated uniformly at random. In other words, a pseudorandom sequence is indistinguishable from a random sequence.
Note that “uniformly at random” here is a mathematical definition: a uniformly random bit sequence is one where the value of each bit is independent (in the sense of probability theory) from the value of other bits as well as from all other events in the world. This definition does not consider whether it is possible to perform this generation in the physical world.
The definition of pseudorandomness only considers the output of the process, not how this output is produced. Otherwise it would be a circular definition: a pseudorandom generator is one that produces pseudorandom output — “pseudorandom output” has to have some definition other than where the output come from. The definition is about what you can deduce from observing the output. A pseudorandom generator is an algorithm that transforms a seed into the element of a pseudorandom sequence family that is indexed by the seed value.
To put this indistinguishability in more mathematical terms, consider an observable property $A$ of the output. For example, “bit $3$ is 1 and bits $4$, $5$ and $6$ are not all equal”. This observable property has a certain probability $\Pr_U(A)$ of being true for the uniform random distribution ($\frac{1}{2} \cdot \frac{6}{8}$ for the example above). If you pick a random element of the pseudorandom sequence family $F$, the probability of this observable property $\Pr_F(A)$ must be close enough to the probability for the uniform random distribution: $\Pr_F(A) \approx Pr_U(A)$.
To make this definition fully precise, we still need to say what observable properties are permitted and what “close enough” means. We aren't interested in adversaries with infinite computational power, which is why we restrict $A$ to polynomial computations. And “close enough” is defined as bounded by a negligible function. That's how the equation in your question comes about. The piece that you were missing is that you don't first select specific sequences $\alpha$ and $\beta$. Rather, $\alpha$ and $\beta$ are a probability distribution over sequences: $\alpha$ is a choice of element of the function famility, and $\beta$ is a uniform choice over all possible functions.


zeroing out slots in SEAL ciphertext I've been messing around with SEAL library for a few days and I've got a following question.
I've got a bunch of datapoints [x_1, ..., x_n], n < poly_mod_deg of type 'double' and I use batch encoding and CKKS sceheme to calculate
their average and variance. Calculating average works fine and I like the result, but I would like to calculate variance in more efficient way.
To explain what I mean:
Going into variance calculation I have following data:
Encrypted([x_1, x_2, x_3, ..., x_n, 0, ..., 0]) and
Encrypted([x_avg, x_avg, x_avg, ..., x_avg]) (*)
Next I calculate their difference and get something like:
Encrypted([x_1 - x_avg, x_2 - x_avg, x_3 - x_avg, ..., x_n - x_avg, -x_avg, -x_avg, ..., -x_avg]) (**)
Then I square and get:
Encrypted([(x_1 - x_avg)^2, (x_2 - x_avg)^2, (x_3 - x_avg)^2, ..., (x_n - x_avg)^2, x_avg^2, x_avg^2, ..., x_avg^2]) (***)
And then I sum first n values using n left by-one rotations and divide the result by n to finally get the variance.
-----------------------------------------------------------------

This works fine for small n. But I want to zero-out useless components at (*) or (**) or (***) so that after squaring I'd get the following:
Encrypted([(x_1 - x_avg)^2, (x_2 - x_avg)^2, (x_3 - x_avg)^2, ..., (x_n - x_avg)^2, 0, ..., 0])
I want that because then I'm able to calculate their sum using only log2(poly_mod_deg/2) sumations using technique described in https://www.youtube.com/watch?v=XaYEHnaAg8M&t=47m29s
Is it possible to achieve that in simple, secure in efficient way?
I've tried to multiply (*) or (**) or (***) by [1.0, 1.0, ..., 1.0, 0.0, ..., 0.0], where all but the first n components are zero.
It didn't work because compiler complained with 'result ciphertext is transparent' and
aborted the mission and I didn't like that solution anyway since it uses one more multiplication, which hopefully is excessive.
Increasingly desperate I also tried to copy encrypted zero from Encrypted([x_1, x_2, x_3, ..., x_n, 0, ..., 0]) into last components of
Encrypted([x_avg, x_avg, x_avg, ..., x_avg]).
 I did something like:
c_zero = Encrypted([x_1, x_2, x_3, ..., x_n, 0, ..., 0])[n+1];
while n < i < poly_mod_deg:
     Encrypted([x_avg, x_avg, x_avg, ..., x_avg])[i] = c_zero;
     i++;
But i guess this stuff just doesn't work this way, since printing out last 20 or 30 values of Encrypted([x_1, x_2, x_3, ..., x_n, 0, ..., 0]) shows no repetition.
On that note, this also probably means that i always have to inform "server-side" about the number of encrypted datapoints in ciphertext? How unsafe is that?
I didn't want to bloat the post with code, so it's here: https://pastebin.com/Uy0wdgG9. Also deleted comments from the code, since they were in my native tongue. Sorry.
Also on the chance that someone from the SEAL team sees this: great job,  fun stuff!

As a caveat, I have never worked with Microsoft SEAL. But the following may still be useful.
The formula for the variance of a finite dataset $(x_1,\dots, x_n)$ can be written as:
$$\sigma^2 = \frac{1}{n}\sum_{i = 1}^n(x_i - \mu)^2$$
where:
$$\mu = \frac{1}{n}\sum_{i = 1}^n x_i$$
Note that $n\mu = \sum_{i = 1}^n x_i$ --- I will switch between these two expressions freely.
One can algebraically manipulate the expression for $\sigma^2$ to the following expression:
$$\sigma^2 = \frac{n\sum_{i = 1}^n x_i^2 - \sum_{i = 1}^n x_i}{n^2}$$
(check that this is an identical formula)!
This expression can be computed more easily as follows. Let $\vec{x} = (x_1,x_2,\dots, x_n, 0,0,\dots,0)$ be your plaintext vector, where I assume $n$ is a secret parameter (things are easier if this is not the case, but not by much).
Let $c$ be the encryption of $\vec{x}$.

Compute the ciphertext vector $c_{n\mu} =(n\mu, n\mu,\dots, n\mu)$ via your rotation trick (you already do this)

Square $c$ coordinate-wise to get the vector $c_{x_i^2}$ with "slots" $(x_1^2,\dots, x_n^2, 0^2,\dots, 0^2)$

Apply your rotation trick to $c_{x_i^2}$ get the vector $c_{\sum_i x_i^2} = (\sum_i x_i^2, \sum_i x_i^2,\dots, \sum_i x_i^2)$

Now, any slot of $c_{n\mu}$ (they all take the value $n\mu$), any slot of $c_{\sum_i x_i^2}$ (they all take the value $\sum_{i = 1}^n x_i^2$), and $N$ are sufficient to compute the variance via the formula:
$$\sigma^2 = \frac{n\sum_{i = 1}^n x_i^2 - n\mu}{n^2}$$
If you can defer this computation to decryption (even as $N\to\infty$ it should remain quite efficient, like 4 arithmetic operations) then you should do that (and the ciphertext can take the form $(c_{n\mu}[0], c_{\sum_i x_i^2}[0], c_N)$, where $c_N$ is a ciphertext encrypting $N$).
If not, the problem is reduced to being able to extract (any) "slot" of a SEAL ciphertext, which is likely quite possible without doing more multiplications.
This leads to a number of different situations:

If $N$ must be kept secret and you cannot defer this computation, you then must clearly compute the multiplications $c_N\times c_N$, $c_N\times c_{\sum_i x_i^2}$ (which can be done in parallel, increasing multiplicative depth by 1), and the division by $c_N\times c_N$, leading to a computation of multiplicative depth 3 (the same complexity as your "bad" situation of zeroing things by multiplying by the ciphertext encryption $(1,1,\dots,1,0,0,\dots,0)$.)

If $N$ can be public, you only have to compute scalar multiplications, so can be done in (total) multiplicative depth 1

If you can defer the computation to decryption, you can do the entire computation in total multiplicative depth 1 again (even while keeping $N$ secret).

All of this discussion is assuming that you want to minimize multiplicative depth. It looks like you are using CKKS as your underlying scheme, and I can't remember if its complexity is controlled by multiplicative depth or something more esoteric (such as GSW's way of computing the complexity of multiplications). Still, the two points of:

Rewriting computations to be algebraically identical, while (hopefully) simpler to compute homomorphically
Deferring (small) parts of the computation for execution on the client when possible

are worth keeping in mind as generic ways to optimize things.


Security of somewhat homomorphic encryption via LSB encoding? I'm reading this paper
https://eprint.iacr.org/2011/344.pdf

It says that
"The secret-key encryption scheme whose security is based on the LWE assumption is rather straightforward.
To encrypt a bit, $m \in \{0, 1\}$ using secret key $\mathbf{s} \in \mathbb{Z}_q^n$, we choose a random vector $\mathbf{a}\in \mathbb{Z}^n_q$ and a "noise" $e$ and output the ciphertext

$$
 c = (\mathbf{a}, b = \langle \mathbf{a}, \mathbf{s}\rangle + 2 e + m) \in \mathbb{Z}^n_q \times \mathbb{Z}_q
$$

The key observation in decryption is that the two “masks” – namely, the secret mask〈a,s〉and the “even mask” 2e– do not interfere with each other. (* Footnote)
"

The footnote says that
"We remark that using $2e$ instead of $e$ as in the original formulation of LWE does not adversely impact security,so long as $q$ is odd (since in that case 2 is a unit in $\mathbb{Z}_q$)"

Does this mean using even $q$ incurs vulnerability of the scheme?
If so, what is the intuition behind that?

As hinted by @kelalaka in the comments, note that $q$ is odd, and $\gcd(2,q)=1.$

Therefore within $Z_q$ we have that $2e\neq 0,$ if and only if $e \neq 0,$ so the noise is never masked.


Practical BCrypt plus XOR encryption for small messages This is a practical solution available and potentially useful to everyone, so please give some leeway not banning this question. Details are at the end, but here is the question:

How secure is the following encryption approach?

In few words, it uses BCrypt to hash passwords. BCrypt is then used repeatedly on the result of prior hashing, and all the hashes are concatenated to make a Key as long as the Message itself. The encryption is a simple Key XOR Message. Details are below:

Note. BCrypt salt is hard coded and is removed from the resulting hash, when applying BCrypt function.

Encryption

  Message = Any Ascii128 text
  Pass1, Pass2, Pass3, Pass4, Pass5 = Ascii128 based 5 password fields
  Password = Pass1 XOR Pass2 XOR Pass3 XOR Pass4 XOR Pass5
  Checksum = {

  ShortMessage = Message
  Repeat while ShortMessage is longer than 50 chars,

ShortMessage is cut in half, and the halves XOR to get new ShortMessage

  ChecksumBase = fromBase64toAscii128(BCrypt(ShortMessage XOR Password))
  Checksum = ChecksumBase.substring(1 to 4)}

  Key = {

  LongKey = BCrypt(Password + Checksum)
  CurrentKey = LongKey + Checksum
  Repeat while LongKey.length < Message.length :

CurrentKey = BCrypt(CurrentKey)
LongKey = CurrentKey + LongKey

  Key = fromBase64toAscii128(LongKey)
  }

  SecureCode = Checksum + (Message XOR Key)
  SafeMessage = fromAscii128toBase32(SecureCode)

Decryption

  SecureCode = fromBase32toAscii128(SafeMessage)
  CheckSum = SecureCode.substring(1 to 4)
  Password = see in Encryption
  Key = see in Encryption
  Message = SecureCode.substring(from 5) XOR Key
  CalculatedCheckSum = see in Encryption
  Integrity check = recovered CheckSum must match CalculatedCheckSum

Please, rate the safety of the approach on a scale from "kids safe" to "unbreakable", as quite a few people use the program, and want to know how secret their secrets are.

There is a link from the project's page to this question, so your answers will be a validation of the project for better or for worse.

The program can be run here. It is on GitHub and cannot be maliciously altered without a public record of the change. (There are no plans for change as this would compromise current user base).

If someone would care to take a look at the JavaScript, to ensure it does what is declared and put a comment in here, this would be awesome.

No that is not secure.

If someone knows the first part of the message (27 characters I think), they can extract the first part of the LongKey and regenerate the rest of it, WITHOUT THE PASSWORD.

The so called checksum is not cryptographic, not even as robust as CRC32, if you have a 100 character message with the first and 2nd half the same, the checksum is 0. You can also swap message halves without changing the checksum. And worst of all, the checksum is both unencrypted and gives away information about the plaintext, assisting in a plaintext recovery effort.

Trying to use the checksum like a salt as part of the bcrypt input is ineffective, and if the password is long enough, is ignored, making all of LongKey first blocks identical, allowing immediate breakage of all messages that used the same passwords.

The passwords being XOR'd together makes the combined password length only as long as the longest one, and might help prevent a dictionary attack but does not increase entropy like concatenation would.

If you want me to rate from "kids safe" to "unbreakable", you might have gotten it up to "kids safe" if almost every step of the way wasnt done incorrectly.


Do you need a HMAC if decryption attempts are severely limited? I am considering an application where data bandwidth is extremely limited, and considering removing message authentication codes from encrypted transmissions. The encryption method is currently AES-256-CBC.

In this particular application, decryption attempts are extremely limited. Each decryption attempt must be initiated by the user, which powers on the processor. At first decryption failure (or success), the processor is powered off.

I am assuming that the AES key is (initially) not known by any attacker.
I am also assuming that the attacker does not have physical access to the decrypting processor.

Given the above assumptions and limitations, is the encryption scheme still secure? The 16 byte overhead for HMAC are very expensive in this application.

"Given the above assumptions and limitations, is the encryption scheme still secure?"

No; the attacker can

remove blocks of [IV + rest_of_ciphertext] from either end to remove corresponding

plaintext blocks without affecting any other part of what it decrypts to
change the IV to change the initial plaintext block in the same way as for the OTP,

without affecting any other part of what it decrypts to
change any other plaintext block in the same way

at the cost of garbling the previous block
remove one or more consecutive internal plaintext blocks at the cost of

xoring the next plaintext block with a pseudorandom but predictable value

.   Furthermore, the attacker can combine those things in whatever order they want.

What follows can be improved if the algorithms can be stateful or there can

be associated data, but otherwise the best way to get short ciphertexts is:

key  =  $\langle$auth_string , PRP_key$\hspace{-0.03 in}\rangle$

encrypt$\big(\hspace{-0.04 in}\langle$auth_string,PRP_key$\hspace{-0.03 in}\rangle$,iv,m$\hspace{-0.03 in}\big)$  =  PRP$\hspace{-0.03 in}\big(\hspace{-0.03 in}$PRP_key ,$\langle$auth_string,m,iv$\rangle \hspace{-0.04 in}\big)$

decrypt$\big(\hspace{-0.04 in}\langle$auth_string,PRP_key$\hspace{-0.03 in}\rangle$,ciphertext$\hspace{-0.02 in}\big)$    =    if PRP-1$\hspace{-0.03 in}\big(\hspace{-0.03 in}$PRP_key,ciphertext$\hspace{-0.02 in}\big)$ parses as

an ordered triple whose left entry is auth_string then that triple's middle entry else $\bot$

auth_string being secret might help against some weakness in the PRP,

but otherwise even letting the attacker choose auth_string would be fine.

The "strong pseudorandom permutation" from Theorem 3.1 is the fastest large-domain PRP I'm aware of, and it will suffice if the number of encryptions is also sufficiently small

compared to ciphertext size.  There are other constructions that handle more queries

and/or ciphertext-space sizes other than powers of 4, with these being the simplest.


Private Information Retrieval--Is it still theoretical? Are there any real world products in which private information retrieval techniques are used?(a data hosting server oblivious of which data item was fetched from it?)If not what are the major barriers for its implementation?

Not a real answer, but some hints:

Single DB PIR schemes (ones that don't need several non-colluding DB) have had serious efficiency problems for a long time. See paper 'on the computational practicality of private information retrieval' by Sion and Carbunar arguing that all schemes at that time (2007) were less efficient than downloading the whole DB (most simple PIR technique).

However the same year, Trostle and Parrish published a PIR scheme that does not have this problem. If someone uses PIR he's probably using this one.

We use it in my team but it's research, and I am not aware of use cases in the industry.

EDIT

As mentionned by DrLecter, Trostle and Parrish single-database cPIR has been broken (http://eprint.iacr.org/2015/012).

Good news are that PIR has evolved since then and a French team built a PIR framework to prove that PIR is now practical: XPIRe: Private Information Retrieval for Everyone

The PIR they use does more or less the same thing as Trostle and Parrish, i.e encryption of a zero for cells you don't want, encryption of 1 for cell(s) you want, but they use a stronger underlying homomorphic encryption scheme so that it's not broken. The obtained throughput and latency they obtain is insane (1080p streaming over NetFlix-like DB !!!).


Can $r$ and $s$ from an ECDSA signature be negative numbers? I have an ECDSA implementation in Mathematica over secp256k1 and $r$ and $s$ are always positive numbers. But if you encode them as bytes, the most significant byte can be over 0x80, which would make it a negative number if the big-number is interpreted as being signed.

I'm asking because the bitcoin implementation has these checks which I don't understand:

if (S[0] & 0x80)
    return error("Non-canonical signature: S value negative");
if (R[0] & 0x80)
    return error("Non-canonical signature: R value negative");

The $r$ and $s$ values that I produce seem that they would fail these checks when they are larger than $2^{255}$

You appear to be testing a DER-encoded integer.

DER-encoded integers are defined so that they can encode both positive and negative values (in cryptography, we don't need to encode negative integers all that often; however ASN.1 isn't specific to cryptography).

DER-encoded integers are defined this way:

Positive values are represented by the minimal number of bytes that can represent the integer (in bigendian byte order), with the msbit of the initial byte being clear.

For example, the value 32768 would be represented by the three bytes 0x00 0x80 0x00.  We are not allowed to use the two octets 0x80 0x00, because 0x80 has the msbit set

Negative values are represented by the minimal number of bytes that can represent the integer (in two's complement notation), with the msbit of the initial byte being set.
Zero is represented as a single 0x00 byte

Hence, testing the msbit of the initial byte will correctly tell you whether the represented integer is nonnegative.


RSA given d and d = p Assume we have a somehow unorthodox implementation of RSA whereby:

$p$ and $q$ are chosen primes of length $n/2$ where $n$ is the number of bits desired in $N=p\,q$ and
$$\begin{align}
\phi &= (p-1)(q-1)\\
d &= p\\
e &= d^{-1}\bmod \phi
\end{align}$$

I can see that there is a weakness here but I'm unsure of how it translates. Playing around a bit I see that I end up with:

$$e = \frac{\phi j + 1}p $$

Further assuming that $\frac{1}p$ can be considered infinitesimal:
$$e ≈ j\left(q\left(1+\frac{1}p\right) -1\right)$$

So basically:
$$e ≈ j(q-1)$$

Is that right? Am I missing something?

Yes, it's broken.  Here is the approach I see:

$$p = \text{gcd}( n, r^e - r \bmod n)$$

with quite high probability, for random $r$.

This happens because $e \equiv 1 \bmod p-1$, and hence $r^e \equiv r \pmod p$ (for any $r$).  It is unlikely that $r^e \equiv r \pmod q$, and hence $r^e - r$ has $p$ as a factor, but (probably) doesn't have $q$.


Is building your own inefficient but secure cipher hard? Everyone says you should never build your own cryptosystem. That doing so is hard and the only way you know it's secure is if it stands up to serious scrutiny.
And yet, if you are willing to go way overboard on key size, rounds cpu time, memory etc. Would it not be fairly easy for even a novice cryptographer to build something secure. Especially if using a well understood basic construction(e.g feistal network).

If you are building something based on existing research, then yes, the construction of such a system would not be challenging. As a very basic example, it wouldn't be extremely challenging to implement a system based on the One-Time Pad given that you have a good programming background and assuming you follow the algorithm's stipulations correctly (e.g. avoiding repeated keys for new messages, good RNG, etc.), your system will be provably secure.

However, if you seek to design and develop new encryption schemes, you might have a harder time. You will likely encounter issues in multiple layers starting from the theoretical development and proof of security and all the way to the practical implementation of the scheme. That is, you will have to, firstly, design an encryption algorithm that can be proved to be secure in a mathematical way. Secondly, depending on the complexity of the algorithm that you designed, you will have to be extra careful in avoiding bugs in your code that could allow a motivated attacker to break your crypto system.

Because of these reasons, it is highly encouraged that such algorithms are open: it allows for more eyes to look for both flaws in the theory as well as in practice.

Some resources to expand your research:

https://crypto.stanford.edu/~ananthr/docs/crypto-proofs.pdf
http://eprint.iacr.org/2000/067
(taken from: Proofs of security methodologies)


How to show that the following function is not a OWF? Given F, which is a Pseudo Random Permutation, I need to prove that the following function f is not a OWF:

f(x, y) = Fx(y)

My first thought would be to create an adversary which tries and compute Fx-1(y) with different values for x, but I'm not sure it would be PPT. How can I solve this?

Any $x$ is fine. Since $F$ is a PRP, for any key $x$ and output string $z$ there is an input string $y$ such that $F_x(y) = z$.


Question about variations on Vigenere cipher I'm new here and by no means an expert on cryptography.  I like to dabble, and one of my favorite classical ciphers is the Vigenere.  I understand that the normal method of Vigenere encrypting is to add the corresponding number of the letter of the key to the number of the letter of the message, thus producing the cipher text for that particular letter.  My question is, regardless of key length, is it advantageous to alter the order in which the key is applied to the message?  For example, instead of moving forward through the alphabet to obtain the cipher text, what if I started off by going backwards?  Or if I alternated by going forward with the first key letter, then backwards with the second, and so on.  Or if I alternated by going backward with the first two key letters, then forward with the next two.  Would this make it any harder to decipher the message or make it more difficult to use letter frequency analysis to obtain the key?
I can provide examples if my question isn't clear.  Thank you in advance for any insight you are able to provide.

Welcome to Cryptography Stack Exchange!
Your variation would not make cryptanalysis significantly harder.
Stepping forward through the alphabet by $n$ steps is the same as stepping backwards through the alphabet by $26-n$ steps and vice-versa. Thus the Vigenere stage S forward (+18) is the same as the variant H backward (-8). The net effect is that the encryption is equivalent regular Vigenere encryption with a garbled codeword and the same cryptanalysis applies. For example, if we used your variant Vigenere with the codeword EXAMPLE and the direction BFBFBBB it would look like Vigenere with the codeword WXAMLPW.
Your idea is related to the "variant Beaufort" of the Vigenere cipher where encryption was done by stepping backwards and encryption by stepping forwards.


What encryption/decryption system should I use for media server There is a server from which media files will be streamed to cross platform mobile/desktop apps.

The idea is to encrypt the files while uploading using the web browser, store it in the server and when requested, files will be sent over to the front end, decrypted there and media played.

Users can use multiple devices (Android, iOS, Webapp, PC, Mac, Linux) with their account, but at any particular time only one device can play the media. If users, hypothetically, get access to the encrypted files from the server or while downloading to the app (man in the middle), should not be able to decrypt the files. Only the app should decrypt the files under the hood.

I am not sure how or what system of encryption to implement since I barely know cryptography.

A good part of this question is answered here, but it really doesn't discuss the part of users not able to decrypt the files using other tools.

"but it really doesn't discuss the part of users not able to decrypt the files using other tools." ... yes it does, because it discusses key management. As by Kerckhoffs principle, you should not try and secure the algorithm itself, security relies on the keys. Tools that receive the correct keys should be able to decrypt the media.

You can of course embed a secret or private key in the app, and require both the keys from the discussed scheme and the app key. It would however just take a single reverse engineering of the app to nullify the additional protection.

The practical way on how keys can be protected on the specific devices (e.g. using device specific key stores) is off topic for this site.


Are SHA-2's $\mathit{Maj}$ and $\mathit{Ch}$ functions non-linear? SHA-2 has two functions:

$\mathit{Maj}(x, y, z) = (x \land y) \oplus (y \land z) \oplus (x \land z)$

$\mathit{Ch}(x, y, z) = (x \land y) \lor (\neg x \land z)$

Are these two functions non-linear? Can they be used in place of S-boxes in block ciphers?

Theses are the "Majority" and "Choose" Boolean functions, respectively; they are linear functions by definition.  Since there is no multiplicative or exponential element in the formulae then any linear combination of these would also be linear.

As for their applicability to S-Block "Substitution" block ciphers, if you design an algorithm using the functions to generate ciphertext characters based upon plaintext, keycode and substitution alphabet inputs then, yes, they could be used.


Using CBC with a fixed IV and a random first plaintext block What if, instead of using CBC mode in the normal way with a random IV, I used this approach:

Use a fixed IV (like a block of 0's).
Before encrypting, generate a random block and prepend it to the plaintext.
After decrypting, ignore the first block.

Is this exactly the same in terms of security as using a random IV?

Also, would it make any difference if I used something like a message counter instead of a random block in step 2?

The security of that approach is equivalent to that of normal CBC.

Your scheme with first plaintext block $IV^\prime$ is clearly identical to normal CBC with $IV=AES(IV^\prime)$. Since a block cipher is a permutation over a block, a uniformly random first plaintext block will lead to a uniformly random IV for normal CBC.

A ciphertext produced with your scheme is of the same nature as with plain CBC. i.e. you can decrypt a normal CBC ciphertext with your algo, and you can decrypt a ciphertext produced by your algo with normal CBC.

The only downside of your scheme is that it costs one additional AES invocation per message. No difference in ciphertext size, and no CPU cost beyond that single call.

One interesting question is what happens with IVs that are unique, but not unpredictable. I suspect your scheme is secure in such a situation, unlike normal CBC. But I don't have a proof for that.


Why are $\lceil 1/\operatorname{entropy-per-bit} \rceil$ number of bits not sufficient to generate an unbiased bit? Consider a biased RNG badrand() generating 1 with probability $0.9$ and 0 with probability $0.1$.
This excellent answer explains that we need 849 bits of badrand() to generate 1 bit of betterrand() with less bias than the NIST recommended $2^{-64}$.
The minimum entropy per bit of badrand() is 0.152 bits/bit.
Considering the additive nature of entropy, 7 bits of badrand() contains 1.064 bits of entropy.
Why, then, do 7 bits of badrand() not suffice to get 1 bit of betterrand()?
If a quantitative answer is difficult, a qualitative one would also inspire deep gratitude in me.

Entropy and bias are not the same.
Yes, total entropy is additive so as you suggest 7 bits of badrand() produce a total of 1.064 bits of entropy. So? How would you use that?  In cryptography we aim to use some source to produce a stream of independently and identically distributed random bits.
Assume a plaintext ($p$) of octets XORed with an octet keystream ($k$) to generate ciphertext ($c$) as $c = p \oplus k$. Where would you get 8 bits of $k$ from?  We would need to use up at least $\frac{8}{0.152} \approx 53$ bits from badrand(). So the issue becomes how do you transform 53 bits into 8 to be usable as an unbiased keystream?
We could use a randomness extractor such as a 2 universal hash function. That can be as simple as vector multiplication. The maths (Leftover Hash Lemma) governing the transformation tells us that the output bias $\epsilon_{hash} = 2^{-(sn - k)/2}$. In your case, $\epsilon_{hash} = 2^{-(0.152 \times 53 - 8)/2} = 0.98$. Not much improvement over the raw bit stream! The maths only works if $n$ is increased to >849 which then gives you a small enough bias for $k$ to be cryptographically useful.
As stated in the linked paper, there is a large entropy loss as an unavoidable(?) consequence of the transformation. The loss can be reduced and the extraction made more efficient, but nothing comes entirely for free.

Speaking of entropy loss: The most important factor that can reduce the entropy loss is the output size of the extractor function. Your example uses 8 bits. So the entropy loss is just over 99%. That's bad. Imagine using SHA-512 instead of an 8 column wide vector extractor. You'd hash 4211 bits to produce 512. The loss is now 88%.


Hardware optimized stream ciphers? As I understand it, ChaCha20 is slower than AES-CTR in hardware.  Are there any hardware-optimized stream ciphers?

eSTREAM competition has 2 profile:software and hardware,and the goal of hardware profile was to design a stream cipher that it should be hardware-optimized,and the final candidates were grain v1 and Trivium and MICKEY v2.a comparison of hardware performance of Grain,trivium and MICHEY is on the below image:


Proofs that NM-CPA implies IND-Cpa and $\text{IND-CCA} \leftrightarrow \text{NM-CCA}$ I am looking for a proof for the following two claims from "Serious Cryptography" by Aumasson.

  NM-CPA implies IND-CPA. [...] IND-CCA and NM-CCA are equivalent notions that imply the presence of the other.

where IND-CPA/IND-CCA and NM-CPA/CCA are defined as indistinguishability and non-malleability under chosen plaintext/chiphertext respectively.

Where can I find those proofs?

This paper, AFAICT: https://www.cs.ucdavis.edu/~rogaway/papers/relations.pdf
It is about the security of public-key encryption, but the proofs about the relations between security definitions are applicable to symmetric encryption.


An unpredictable PRG is secure (Theorem Yao'82) in the Mr Boneh's online course is stated the following theorem:

  Let $G:K \to \{0,1\}^n$ be a PRG.

  “Thm”: if $\forall i \in \{0, … ,n-1\}$ the PRG $G$ is unpredictable at pos. $i$,
  then $G$ is a secure PRG.

Moreover, according to his words, proving this is just a "puzzle" to prove, but actually I can't see it so easily, the only idea I have at the moment is arguing that if you can't predict the next bit of some pseudo-random string, then you can't distinguish between that pseudo-random string and a that pseudo concatenated with a truly random one in that position, It's a nice beginning but I don't know how to exploit it. Can someone give me a hand in the argument for the proof? Thank you very much.

PS: Here you can find the definition of unpredictable, secure PRG we've used and the theorem itself (Althought in my opinion, those definitions as stated there are not satisfactory from a mathematical point of view).

This lecture  (PDF) has the solution in section 3.

Here's my informal explanation of the proof:

We have an unpredictable PRG $G$. We want to show that $G$ is secure, or in other words indistinguishable from $R$ (I'll use = to mean indistinguishable whenever referring to two distributions for the remainder of the proof).

Using the notation that $G_k R_{n-k}$ means get the first $k$ bits using $G$ and generate the last $n-k$ bits totally randomly, it suffices to show that $G_{i-1} R_{n-i+1} = G_{i} R_{n-i} \ \forall i$, since then $G_n = G_{n-1} R_1 = G_{n-2} R_2 ... = R_n$ by a trivial induction, and $G_n$ is $G$, $R_n$ is $R$ by definition.

So we want to show that for all $0 \le i \le n-1$, $G_{i-1} R_{n-i+1} = G_{i} R_{n-i}$.

Assume for sake of contradiction that this doesn't hold for some $i$. That means there is some statistical test $A$ which can distinguish $G_{i-1} R_{n-i+1}$ from $G_{i} R_{n-i}$, or a statistical test where the advantage is non negligible. This means that either $A$ is more likely to equal $1$ when using $G_{i} R_{n-i}$, or more likely to equal $0$ when using $G_{i} R_{n-i}$, without loss of generality let's say $1$. So pick a random bit $b$ and run $A(G_{i-1} b R_{n-i})$.

If it returns $1$, then we'll guess that $b = g_i$ (since $A$ is more likely to equal $1$ when the first $i$ bits come from $G$); if it returns $0$, we'll guess that $b \neq g_i$. This is just a guess, but since there's a non-negligible advantage, the odds that we guessed correctly are greater than $\frac 1 2$ by the same non-negligible factor.  This means we can predict the $i$th bit from the first $i-1$ bits, which contradicts our assumption that $G$ is not predictable.


How can convert affine to Jacobian coordinates? I have a point in affine coordinates: $(x,y)$.

What should I do when I want to convert to $(X,Y,Z)$ in Jacobian coordinates?
I need it for calculating ECC in a prime field.

When you go from Affine to Jacobian, $X$ and $Y$ stay the same, and $Z$ is equal to $1$

Affine -> Jacobian:

$(X',Y',Z') = (X,Y,1)$

Jacobian -> Affine:

$(X',Y') = (\frac{X}{Z^2}, \frac{Y}{Z^3} )$