DES strength and weakness I'm looking to discover what DES's Strengths and Weaknesses are.

I understand that DES is a block fiestel cipher operating on 64 bit blocks and 56 bit keys (after deduction of 8 bits). And I realise that DES is weak against Brute force in this day and age.

But I'm looking to understand firstly, why is/was DES so strong originally. I.e. how does it defend against common attacks.
And secondly: other than key space, are there any DES specific weaknesses that can be practically exploited? If so, is there an obvious solution to preventing that weakness?

As a side note, I'm not very mathematically inclined so a high level explanation is likely needed, additionally I'm not as interested in Double or triple DES.

The wikipedia article @SEJPM links to is about as high level of an overview as you can really get. We can elaborate on some of the points.

DES is weak against Brute force in this day and age.

Actually, it was weak against brute force pretty much as soon as it was standardized. According to the wikipedia article, the cipher was standardized in 1977. Reading further, in the section about brute force attacks:

  In 1977, Diffie and Hellman proposed a machine costing an estimated US$20 million which could find a DES key in a single day.

So it is arguable that DES was never strong against brute force attacks (the standardized post-NSA consultation version anyways - originally the designers did propose a "real" key size).

Why was DES so strong originally

Let's look at the section of the article for attacks faster then brute force:

Differential cryptanalysis is one area where DES was relatively strong. It's understood that IBM and the NSA both knew about differential cryptanalysis when DES was designed, and chose to keep this information secret. There exists differential attack(s) against DES, but they are not as devastating as they are against some other ciphers (i.e. FEAL)

Resistance to differential attack is determined by differential characteristics of the S-box. The DES s-box was designed with this in mind.
A "differential" is a pair of differences: The difference between two inputs to the function, and the difference between the two corresponding outputs. The probability that this output difference occurs for a pair of inputs with the given difference is the basis for the attack.

Are there any DES specific weaknesses that can be practically exploited?

Continuing further in the same section of the article as before, they discuss linear cryptanalysis.

DES was not known to be written with defense against linear cryptanalysis in mind. It is arguable whether or not the mentioned attacks constitute a "practical" break; These attacks only require known plaintext-ciphertext pairs, which are actually not uncommon in practice (i.e. HTTP GET) and can be practical to obtain, but it does require a large number of such pairs.

It is possible to defend against linear cryptanalysis by choosing s-box values appropriately, similarly to differential cryptanalysis. "Linearity" can be a somewhat nebulous concept and difficult to understand.. Put possibly over simplified, the s-box should be as different as possible from any linear equation. Basically, it should be difficult to come up with a simple equation that accurately approximates the equation of the s-box.

DES has weak keys

A stronger key schedule should prevent weak keys
Weak keys are technically uncommon, but it's arguable that all 56 bit keys are weak

The 64 bit block size could be larger

This is technically more relevant to the security of the mode of operation used with the cipher then the cipher itself


Probability last character sha256 hash A quick question. I want to use the last character of a SHA256 hash (blockhash of a bitcoin block) as my random source. Is 100 /16(amount of different chars) = 6.25% true for all characters or are some characters more likely to be the last char of a hash.

The output of any modern hash is binary. Not all byte values however map to (printable) characters. So what you are looking at is a textual representation of the hash, using an encoding such as hexadecimals (e.g. for sha256sum) or base 64.

You are mentioning the value 16, so lets presume that the output is in hexadecimals. In that case each of the characters 0-9 together with A-F (in upper- or lowercase) is expected with a probability of precisely $1\over{16}$, given that the observer doesn't have any information on the input.

If the input can be guessed and verified then the chance of guessing the output is a perfect 1: the attacker can simply perform the hash calculation himself to calculate the output. You would have to perform HMAC instead of the hash function and keep the key secret.

Depending on your requirements you are probably better off using a known secure PRNG (or DRBG) and seed it using the input.


Why don't table lookups run in constant time? The Wikipedia article on big O notation says that performing a lookup is a constant time operation. So why are lookup tables susceptible to timing attacks?

It mostly has to do with the real world influence of memory caches.

A cache is a small amount of fast memory; when you read from memory, the contents are placed in this fast memory (possibly along with adjacent locations); if you read from the location again, you read it from the fast memory (which, of course, proceeds much faster).

Hence, if you read a location that you've read before, it goes much faster than if you read a location which you haven't; hence, you're not constant time.

Modern CPUs can process data much faster than memory can respond (perhaps by a factor of 100), hence caches are pretty much ubiquitous.  Some lower end microcontrollers might not have them; but they're an exception...


Paillier can add and multiply, why is it only partially homomorphic? I've seen that it's widely accepted that before Gentry's breakthrough (which is not practical yet) in 2009 there were no known full homomorphic encryption scheme.

I've read here in another answer that:

  "...there are many known partially homomorphic cryptosystems, each one
  can either multiply or add numbers."

Now here on some interactive webpage allowing to test Paillier here:

mhe.github.io/jspaillier/

I can do [(A+B)*C], hence doing both addition and multiplication (?).

Why is Paillier not fully homomorphic seen that it can do both addition and multiplication?

It can not do multiplication in the plaintext domain using two ciphertexts. In other words, given $E(m_1)$ and $E(m_2)$, you can not get $E(m_1\cdot m_2)$. You can only get $E(m_1+m_2)$.

Given $E(m_1)$ and $m_2$, you can get $E(m_1\cdot m_2)$ however. But notice that $m_2$ in this case was not encrypted. On the site you reference, $C$ is not encrypted. It is using this feature that I just described.


Having two messages and a result ciphertext, is it possible to know which one was encrypted using One Time Pad? I have two messages $m_1$ and $m_2$ and a result ciphertext $c$, one-time pad was used to create the ciphertext $c$, is it possible to know which message was used to generate the ciphertext $c$?

No, not if the messages $m_1$ and $m_2$ have an identical length.
A one-time pad can produce any ciphertext from a message, so you wouldn't know which message was used.
If the messages differ in length than you would know, because the resulting ciphertext from a one-time pad has the same length as the original message.
This is of course assuming that you don't extend the shorter message with additional information to match it's length to the longer message or vice versa, somehow shorten the longer message.


Can every signature scheme be transformed into a public-key encryption scheme? I am reading about Signing vs. Public-Key encryption and a question pop up in mind that is it possible to transform any signature scheme to a public-key encryption scheme?

No, we know no general way to build a public-key encryption scheme from a signature scheme.
And accordingly, we have some signature schemes with no known way to build a public-key encryption scheme from the same primitives. An example is the eXtended Merkle Signature Scheme, built from symmetric hash and PRF.
[It was not asked, but: I learned from Maeher's comment that we can build a signature scheme from any public key encryption scheme. And I can't tell from memory a public-key encryption scheme that does not have a related  signature scheme built from similar primitives or underlying problem(s)].


Which US standard includes a signature based on Ed25519? Which standard organization (e.g. NIST or ANSI) standardizes signature Ed25519?

In December 2015 there has been a followup on FIPS 186-4 where multiple organizations could respond to a few questions about that document from NIST. Many of them indicated that they would like Ed25519 to be supported (and Brainpool curves and Goldilocks-curve as well). There has been no followup 186-4 yet, so that means it is not in there (yet).

ANSI X9.62 and X9.63 were heavily influenced by Certicom (that use the same set of P-256 etc. curves). It's darn unlikely that they contain Ed2219 by now. There is no sign of it anyway, and the latest official X9.62 predates the official release of the curve by D.J. Bernstein.

In other words, it hasn't been standardized by these US based organizations yet.


Why is SSL on top of TCP? Why is SSL not under TCP (the Transport layer)?

why the SSL is not under the TCP ( Transport layer ) ?

Because SSL can use TCP [1] to transport SSL records, and so SSL relies on TCP as a service.

That is, SSL takes the user data stream, and converts it into a series of records; it then gives these records to TCP to transmit.  On the other side, the receiver's TCP stack gets these records and gives it to SSL to decrypt.

Similarly, TCP takes the data it has been given, and converts it into a series of segments; it then gives these segments to IP to transmit (hence TCP is shown on top of IP).

[1] There's no requirement that SSL has to use TCP; it's just what is used in practice.


BLOCK SIZE in CBC and GCM In case I am using CBC cipher in that case is it must that my encrypted text is in multiple of the BLOCK SIZE?
Is the same true for GCM?

No, GCM does not require padding, nor does it require plaintext to be a multiple of the block size.

GCM is a mode that combines CTR, which is a stream cipher mode, with GMAC authentication, which dave has pointed out does require its inputs to be a multiple of its block size, 128-bits. However the GMAC process simply null pads the ciphertext input, then processes the length of the data as an additional input, to eliminate issues relating to that padding method.

CTR mode turns a block cipher into a stream cipher by encrypting an incrementing counter. GCM is only used with a 128-bit block cipher by design, so the stream cipher outputs are generated in 128-bit increments, and only the needed bits are used to encrypt the plaintext. If the plaintext is 136 bits, 256 bits of stream cipher output is generated, and the first 136 bits are used.

Because GCM is based on CTR, the length of the ciphertext is the same as the length of the plaintext, plus the GMAC authentication tag length, plus the length of the Nonce.


Is PKCS#5 deterministic if both sides use an agreed salt and iteration count In a system were both sides have access to a common secret, and
publicly exchange an iteration count and salt, can a PKCS#5 (Password-based Encryption Standard) algorithm
be used to generate a key suitable for use as a session
key to support AES encryption of a small stream
(<1Mb) of data?

My question is: can both sides run the algorithm--given the "common secret", publicly available salt, and iteration count--and then generate the same key?

The intention is that a new session key would be generated
via this process for each new connection.

Yes. PBKDF2, defined in PKCS#5, is deterministic; you can check its description.


NIST test vectors for RSASSA-PKCS1-V1_5-SIGN with the SHA-256 hash function? I haven't been able to find it on the web anywhere, and I need to check if my implementation of the algorithm is correct. Does NIST provide such a file?

A zip file of test vectors (FIPS 186-2 Algoithm Test Vectors for RSA) can be found at the bottom of the page on NIST's site pertaining to CAVP Testing: Digital Signatures.

This file contains a readme and the test vectors for X9.31RSA,  RSA PKCS#1 Ver 1.5, and RSA PKCS#1 RSASSA-PSS signature generation. It looks like it does contain vectors for SHA-256.


Cost of multiplication when e is randomly selected. RSA Using schoolbook multiplication (which has cost $\mathcal{O}(n^2)$) to multiply two $n$-bit numbers)

what is the cost of computing an RSA encryption with $e = 3$?
What is the cost if $e$ is chosen randomly in the range $\{3, 5, 7, \ldots, \varphi(N) − 1\}$?

Since this is schoolbook multiplication and homework, I'll give some hints.

Note that, your question is missing an important part, which algorithm we use in the modular exponentiation?

We don't have just multiplications due to the exponentiation operation. We also need the modular reduction. See Modular Exponentiation for general detail.

$$ m^e = c \bmod n$$

You may apply either taking the exponentiation than modular reduction, which will cause huge intermediate values, or you can use apply multiple and reduction paradigm. For this in general, Exponentiating by Squaring  algorithm is used.
Now, reduction, in this case, requires modular reduction that. You may or may not add this into your calculations.
for the second part, hint; when using the Exponentiating by Squaring we use the bits of the exponent.


Non-Interactive Zero-Knowledge-Proof for discret Logarithm? In a Non-Interactive $Zero-Knowledge-Proof$, the challenge is chosen
by the Prover.

I am trying to find a Non-Interactive Zero-Knowledge-Proof based on the following problem:

DISCRETE LOGARITHM

Input: Prime number $p$, generator $g$ of $Z^{*}_{p}$ , and $y\in Z^{∗}_{p}$ .

Question: find $x \in \lbrace1, . . . , p − 1\rbrace$ with $y ≡ g^{x}\;mod\;p$?

It seems, what you are looking for is a Non-Interactive Zero Knowledge Proof of Knowledge (NIZKPok) of a discrete logarithm.

The Schnorr identification scheme is an (interactive) ZKPoK and can be transformed in to a non interactive one (in the random oracle model) using the Fiat-Shamir transformation.

It works in any group, is perfectly sound and computationally zero knowledge under the discrete logarithm assumption for that group in the random oracle model.

http://publikationen.stub.uni-frankfurt.de/files/4280/schnorr.pdf

http://en.wikipedia.org/wiki/Schnorr_signature


How to convert a set of sequential integers into a set of unique random numbers? I have a set of sequential and non-duplicate integers which I would like to convert into a set of non-duplicate random integers.

What I want to achieve is this  - I have a list of sequential numbers like below

[1, 2, 3, 4, 5, 6, 7, 8, 9]

This list is going to be quite big in reality e.g. 100 million

I want to shuffle this list multiple times in order to rearrange the numbers in the list. Each shuffle should give me a new sequence in such a way that, if I pick a number at a particular position in the list after each shuffle, I should never get a duplicate.

For example, if the above list is shuffled three times, I get the following three sequences after each shuffle

shuffle 1 --> [9, 3, 4, 1, 7, 2, 6, 5, 8]
shuffle 2 --> [8, 2, 7, 5, 4, 6, 3, 9, 1]
shuffle 3 --> [1, 9, 6, 7, 5, 3, 4, 8, 2]

In the above lists, if you pick a number at any position, say 2,  from all the sets, you never get any duplicates. You will get a duplicate if you pick position 2 from the first sequence and position 5 from the third set and this is fine.

For some reason, I feel that there should be a cryptographic function for this kind of shuffling to which I can pass my input sequence and I get a shuffled sequence back as described above. Is there any? I have looked at LFSR but just not sure if that solution works in this case.

Let $P$ be an arbitrary random fixed permutation of $n$ elements. Each of the desired shuffle can be generated from the previous as follows:

apply $P$ to the previous shuffle (or the initial set/vector, the first time);
rotate the result one to the left;
apply $P^{-1}$ to the result.

This will have the property asked by "if I pick a number at a particular position in the list after each shuffle, I should never get a duplicate". Proof: in applying the shuffle sequentially, the next application of $P$ with cancel the previous application of $P^{-1}$. It follows that the rotation will operate on the result of the previous rotation, thus that the property is met at the output of the rotation. It follows that the property is met after applying $P^{-1}$, thus at the output.

We can iterate this $n-1$ times (if we do it once more, we are back to the original, thus will get something clearly sequential, thus in the context distinguishable from the required "random integers" with great ease and near certainty).

We can use the Fisher-Yates shuffle to generate $P$. Or, if keeping it in memory is an issue because of size, we can use a cipher to implement $P$, and its reverse; that's a standard trick of Format Preserving Encryption.

Any isolated shuffle is indistinguishable from a random shuffle, but even the first two shuffles generated are distinguishable from random shuffles with the required property (which perhaps is undesirable, if not clearly prohibited).

If we remove the requirement that the same operation is iterated to go from one shuffle to the next (we are told that we can), we can do something better: pick three arbitrary random permutations $P$, $Q$, $R$ of $n$ elements, and get the $(j+1)^\text{th}$ shuffle as

apply $P$ to the initial state
rotate the result $Q(j)$ times to the left, where $Q(j)$ is the $(j+1)^\text{th}$ element of the vector obtained by applying $Q$ to the vector of the first $n$ non-negative integers; or, otherwise said, $Q(j)$ is an integer $q_j$ with $0\le q_j<n$, such that $0\le i<j<n\implies q_i\ne q_j$.
apply $R$ to the result.

This time, we can obtain $n$ individually random-looking shuffles, which obviously is the maximum. Again, Fisher-Yates or FPE can be used to implement $P$, $Q$ and $R$. Even knowing the initial shuffle and the rank of any two generated shuffles, I vaguely conjecture (without proof) that they are indistinguishable from two random shuffles meeting the property asked. By a counting argument, three generated shuffles are distinguishable, at least by an unbounded adversary; thus we are far from generating the best randomness possible.

I have asked the question in more academic terms there.

Here is sample code in Java for the second method. Class MyCipher implements a Pseudo Random Permutation of size elements, made using cycling (arguably the simplest efficient FPE technique), and a basic iterated block cipher. Class MyShuffledArray is then a straightforward implementation of the technique that I propose. The code is usable for large parameters, and uses constant memory.

import java.util.Random;
import java.security.SecureRandom;

public class MyShuffledArrayDemo {

    // MyCipher implement a PRP of size elements
    static class MyCipher {
        private static final int R = 40;        // number of rounds
        private final int size;                 // size of PRP
        private final int mask;                 // bit mask for block
        // 0 < size <= mask+1  and mask+1 is a power of 2
        private final int rish;                 // right shift count
        private final int[] rk = new int[R];    // rk for each round

        // Constructor from rng source
        private MyCipher(int size, Random rng) {
            assert size>0 : "MyCipher.size must be positive";
            int i,j;
            // find block cipher width j in bits; and mask
            for (j = 3, i = 8; j<31 && i<size; ++j)
                i += i;
            this.size = size;
            this.mask = i-1;    // one less than a power of two
            this.rish = j*3/7;  // shift count, at least 1
            i = R; do
                rk[--i] = rng.nextInt();
            while (i!=0);
        }

        // Implement PRP, using a basic iterated block cipher and cycling.
        // Input and output are a non-negative integer less than size.
        private int Perm(int x) {
            assert x>=0 && x<this.size : "bad input to MyCipher.encrypt";
            do { // cycling loop; executed on average less than twice when size>4
                int r = R;
                do {// Round loop; each losslessly transforms x by
                    // - multiplying by 0xADB modulo a power of 2
                    // - adding a round key
                    // - XORing x with a right-shifted version
                    // Here, x<= mask  and mask+1 is a power of 2
                    x = (x*0xADB+this.rk[--r]) & this.mask;
                    x ^= x>>>this.rish;
                    }
                while (r!=0);
                }
            while (x>=this.size);
            return x;
        }

    } // class MyCipher

    // MyShuffledArray implement a virtual square array where each line and column appears to be a random permutation
    static class MyShuffledArray {
        private final int size;         // dimension
        private MyCipher P,Q,R;

        // Constructor from rng source
        private MyShuffledArray(int size, Random rng) {
            assert size>0 && size<=0x40000000: "MyShuffledArray.size must be positive and at most 1073741824";
            this.size = size;
            P = new MyCipher(size, rng);
            Q = new MyCipher(size, rng);
            R = new MyCipher(size, rng);
            }

        // Implement the virtual array
        private int Get(int col, int lin) {
            return R.Perm((P.Perm(col)+Q.Perm(lin))%this.size);
            }

        } // class MyShuffledArray

    // Example use
    final static int START_OF_RANGE  = 1;
    final static int END_OF_RANGE    = 9;
    final static int NUMBER_OF_LISTS = 3;
    final static int size = END_OF_RANGE - START_OF_RANGE + 1;

    public static void main(String[] args) {
        MyShuffledArray myShuffledArray = new MyShuffledArray(size, new SecureRandom());
        for (int j = 0; j <NUMBER_OF_LISTS; j++) {
            for (int i = 0; i <size; i++)
                System.out.print(String.format(i==0?"[%d":", %d", myShuffledArray.Get(i,j) + START_OF_RANGE));
            System.out.println("]");
        }
    }
}

This answer identifies that we are generating a latin square. Here is a literature survey.


Why is it a security problem that two RSA moduli are not co-prime? I found this security problem, for example:

Alice has an RSA public key: $e = 37$ and $\phi$ (totient, $N_A = (pa-1)(qa-1)$) is $55$, so the key is $(37, 55)$.
Bob has an RSA public key: $e = 37$ and $\phi$ (totient, $N_B$ = $(p_B-1) (q_B-1)$) is $77$, so the key is $(37, 77)$.

So I see that $\gcd(55, 77)$ is $11$. But what does it mean for the security issues?

It sounds like it is then much simpler factorize the totient. But how? I can see that $55 = 11 \times 5$ and $77 = 11 \times 7$ also without calculating the gcd. Even when dealing with big numbers (say 2048 bits), what does it help me with to find a gcd not equal 1? $N_A$ could be a multiplication of 100 different prime numbers and of course it will have commonalities with some other totient values (say $N_b$), but the commonality may not be the whole $p$ or $q$.

Say:

Na = (pa-1)*(qa-1) = (a*b*c*d*e*f)*(g*j*i*k)
Nb = (pb-1)*(qb-1) = (l*m*n*e*f)*(r*g*u*v*w*x*y*z)

so the gcd of Na and Nb is e*f*g. Where does it help me to find the initial pa, qa, pb, qb?

The public key is actually $(n,e)$ where $n = p \, q$: it's the modulus, which is the product of the two primes, that appears in the public key.

Suppose that you have two public keys $(n_A, e_A)$ and $(n_B, e_B)$ with $n_A \neq n_B$, and that $\gcd(n_A, n_B) \neq 1$. You have a common divisor of both $n_A$ and $n_B$. But $n_A$ and $n_B$ have only two divisors each, the two primes. Therefore $\gcd(n_A,n_B)$ is one of the secret primes of both keys, and the other secret primes are trivially $n_A / \gcd(n_A,n_B)$ and $n_B / \gcd(n_A,n_B)$.

This shows that it's critical that in an RSA key, both primes are unique.

Knowing a factor of the two totients may or may not reveal the private key. If the factor you have is $4$, that doesn't give you any information: $(p-1)(q-1)$ is always a multiple of $4$. If the factor you have happens to be $p-1$ or to let you find $p-1$, that's obviously a problem. But since the totient is not normally exposed anywhere, this isn't a common concern.


Is there a floating point CSPRNG? Is there a floating-point CSPRNG that operates, natively, using floating point operations?

Looking for a CSPRNG that's very fast on GPUs, and would be hard for a CPU to beat.

EDIT: Floating point doesn't matter too much.   Specifically, I'm looking for something for which GPUs or FPUs are, by far, the optimal hardware to use: as opposed to custom hardware, because the operations used are already heavily optimized on GPU.

My understanding is that floating-point-operations (FLOPS) are probably the best candidate here.    (It seems to me that most chaotic attractors can be trivially run using FLOPS.)

Are you sure?

Float operations are very hard to reproduce in diverse environments.

Do you round towards positive, negative or zero? Do you handle denormals or just treat them as zero? What about dividing by zero?

I'm sure we would love to have that problem with every cipher we implement.

  Looking for a CSPRNG that's very fast on GPUs, and would be hard for a CPU or FPGA to beat.

To beat FPGA... don't do anything. There are problems that are slow on CPUs & GPUs, but otherwise you won't have as big FPGA that can reach nearly same frequency. If that wasn't case we wouldn't have processors, just builtin FPGAs that switch between GPUs and CPUs...

To beat CPU... just use something that uses a lot of simple math... +,-,xor,ror,rol etc. This doesn't have to be on floats, ints will suffice. Chacha20 might work well on GPUs. Note that this won't be slow on CPUs, it will just be faster on GPUs because it parallelizes well (and this is always case, because CPUs are complex beasts that can do more than GPU, except there just isn't enough of it for raw number crunching at that speed).

Honestly, most cryptographic primitives will be faster on GPUs because they frequently rely on number crunching, and rarely do any significant memory access and/or branching.

Just remember that there are still ASICs that will always win against you, because they are exceptionally good at number crunching (and if you are looking to outrun them, argon2 and CPU are your friends).


How does one scale encryption strength upwards from 256-bit? I have seen many examples of encryption up to about 256-bit. But how does one programmatically scale the logic upwards in a language such as PHP or Java to say 1024-bit or even 4096-bit and higher?

Are there any websites that explain the workings of a very large encryption on a modern 64-bit computer? For example what kind of numbers (Long Int, Double, etc.) would one use and how can one even extend that range and still keep it computable to the computer?

Would this scaling's security be compromised by the limitations of the processing power available, i.e. 64-bit processor?

I understand that time is a factor in very large encryptions, but in this case time doesn't matter that much.

As @David Schwartz said, using something like 3AES should work to scale up the security (but see my comment on the meet-in-the-middle attack). But seriously, why would you even need 512-bits of security in a symmetric algorithm? According to the analysis on wikipedia it would take 50,955,671,114,250,100,000,000,000,000,000,000,000,000,000,000,000,000 years to bruteforce 256 bit AES (given a few assumptions on speed). I doubt you have any data that needs to be secured for that long.

As far as whether the CPU limits the security strength, it doesn't. There are libraries out there which provide "infinite" precision numbers (i.e., gmplib for c/c++, BigInteger and BigDecimal for Java, etc). For more on computing with large numbers, see chapter 14 of the Handbook of Applied Cryptography (HAC). Internally, these libraries use things like long long int or even plain int stored in an array. HAC has the algorithms.


How to prove a lemma that is based on phi-hiding assumption? Assume that the $\phi$-hiding assumption is true, i.e. that for a composite number $m$, a PPT adversary A cannot distinguish between a prime $p_0$ that divides $\phi(m)$ and another prime $p_1$ that doesn't divide $\phi(m)$.

How to prove that a PPT adversary B cannot distinguish $q_0 = (r \cdot p_0) \bmod \phi(m)$ and $q_1 = (r \cdot p_1) \bmod \phi(m)$, where $r$ is a random integer between 1  and $\phi(m)$ inclusive?

I know the basic idea is to let A construct $q_0$ and $q_1$ and give them to B. But the issue is that A doesn't know $\phi(m)$.

There exists a distinguisher that works with nontrivial advantage, $O(1/\log \phi(m))$.

This is because $q_0$ must be a multiple of $p_0$; however $q_1$ is a random value between $0$ and $\phi(m)-1$.

Hence, the distinguisher is "test both for primality, if one is prime, say that one is $r \cdot p_1 \bmod \phi(m)$"

$q_1$ is a random value, and hence it will be prime with probability $O(1 / \log \phi(m))$.

$q_0$ is a value $k p_0$, for a random $k \in (0, \phi(m)/p_0)$; hence it will be prime only if $k=1$, which happens with tiny probability $p_0 / \phi(m)$

$1 / \log(\phi(m)) \ggg p_0 / \phi(m)$, and hence this is an effective distinguisher.

If the adversary is given several rounds, say, multiple values $q_0, q'_0$ and $q_1, q'_1$, much better distinguishers can be constructed.


what are the plaintext's for the RC4 stream cipher test vectors in RFC6229? https://tools.ietf.org/html/rfc6229 has stuff like this:

Key length: 40 bits.
 key: 0x0102030405

 DEC    0 HEX    0:  b2 39 63 05  f0 3d c0 27   cc c3 52 4a  0a 11 18 a8
 DEC   16 HEX   10:  69 82 94 4f  18 fc 82 d5   89 c4 03 a4  7a 0d 09 19
 DEC  240 HEX   f0:  28 cb 11 32  c9 6c e2 86   42 1d ca ad  b8 b6 9e ae
 DEC  256 HEX  100:  1c fc f6 2b  03 ed db 64   1d 77 df cf  7f 8d 8c 93
 DEC  496 HEX  1f0:  42 b7 d0 cd  d9 18 a8 a3   3d d5 17 81  c8 1f 40 41
 DEC  512 HEX  200:  64 59 84 44  32 a7 da 92   3c fb 3e b4  98 06 61 f6
 DEC  752 HEX  2f0:  ec 10 32 7b  de 2b ee fd   18 f9 27 76  80 45 7e 22
 DEC  768 HEX  300:  eb 62 63 8d  4f 0b a1 fe   9f ca 20 e0  5b f8 ff 2b
 DEC 1008 HEX  3f0:  45 12 90 48  e6 a0 ed 0b   56 b4 90 33  8f 07 8d a5
 DEC 1024 HEX  400:  30 ab bc c7  c2 0b 01 60   9f 23 ee 2d  5f 6b b7 df
 DEC 1520 HEX  5f0:  32 94 f7 44  d8 f9 79 05   07 e7 0f 62  e5 bb ce ea
 DEC 1536 HEX  600:  d8 72 9d b4  18 82 25 9b   ee 4f 82 53  25 f5 a1 30
 DEC 2032 HEX  7f0:  1e b1 4a 0c  13 b3 bf 47   fa 2a 0b a9  3a d4 5b 8b
 DEC 2048 HEX  800:  cc 58 2f 8b  a9 f2 65 e2   b1 be 91 12  e9 75 d2 d7
 DEC 3056 HEX  bf0:  f2 e3 0f 9b  d1 02 ec bf   75 aa ad e9  bc 35 c4 3c
 DEC 3072 HEX  c00:  ec 0e 11 c4  79 dc 32 9d   c8 da 79 68  fe 96 56 81
 DEC 4080 HEX  ff0:  06 83 26 a2  11 84 16 d2   1f 9d 04 b2  cd 1c a0 50
 DEC 4096 HEX 1000:  ff 25 b5 89  95 99 67 07   e5 1f bd f0  8b 34 d8 75

So it's pretty obvious what the key is but what is the plaintext supposed to be? I assume each the DEC part of each line corresponds to the offset?

RC4 is some kind of pseudo random number generator. You input a key (seed) and now can get a stream of pseudo random numbers. The values here are this numbers, always a byte at a time.

Unlike a block cipher, you don't have a plaintext. You use this key stream to add it to the plaintext to get the ciphertext. "Adding" can be done with XOR, because that's pretty easy and the most common way.

Yes, DEC means the offset. The first 16 values are the 16 output bytes of RC4 with the mentioned key. The next 16 values are the output bytes after the first 16. The third line has the output bytes after the first 240 bytes.

We could say that the plaintext was all zero bits. This would lead to the ciphertext being the key stream.

This online tools allows to encrypt / decrypt something with RC4. Switch the input and the key to hex numbers, write only zeros as input text and then copy the key into the key field (without the 0x at the start). Now you can see exactly the mentioned numbers as output of the function.


cbc - why not like this? what's wrong? ok, well... first: it's a "just for fun" question. I don't have a project dealing with this... I've simply a bit time and would like to talk a bit about some (maybe stupid) possibilities and try to learn something...

I always thought (before I was looking at the algorithm) that algorithms like cbc provide security against modifications of the encrypted data (so the idea was -> if you can decrypt the last block, everything must be fine) ... obiousely that's not the case. And here are my questions:

a) why? ... why wasn't it designed like this? Today we need MAC's to confim the integrity. So, we need 2 different algorithms to achieve this goal... wouldn't it be easier if one algorithm would do all of it?

b) ... could CBC be modified in a way so that it would support it? In this case my "security Tag" could be ... well... don't know... maybe sending the first block again? If it matches, everything was fine? Or does it have a huge flaw I don't see right now? ... or, is it simply not practical because of the computational power it needs or... lack of parallelization... things like that...

(I modified the pictures from Wikipedia to show the first idea that crossed my mind)

why? ... why wasn't it designed like this? Today we need MAC's to confim the integrity. So, we need 2 different algorithms to achieve this goal... wouldn't it be easier if one algorithm would do all of it?

Yes, but the fact that a MAC is almost always required is simply an idea that surfaced later. MAC constructions themselves surfaced later than ciphers. Before them there was a focus on error propagation and cribs (checksum values also encrypted).

  ... could CBC be modified in a way so that it would support it? In this case my "security Tag" could be ... well... don't know... maybe sending the first block again? If it matches, everything was fine? Or does it have a huge flaw I don't see right now? ... or, is it simply not practical because of the computational power it needs or... lack of parallelization... things like that...

There are single pass algorithms such as OCB, but it is patented. GCM is another one which has a relatively cheap operation over all the blocks, so it is often called a 1,5 pass algorithm.

As you don't describe your algorithm well we cannot analyze it. Your altered CBC scheme obviously doesn't work. The way you XOR you can easily get repeat ciphertext for instance, leaking information about the plaintext. For instance, just encrypt all zero plaintext. A mode of encryption must be secure without any restrictions on the plaintext.

A MAC should be over all the data you need to protect (encrypted or not). I don't see that in your scheme (then again, I don't see any tag displayed in your scheme).


The attacker model of the Lucky13 attack in TLS Lucky13 is a timing attack against the MAC in the CBC MAC-then-encrypt ciphersuites. In the attack's page:

  The attacks involve detecting small differences in the time at which
  TLS error messages appear on the network in response to
  attacker-generated ciphertexts.

My question is: Can a passive adversary perform Lucky13? In other words, I need to know if Lucky13 attacker's model is active MitM or passive network attacker who just collect traffic and perform analysis afterwards?

The Lucky13 article on Our Results;

... attacks can be mounted by a standard man-in-the-middle (MITM) attacker who sees only ciphertext and can inject ciphertexts of his own composition into the network.

Definition of passive and active MTIM from sll.com

Passive MITM: In a passive MITM attack attackers ‘tap’ the communication, capturing information in transit without changing it.
Active MITM: If attackers attempt to modify or tamper with the information itself they are committing an active MITM attack. A very common way to launch a MITM attack is by creating a fake node on a publicly-available computer network, such as a coffee shop's WiFi network.

Injection is an attempt to modify therefore it is an active MITM attack.
on the discussion;

We reiterate that the attacks are ciphertext-only, and so can be carried out by the standard MITM attacker, without a chosen-plaintext capability.

Chosen plaintext attack means; the attacker obtains encryption of plaintexts of his choice. So, in Luck13, the attacker only used ciphertext that they can obtain and injected them into the network.


Ranking "amount of randomization" in a sequence I'm facing the problem of implementing pseudo random bit generator (PRBG) on a very low power device. NIST.SP800-22 "Statistical test suite for Pseudo Random Generators" suggests a suite of 15 tests for randomness.

Is there a way to use those tests as "randomness measures" except from pass / fail?

That is, suppose you want to do changes in your random generator, and to measure, whether you improved the randomness or not. The NIST suite suggests a way to decide whether you are random or not, but its hard to extract the information of "improvement": For two different algorithms, it may happen that for some tests the first gives higher p-value, for other tests the same PRBG gives lower p values, although both pass all tests. So'

is there some "measure of amount of randomness" test, or or how can NIST tests turn to be such?

The various nist tests look for patterns which should not be present in random data.
For any such pattern, e.g imbalance, repetition etc. you can ask youself what is he likelyhood of this strength imbalance or worse occuring in random data. this is the pValue.
If we toss a coin multiple times we can count heads and tails. The closer they are to even the better. We can quantify this as probability. We then look at longer sequences and also expect them to show up more or less with equal frequency and again we can calculate pValue to quantify how likly discrepencies found are to be chance.
Most Nist tests already come with this built in.
We also like to analyze the cycle size of PRNGs even when they are too long to detect in a quick black box test this is another measure of "randomness".
Remember these tests are not sufficient for a PRNG to be secure. And though failing any means the stream is distinguishable from random it may still be decent for some cryptographic operations (Solitaire cipher as an example of a biased yet reasonably secure stream cipher).


inverse element in Paillier cryptosystem As I know, in Paillier cryptosystem, the encryption $c$ of a message $m$ is calculated as $c=g^m r^n \bmod n^2$.

Now, I am wondering if I can derive $g^m  \bmod n^2$ given that I know $c$, $r$, and $n$?

It seems that the "$\bmod\ n^2$" operation does not constitute a finite field. Not every element has the corresponding multiplicative inverse in $\mathbb Z^*_{n^2}$. So, it seems not always impossible for to find a proper $(r^n)^{-1}$ to get $g^m=g^m r^n (r^n)^{-1} \bmod n^2$

If so, can we find or limit the use of $r$ so that $(r^n)^{-1}$ can always be found?

Yes. $r^n$ needs to be coprime with $n^2$. The only elements which have don't an inverse modulo $p^2 q^2$ are all multiples of $p$ and all multiples of $q$, so we just require $\gcd{(r^n, p)} = \gcd{(r^n, q)} = 1$.

$\implies \gcd{(r^n, n}) = 1$

Clearly, if $r$ is coprime to $n$, then $r \times r \times \cdots \times r ~ (n ~ \mathrm{times})$ will also be coprime to $n$, so:

$\gcd{(r, n)} = 1$

The probability of a random $r \in \mathbb{Z}_n^*$ not satisfying the above is equal to $\frac{n - 1 - \varphi{(n)}}{n - 1} \to 0$.

Assuming you use sufficiently large $n$, the probability of selecting a bad $r$ (one that cannot be inverted, according to your criterion) is smaller than the probability of your hardware failing and screwing up the calculation while you getting hit by a dozen lightning bolts simultaneously. I think you'll be fine.


Point Matching Function for Curve 25519 Does anybody know a point-matching function for curve 25519?
Or has a straight-forward way how to derive any arbitrary point-matching function?
It should be like a reversible mapping from and to a 128+ bit number to and from points on the Curve 25519.
The aim is actually to have the point being on the edwards form of the curve.

This is what Elligator was designed for.
Specifically, the Elligator 2 is suitable for Curve25519 which maps a 32 bytes integer to a point on the curve.
As for implementations of this map:

libsodium: the implemented function maps a $32$ bytes vector to a point that belongs on the prime order subgroup on the Edwards form of Curve25519, by multiplying by the curve cofactor; but not the inverse map;
Monocypher implements the map and its inverse, but the points seem to be on the Montgomery form so it might be needed to convert the points to the Edwards form if necessary, and additional code in Python is present for Edwards form of Curve25519;
C implementation of elligator 2: words for Curve25519.

For information, there is a version made for prime order curves in Weierstrass form called Elligator squared.
Thanks to xorhash for additional links.


Security Strength of BigInteger vs elliptic curve parameter value Choosing 512 bit prime biginteger as secret value as in RSA
Choosing TypeA curve (rbits=256,qbits=512) and setting secret value by randomly selecting from $Z_r$ value
I wanna know which one has more security strength even though I know 128 bit security can be obtained with 256 bit elliptic curve and 3072-bit RSA keys.I need some detailed explanation.When we set rbits=256 bits, is it 256 bit elliptic curve? Or when we set qbits=256 bits, is it 256 bit elliptic curve?

A Type A curve has embedding degree 2. That means via the pairing we get an homomorphism from an ECC curve of bit length k to a finite field with 2 k bits (i.e. qbits).

You have to compare the complexity of:

calculating the discrete logarithm in the EC group with k bits and without using the paring homomorphism (i.e. by a generic algorithm)
calculating the discrete logarithm in the finite field with 2k bits by the number field sieve.

and take the minimum of both.

The complexity of a generic ECC DL algorithm is $2^{k/2}$

The complexity of the number field sieve for a finite field with k bits is approximately
$$\lambda (k) := \exp(1.9 (k \log (2))^{1/3} \log(k \log (2))^{2/3})$$

Therefore we have to compare $2^{k/2}$ with $\lambda (2k)$.

For big values of k, surely the factorisation in the finite field is faster then the generic ECC algorithm. So let us calculate the break-even point:

$$min_k (\lambda (2 k) = 2^{k/2})$$

This gives $k \approx 65$.
From that value of k on we can calculate the running time complexity as $\lambda (2k)$

For instance, an elliptic Type A curve with 256 bits gives you a strength of 63 bits only .

Please take this result with a grain of salt, because I have omitted the $o(1)$ term.

For real cryptographic use its maybe a better idea to use the table from the NIST SP 800-57 document:

Strength  RSA modulus size
      80        1024
     112        2048
     128        3072
     192        7680
     256       15360

For instance, that would have the following security implication:
In order to get a strong security (i.e. strength >100) type A curve, you need a finite field size of 2048 bits. This means your type A curve must have rbits=1024 and qbits=2048.


Strange MAC algorithm I'm working with a payment provider which uses the following algorithm for signing messages:

The merchant is securely given a secret key k, known to them and the payment provider only.
EDIT: Usually the key is quite long.
The payment is implemented by using a redirect, and the merchant later receives callbacks containing information about the success or failure of the payment operation. The merchant considers this information trustworthy. Here is an example of a successful payment callback for order no. 1234 and a merchant hosted at example.com:

example.com?orderID=1234&paymentStatus=SUCCESS&...&signature=abcd
The message m which is signed is formed in the following way:

orderid=<..>|paymentStatus=<..>|...
The signature algorithm S(m,k) is chosen to be: signature=H(m||k) (m||k means m concatenated with the secret key k) where H is a hashing function, in this case MD5.
The verification algorithm is V(signature, m, k) and returns true only if H(m||k) = signature.

As far as I understood the inner workings of MD5 if the signing algorithm was S(m,k) = H(k||m) then this would be totally insecure because if an attacker knows H(k||m) she may be able to calculate H(k||m||m') where m' is a message of her choice - this would mean that the signature is vulnerable to both existential and selective forgery. Correct? But deliberately or not the algorithm is S(m,k) = H(m||k) - the key is put last in the concatenated string.

So far I cannot think of exploitable vulnerability in this protocol (I'm not considering the problems inherent to MD5). Any ideas, is this secure enough?

We can attack the MAC defined by: MAC(k,m)=MD5(m||k), in a chosen-messages setup, basically because MD5's collision-resistance is broken.

The adversary chooses m and m' of the same length $b\ge64$ bytes, differing only in their first $\lfloor b/64\rfloor$ 64-byte blocks, such that there is a collision after hashing these blocks of m and m'. If follows that MAC(k,m)=MAC(k,m'), and also MAC(k,m||m")=MAC(k,m'||m") for any m". We know various efficient techniques to create such m and m', with $b$ down to 128 or even 64 bytes, including with a moderate degree of constraints:

Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu: Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD (rump session of Crypto 2004, and in Cryptology ePrint Archive)
Xiaoyun Wang, Hongbo Yu: How to Break MD5 and Other Hash Functions (in proceedings of Eurocrypt 2005)
Vlastimil Klima: Tunnels in Hash Functions: MD5 Collisions Within a Minute (in Cryptology ePrint Archive, 2006)
Marc Stevens: Single-block collision attack on MD5 (in Cryptology ePrint Archive, 2012, and here with code and example)
Tao Xie, Fanbao Liu and Dengguo Feng: Fast Collision Attack on MD5 (in Cryptology ePrint Archive, 2013)

If instead of MD5 we had an unbroken Merkle-Damgård hash like SHA-256, or a hash secure in the random oracle model (which SHA-256 is not quite, for it has the length-extension property), then we'd basically have no known attack, as discussed in this question.


Understanding double hash and 0 block prepending to mitigate length extension attacks So, reading the chapter about hash functions from the book "Applied Cryptography". There's a point where, as a conclusion, the construction:

SHA-X(SHA-X(0^b || m))

Saying:

  Prepending the message with a block of zeros makes it so that, unless something unusual happens, the first block input to the inner hash function im hd is different than the input to the outer hash function.

The thing is I don't quite get it.

Forgetting about the prepending of a block of 0's to the inner hash function, let's state that it's clear that:

  If we find a collision for the output of the inner hash function, then we get a collision for the output of the outer hash function.

So, how is it different prepending a block of all 0's to the message to mitigate length extension attack?

If I have the messages:

m=m1..mk
m'=m1..mk,mk+1

When prepending a block of 0's to both of them as input for the inner hash function will give us the same "problematic" situation we have with length extension attacks. We will have a partial message collision up to

0b||m1..mk

And then we have mk+1 "to play" and be able to generate a length extension attack...

I'm aware that there's obviously something wrong with my reasoning, so I'm hoping someone can give me a hand and point out what it is.

The objective of the construction $H'(m)=H(H(0^b\mathbin\|m))$ is not to strengthen $H$ against collision attacks; as noted in the question, that does not work.

The objective is preventing a length-extension attack. In such attack, an adversary knows the hash $h=H(m_0)$ of some unknown $m_0$, and the length $l$ of $m_0$. Then from $h$ and $l$ s/he constructs a short $m_1$ such that for any given $m_2$, it is easy to compute $h'=H(m_0\mathbin\|m_1\mathbin\|m_2)$. Essentially, $m_1$ is the padding internally appended to $m_0$ in the normal computation of $h=H(m_0)$, so that the internal state of the hash after hashing $m_0\mathbin\|m_1$ is the known $h$.

A length-extension attack can matter in practice, e.g. $F_k(m)=H(k\mathbin \|m)$ is insecure as a Message Authentication Code if $H$ has a length-extension property, as SHA-1, SHA-256 and SHA-512 do. That's one reason to use HMAC to build a MAC or Key Derivation Function.

If the $0^b$ is the question's construction was absent, as in $H'(m)=H(H(m))$, we'd have the property: $\forall m,H'(H(m))=H(H'(m))$. We can construct some (largely artificial) protocols which would be secure for $H$, but are insecure for $H'$ due to that property; and correspondingly, that property makes some security proofs hairy, impossible, or weaker. With $H'(m)=H(H(0^b\mathbin\|m))$, that or similar properties do not hold, which is good for simpler/stronger security proofs.


Is encrypted e-mail sent over TLS 1.3 a form of "forward secrecy" (similar to something like Signal)? One common complaint about GPG-encrypted e-mail is that it doesn't provide forward secrecy; however with opportunistic TLS becoming increasingly common in both IMAP and SMTP, it's not unreasonable to expect that e-mail sent from one message transfer agent (MTA) to another is done over a TLS protocol that utilizes (EC)DHE—by far the biggest e-mail provider, Gmail, is configured to send and receive e-mail this way by default. Thus if communication between mail user agents (MUAs) and message submission agents, MUAs and message delivery agents, and MTAs and MTAs is done using such a protocol (e.g., TLS 1.3); then even if the GPG key that was used to encrypt the e-mail is fairly static, shouldn't this constitute as "forward secrecy"?

It seems to me that the only way to decrypt someone else's e-mail is if the end-point device has been compromised. This is also true for Signal though. Am I mistaken?

Forward secrecy is a confusing term that should be abandoned, especially the meaningless but value-loaded variant ‘perfect forward secrecy’.  It is especially confusing because it is often associated with any protocol that does ephemeral DH key agreement, like TLS—even if, as in TLS<1.3 session resumption, the keys capable of decrypting transcripts of past sessions are deliberately kept around for long periods of time.  Instead, you should ask: Who has the data, who has the decryption keys, and when can the decryption keys be erased?

Suppose Alice decides she wants to send a message to Bob, and types it into her laptop.

Let's look at the flow of data in email.

Alice's laptop sends the message to Alice's MTA outgoing.oohay.com over the internet, encrypted.

The decryption keys between Alice's laptop and Alice's MTA outgoing.oohay.com can be erased after this step, but now outgoing.oohay.com necessarily has a plaintext copy of the message.

outgoing.oohay.com sends the message to Bob's MTA incoming.oogleborg.com over the internet, encrypted.

The decryption keys between outgoing.oohay.com and incoming.oogleborg.com can be erased after this step, but now incoming.oogleborg.com necessarily has a plaintext copy of the message.

A couple days later, after Bob gets back from vacation, he logs into his workstation and downloads the message from incoming.oogleborg.com over the internet, encrypted.

The decryption keys between Bob's workstation and incoming.oogleborg.com can be erased after this step, but erasing the keys for the TLS sessions doesn't help with the plaintext copies that were left on Oohay and Oogleborg's servers!

If Alice's message is an OpenPGP-encrypted message, then you also need to answer: When does Bob erase all copies of his decryption key?  If it's not before Bob's laptop is compromised, then even if Bob has deleted old email messages, an adversary can use Bob's decryption key to decrypt ciphertexts of old email messages.

In contrast, here's the flow in Signal.

Alice's laptop encrypts the message and some ratcheting administrivia using her current key for Bob, and sends it to the Google mothership for distribution.

The Google mothership necessarily has a ciphertext copy of the message, and needs no keys.
Alice can now turn her ratchet and erase the key that would allow decryption of the ciphertext stored on the Google mothership.
After this point, if Alice has followed the protocol, only Bob has the key to decrypt the ciphertext or any way to derive it.

A couple days later, after Bob gets back from vacation, he logs into his workstation and downloads the ciphertext from the Google mothership.

If the ratcheting administrivia shows the messages are in order, Bob can now turn his ratchet and erase the key that would allow decryption of the ciphertext stored on the Google mothership.  (If the messages were delivered out of order, Bob has to hang onto the decryption key for a little longer.)
After this point, if Alice and Bob have followed the protocol, nobody has the key to decrypt the ciphertext or any way to derive it.

If Bob decides to delete old Signal messages (e.g., with ‘disappearing messages’, which are, of course, voluntary requests for the peer to respect, and which it is good etiquette to respect), then future compromise of Bob's workstation still isn't enough to decrypt ciphertexts of old Signal messages.

Could Bob rapidly rotate his OpenPGP encryption key pairs to achieve a similar effect?  Yes—if he erases them that's enough to prevent decryption of past ciphertexts.  But there's no OpenPGP tooling to do this automatically, and OpenPGP is enough of a pain to deal with without rolling keys over every Thursday that approximately nobody wants to deal with it, and there's certainly nothing in the protocol to automatically roll keys over after every message while also handling reasonable out-of-order delivery.

That's because OpenPGP was—from a modern perspective with the benefit of hindsight—designed as a toy for early '90s crypto nerds to spend all their time reconfiguring their email clients to handle, mashing ‘signature’ and ‘encryption’ together like LEGO bricks, rather than a protocol to facilitate human interaction like Signal with security goals studied in the cryptography literature.

To be fair to the early PGP designers, a good deal of crucial cryptography literature was evolving concurrently with the development of PGP during the '90s—but even when confronted with basic cryptographic problems in the protocol for humans, the designers abdicated responsibility for addressing them in 2001.  Despite contemporary literature on exactly how to address it, to this day OpenPGP doesn't support public-key authenticated encryption.  OpenPGP didn't even achieve what has for two decades been the cryptographic standard security notion of public-key encryption until 2018 when EFAIL persuaded the OpenPGP world to begrudgingly make the MDC mandatory—a decade and a half after being alerted to problems with the MDC in 2002.


What information should I send along with an AES ciphertext and is there any standard to do that? While using some crypto implementations I got to see that many times a comment is added to the ciphertext.

For example:

-----BEGIN PGP MESSAGE-----
Version: OpenPGP.js v1.5.0
Comment: http://openpgpjs.org

wcBMAyJd6d8o7Y2pAQf/WZM1LV/iq3R8QGK7fUiQoUVzR8nEow+RJcBh6ujH
MBGWKcm4Y//a76hOL4r/Htbt7lwnfGe2HLrznRQip1TaONW897zrD7amsOp3
xlbZZep/HQNHNgtOGHx4peqDjrPQk9Y7HvRxrPFQWM2jMFTFlvJsw3kBWiNn
FI0jn+8RZalxCXloAE2OSWTkzInf+RfAefrFRCSiQW536UZ0h89u560TgA10
u7N0b+iGzRAB+4AFBZjkWpO5/KpYRzlUng+BMw4TmrlHJlLxiW7s3R3V74/J
ZNu1IIZ0S16A0r3XuWGbccO59igNY8qzi3FyMiQgCbYCReccm6M59no7M0gK
0tJFAe9BC5GJuS0oTrnoH9Wf6/tftw5booEaNU67HDnU0qI9blUK2rFVFoR/
ZCNlDy2HxpQZFgrnGPBMsvV6wZSj/LgLF+wi
=jLQU
-----END PGP MESSAGE-----

Where:

-----BEGIN PGP MESSAGE-----

… identifies the beginning of the data.

Version: OpenPGP.js v1.5.0

… identifies which implementation of the protocol was used to encrypt the text.

Comment: http://openpgpjs.org

… provides a generic comment.

-----END PGP MESSAGE-----

identifies the end of the data.

The first thing I am wondering if it's some standard out there for this comments, and if so some links or informations about it.
Would've asked to Google but don't know what to search.

Then, I would like to use a comment like the one showed above to store my ciphered messages as plaintext.

Assuming I want to do that for a message ciphered using AES, which informations should I store?

Should I store the AES mode used for encryption ?
Should I store the AES implementation I used ?
Should I store the initialization vector ?
Should I try to be compliant to some standards while storing these informations ?

What you are looking for is a definition of PEM, privacy enhanced mail. Obviously PEM is not just used for mail anymore. The definition of the header lines seems to be best described by section 4.6: "Summary of Encapsulated Header Fields" of RFC 1421: "Privacy Enhancement for Internet Electronic Mail: Part I: Message Encryption and Authentication Procedures". Obviously for PGP specific header fields you'll have to take a look at the OpenPGP format, specifically the section about ASCII armor.

  Then, i would like to use a comment like the one showed above to store my ciphered messages as plaintext. Assuming i want to do that for a message ciphered using AES, which informations should i store ?

That depends on the scheme you've chosen. For transport security the minimum would be the IV, the ciphertext and an authentication tag over both.

  Should i store the AES mode used for encryption ?

That depends. You could store a protocol version instead which determines which mode is used. You should not just store the mode without authentication and then proceed to process the message based on the header fields. That would give an attacker to decide which operation is performed on the receiving side. You need to keep control over what is performed on the receiving side.

  Should i store the AES implementation i used ?

No, the implementation of the block cipher should be irrelevant if you've decided upon a well defined protocol.

You could store a version of the software implementation of a protocol. In that case you may be able to work around possible bugs within the implementation. I've seen quite a few instances where the implementation of PGP did matter.

  Should i store the initialization vector ?

Yes, unless you've got ways of establishing the IV out-of-band (e.g. an operation over a message counter included in a message counter, or a counter kept in sync at both sides). If unsure include a random IV of sufficient size.

  Should i try to be compliant to some standards while storing these informations ?

It's strongly advisable to keep to well known container formats such as CMS or the already named OpenPGP yes.


(Re-)Using deterministic IV in CTR mode / How to: deterministic AES I am aware of the requirement of an IV to be unique in CTR mode (Why must IV/key-pairs not be reused in CTR mode?). However I wonder if I can use an IV depending on the plaintext deterministically. This means, of course, that the whole encryption is deterministic, which is what I want.

In the following scenario:

$C_1 = ENC_{AES-CTR}(K, P_1, IV(P_1))$

$C_2 = ENC_{AES-CTR}(K, P_2, IV(P_2))$

If $P_1 = P_2$

then $C_1 = C_2$

then $C_1 \oplus C_2 = C_1 \oplus C_1 = 0$, which essentially doesn't mean anything other than $P_1 = P_2$, which we already knew, as we're talking about deterministic encryption.

The question is: Is, by definition, the use of an IV for the same plaintext a re-use? If not, will a strong hash function be suitable to derive an IV from the plaintext? (Similar question: Security of this deterministic encryption scheme)

I'd like to use SIV mode, but it's not available in neither of the different platforms involved.

Edit:
Some more information about my plaintext: I want to encrypt filenames. This means the plaintext is short, might consist of known words, has little entropy and sometimes fits into a single block. As already said before, I want equal plaintext filenames to result in equal ciphertexts.

Edit 2:
All information needed for decryption must be contained in the resulting ciphered filename, e.g. as a prefix. Due to length constraints on certain file systems this prefix should be as short as possible.

I cannot prove that your scheme is secure, but as far as I know, a non-cryptographic hash function would work fine as there is an infinite number of inputs to any given hash, making it impossible to bruteforce all but the shortest messages (which would be an issue for short messages, you may want to append some sort of 128-bit padding).

However, that said, 128-bit block ciphers begin to lose security after $2^{64}$ blocks, as the number of collisions increase. In CBC mode, subsequent blocks use the previous block as an IV. If two blocks have the same output, that means that the two previous blocks XORed together will equal the two plaintexts XORed together.


Real time video stream AES encryption with authentication I am now studying AES encryption for real-time video streaming. It seems that Netflix uses the AES-GCM (or CBC + MAC) mode for real-time video encryption and authentication. With MAC authentication, the client can only get the MAC message after the whole video is encrypted and authenticated. After that, the client can verify and play the video. However, if the client wants to play the video immediately (without receiving and decrypting the whole video), how can the client verify the MAC message?

I guess the video stream may be divided into many small slices. The server will encrypt and authenticate those slices one by one. At the receiving side, the client will verify, decrypt and play slice_1, then slice_2 ,then slice_3 and so on.

I am not sure whether my guess is right. Could someone please give me some advice? How does the real video provider's server do this kind of secure video stream transmission? If my guess is right, what is the typical size of video slices, or it is dynamic?

updated per comments;
Currently Netflix Uses AES-GCM

I am now studying the AES encryption for real-time video stream. It seems that Netflix uses the AES-GCM (or CBC + MAC) mode for real-time video encryption and authentication.

With MAC authentication, client can only get the MAC message after the> whole video is encrypted and authenticated. After that, the client can only get the MAC message after the whole video is encrypted and authenticated.

This blog post, posted on Aug 8, 2016 by Netflix, mentions that;

Cipher Evaluation
We evaluated available and applicable ciphers and
decided to primarily use the Advanced Encryption Standard (AES) cipher
in Galois/Counter Mode (GCM), available starting in TLS 1.2.
We chose AES-GCM over the Cipher Block Chaining (CBC) method, which comes at a
higher computational cost. The AES-GCM cipher algorithm encrypts and
authenticates the message simultaneously — as opposed to AES-CBC,
which requires an additional pass over the data to generate keyed-hash
message authentication code (HMAC). CBC can still be used as a
fallback for clients that cannot support the preferred method.
We needed to determine the best implementation of AES-GCM with the
AES-NI instruction set, so we investigated alternatives to OpenSSL,
including BoringSSL and the Intel Intelligent Storage Acceleration
Library (ISA-L).

How AES-GCM enables immediate playing

However, if the client wants to play the video immediately (without receiving and decrypting the whole video), how can the client verify the MAC message?

AES-GCM mode requires the receiver to verify the tag before using the plaintext. Since Netflix uses SSL/TLS there is a limit of a record in SSL/TLS, see RFC-5246 section-6.2.1. The amount is given as $2^{14}$ bytes or less. $2^{14}$ bytes is just ~16 kB. This amount is easy to verify the tag and decrypt the data even the user jumps on the movie.

Server Side

I am not sure whether my guess is right. Can anyone give any advise? How does the real video provider's server do this kind of secure video stream transmission?

Netflix used AES-CBC now AES-GCM. As mentioned in the blog, AES-CBC mode of operation requires an additional pass to generate the HMAC. AES-GCM, however, can perform encryptions and authentication the message simultaneously. This is good for the server-side for reducing the data access.  With the usual numbering of the data, the server can feed the client with many records at once.
On the server-side they use AES-NI, ISA-L, and BoringSSL
Note that; they developed a special TLS;

To retain the benefits of the sendfile model while adding TLS
functionality, we designed a hybrid TLS scheme whereby session
management stays in the application space, but the bulk encryption is
inserted into the sendfile data pipeline in the kernel. This extends
sendfile to support encrypting data for TLS/SSL connections.

see the two technical articles from Netflix developers;

Optimizing TLS for High–Bandwidth Applications in FreeBSD
Improving High–Bandwidth TLS in the FreeBSD kernel.

Parameters

If my guess is right, what is the typical size of video slices, or it is dynamic?

The Netflix articles don't exactly mention this. This paragraph from the article 1;

When the keys were ready, have the TLS library
send them to the kernel and let the kernel do the encryption
part, while all the other parts of TLS would continue to be
executed by the TLS library. The TLS library would continue
to frame its messages and submit framed but un-encrypted
messages to the kernel.

implicitly implies that they are bound to TLS record size, $2^{14}$ bytes.


HMAC key storage for a web app? If one is going to use an HMAC, I.E: http://php.net/manual/en/function.hash-hmac.php, where exactly are they storing the key?

Without some sort of secure storage (i.e not in a local file or code), I feel like one is fooling oneself when using a HMAC (as with the above function). I missing something related to the storage of keys?

Before we get into the key storage and management issues, I wanted to clarify the scheme that is proposed in the linked article, to make sure it is clear what we are talking about.
Let's assume we get pw for authentication from the user and retrieve salt and tag from the database and we get sk from the storage method (see below) being a secret key. We then only accept the password pw if and only if tag=hmac(sk,salt||pw||salt) holds. The prototype of hmac looks as follows: MessageAuthenticationCode = hmac(SecretKey,Message), where the input SecretKey is implicit for trusted devices which provide a parameter for designating a specific secret key stored inside the device.

I really only see three options you have for storing the key if you want to use to do the password verification on a server that reboots:

Use a trusted device connected to the server. This includes smart cards (they may be too slow), trusted platform modules (TPMs; which may also be too slow) and hardware security modules (HSMs; which may be too expensive)
Store the encrypted key and hold the clear one in RAM and require user interaction for unlock. This may work by sending the server a secret password that allows for decryption of the HMAC key if it's at rest or may use this protocol (with EC-ElGamal) for smart card / TPM / HSM based / software based remote unlock.
Store the encrypted key temporarily, hold the clear one in RAM and use a trusted device. This means you let the server generate the secret HMAC key which is only held in RAM until a reboot happens and use a trusted device on reboot only. You may combine this with the second approach.

Now for the details and trade-offs of each method.
Trusted Devices
You can get yourself a smart card and install it in the server. You then send the password to be checked to the card, which holds the key, and receive the corresponding password hash which you compare to the stored value. This may not be suitable for mass-authentication as smart cards tend to be slow  but is the (second) cheapest option among the trusted devices.
You can get a server mainboard featuring a trusted platform module (TPM) and use it like the smart card in the above paragraph. However the TPM suffers from the same problems: While it tends to be cheap it usually is rather slow and not suited for a larger service (handling more than ~10 requests per second).
The "best" solution from this category is the hardware security module(HSM). It would be used just like the other two. Whatsoever those modules tend to be very fast and would very-well be capable of handling many requests in very short times. Furthermore HSMs tend to also have better security certifications then smart cards and TPMs. The downside of course is that HSMs are very expensive, with the cheap ones starting at several hundred dollars and the better ones going up to several ten-thousand dollars, whereas smart cards are within the price range of a few dollars to a hundred dollars per piece.
TL;DR: So overall, while they provide the most security, I don't think trusted devices would solve your situation, because of API, speed and price restrictions.
User Interaction
Here there are basically four different options. A combination of in-place or remote password-based or public-key based key unlock. I'll quickly describe each.
But first I need to describe the overall concept of this approach. You let the server generate the HMAC key in RAM and store an encrypted copy on the hard drives. Every time the server reboots, the HMAC key gets wiped from the RAM and the encrypted copy needs to be unlocked in order to verify passwords. This is where the user interaction comes into play.
The first version of this would to simply enter the password while being directly and physically connected to the server. This is arguably the most secure solution of those requiring user interaction but on the other hand also the most time-intensive solution, as you have to plug-in a monitor and a keyboard, every time your server restarts, so you won't want to do this.
The second version is nearly identical to the first, but this time you'd connect a smart card reader (with a pinpad) to the server, enter the PIN and let the card (asymmetrically) decrypt the stored HMAC key. While this is even more secure than the first approach it suffers from the same problems and thereby usually isn't an option.
The third version improves upon the first, by establishing a TLS (or otherwise) secured channel to the server and handing the password over this way. While this is obviously less secure than the first version as there's the risk of intercaption and man-in-the-middle attacks it is also a lot more scalable.
The fourth version improves upon the second. You'd establish a secured channel (TLS, IPSec, local network, whatever) to the server and then run this protocol on it. This will allow you to decrypt the stored key without the key (or the ciphertext) ever having to leave the server. Yet only the correct smart card / private key can unlock the HMAC key. This is the most secure and most scalable solution among the remote-solutions that require user interaction at boot.
TL;DR: This may be an appraoch that is suitable for your needs, but may require too much user interaction to scale well. And of course the security of a fully hardware based solution can't be reached which may be acceptable as the API, speed and price can be met.
Trusted devices on Reboot
Full disclosure: I didn't invent this approach, but observed it first at Jetico's BestCrypt VolumeEncryption.
You can let the server generate the key in RAM. Now you let the key stay there until a scheduled reboot happens where the TPM will encrypt the HMAC-key and store it onto the drive. Now the server reboots and after the reboot the TPM will unlock the key and afterwards delete it. This allows for unattended reboots but has the problem that if an unexpected reboot happens the key will be lost and no passwords can be verified. The positive side is of course that this will scale extremely well and will allow for fast software based verification while using powerful hardware protection when necessary.
TL;DR: While this solution will scale quite well, it has the issue of key-backup in case the server shuts-down without a warning. And of course the security of a fully hardware based solution can't be reached which may be acceptable as the API, speed and price can be met.
The optimal solution (?)
This approach will work the same as the previous one with the small exception that one makes an encrypted backup of the HMAC-key to the drives. Most of the time the server will operate as in the above approach (using software-based HMAC for verification), but in the case of reboots the TPM will kick in and temporarily make the back-up copy for the reboot. Now the weakness of the "old" approaches was that there's no backup for the case of unexpected reboots. In such cases the user interaction appraoch could kick in and allow for decryption of the back-up key. This would even fix the problems of the "blind-decryption" protocol as the user now would very rarely use this method and only in cases where it was sure what happened, allowing for stronger key protection (like a smart card in a vault) and where the user can directly see the result (successful unlock). Furthermore the backup copy of the HMAC-key could be moved to a physically secure location (like a CD inside a vault) which was one of the problems of the stand-alone protocol.
TL;DR: This approach fixes the issues with the previous one, so there's a solid back-up, allowing for unexpected reboots and for unattended planned reboots. And of course the security of a fully hardware based solution can't be reached which may be acceptable as the API, speed and price can be met.
Note: Drives may be directly attached to the processor / mainboard or may be at a physically different location.


How to determine the exponent when using RSA Can someone please explain to me how, when using RSA, to determine the exponent to be used in encryption and decryption? I have attempted a worked example on using RSA (shown below) but I can't ever get the decryption algorithm to work.

Worked example:

$p  = 29$

$q  = 37$

$n  = 29*37
 = 1073$

$\phi  = (29-1)(37-1)
     = 1008$

$e = 3$

$d  = (2(1008))+1)/3
 = 672.3333333$

$m  = 121512$ (taking the positions in the alphabet for 'L', 'O' and 'L')

Encrypt:  $ c = 121512^3 \mod 1073 = 878$

Decrypt: $ 878^{672.3333333} \mod 1073 = 352.91536313837299042255202310536$

There are three main errors here:

Exponent $e$ must be chosen to be coprime with  $\phi$. In your question, exponent $e = 3$ is not coprime with $\phi = 1008$. You can choose $e = 5$ instead.
You must use integer arithmetic, not floating-point. In other words, you cannot have values expressed with decimals.
You cannot encrypt a message bigger than the modulo (in this case, $n = 1073$).

Taking these aspects into account, the remaining steps are as follows. The private key $d$ must be computed so $e \cdot d = 1 \mod \phi$. Using this online tool, we find the private key $d = 605$. Next, we cannot encipher message 121512 since is bigger than the modulo, but we can encipher the first three digits, so $m_1 = 121$. Hence, the other half of the message is $m_2 = 512$. The encryption of $m_1$ is $c_1 = (m_1)^{e} \mod n = 121^{5} \mod 1073 = 25937424601 \mod 1073 = 544$.

You can figure out the rest.


Do equivalent RSA keys exist? If $m^{ed} \bmod n = m$ for message $m$, public key $e$ and private key $d$, then adding any integer multiple of $n$ to $m^{ed}$ still equals $m$ modulo $n$.

Supposing it exists, how do I find an equivalent key, d', such that $m^{ed'} = m^{ed} + kn$?

The formula at the heart of RSA is:

$$x^{\lambda(n)} = 1 \pmod n$$

where $\lambda$ is the Carmichael function. In the case of two-prime RSA it's $\operatorname{lcm} (p - 1, q-1)$.

$$m^{k \cdot \lambda(n)+1} = m \pmod n$$

We choose $d$ such that $e\cdot d = 1 \pmod {\lambda(n)}$. If $\operatorname{GCD}(e,\lambda(n)) = 1$ then there is exactly one solution in the interval $0 \leq d < \lambda(n)$ but you can construct infinitely many solutions outside this interval by adding $k \cdot \lambda(n)$.

(There are some complications when $\operatorname{GCD}(x,n)\neq 1$, which I'll ignore, since it'll still work in that case)


Are Edon-R 512 and Blue Midnight Wish 512 safe/recommendable? Looking for a faster cryptographic hash function for embedded devices, I found Edon-R 512 and Blue Midnight Wish 512, both impressively fast. Are they safe for general purpose hashing in hostile environments?

I am especially interested in Edon-R 512, which is faster, but knowing that it came from the same authors as Blue Midnight Wish 512, which was created as a more secure alternative, I expect it to be weaker. Is Edon-R 512 strong enough?

Currently I am using SHA-256, so anything as strong will do. I do not need a hash function at the SHA-3 security level.

Edon-R seems broken, in particular by Peter Novotney and Niels Ferguson's Detectable correlations in Edon-R and (in secret-prefix MAC mode) Gaëtan Leurent's Practical Key Recovery Attack against Secret-IV Edon-R. These attacks got no rebuttal (and attacks only get better; they never get worse); the design did not make it to the SHA-3 competition's second round; a project's archive appears unchanged since November 2008. I thus recommend against using Edon-R.

Blue Midnight Wish, in the variant that made it to the SHA-3 competition's second round (archive), is not broken as far as I can tell. The closest thing to an attack seems to be Gaëtan Leurent and Søren S. Thomsen's Practical Near-Collisions on the Compression Function of BMW (in proceedings of FSE 2011); but they admit that "it does not weaken the security of the iterated hash function" (that is, full BMW); and the rebuttal raises the argument that BMW's double-pipe construction should make it nontrivial to turn a partial collision for the compression function into an attack on the hash. I'd say that if speed was worth living dangerously and far from the mainstream, using Blue Midnight Wish (irrespective of size) could make some sense.

Here's how BMW's elimination from the final SHA-3 round (making BMW history) was justified:

  Although BMW has very good software performance, and good potentials for pipelining and area-efficient high-throughput values, a disadvantage of the algorithm is its irregular and not-well-understood design. Since the compression function of BMW does not have a conventional iterated-round structure, there appears to be no obviously simple way to adjust the security margin, or to trade performance for security. Moreover, the attacks on the algorithm, even after an extensive tweak, did not provide confidence in the security of the algorithm. For these reasons, BMW was not selected as a finalist.

Footnote: I second the recommendations in that other answer.


local collisions in SHA 0 I have found interesting for me paper about constructing collisions in SHA 0. On page 60 the author determines M variable which is a concatenation of 32-bits vectors $M^{(i)}$, but I can't find any explanation about this

$$\forall i,0\leq i\leq 79,M^{(i)}_{0,k}=0\text{ if }k\neq 1$$
$$\forall i,0\leq i\leq 79,M^{(i)}_{0,k}=m_0^{(i)}$$

$M$ with superscript $(i)$ means a 32-bits vector which refers to $i$-th word W.

What does $M$ with two subscripts $0$ and $k$ mean?

It is very important to make it clear because whole process of getting right mask $M$ is based on the first mask $M_0$. Please help me to understand the author's definition.

In the referenced paper, $M^{(i)}_{j,k}$ is bit $k$ of the 32-bit $M^{(i)}_j$, with $-5\le i<80$, $j$ the same index as in $m_j$ with $0\le j<6$, and bit index $k$ is with $0\le k<32$.

The question's two statements are thus equivalent to
$$\forall i,0\leq i\leq79,\quad M^{(i)}_0=\begin{cases}
\mathtt{00000000_h}&\text{if }m_0^{(i)}=0\\
\mathtt{00000002_h}&\text{if }m_0^{(i)}=1
\end{cases}$$


Is $f\colon x\mapsto g(x+1)$ necessarily a pseudorandom function? Let $l\in\mathbb N$ and suppose
$$g\colon\;\{0,1\}^l\to\{0,1\}^l$$
is a pseudorandom function.
Is $f$, defined as below, necessarily a pseudorandom function as well?

$$f(x)=g((x+1)\bmod2^l)$$

The general way to answer questions like this in the affirmative (i.e. prove that some transformation of a certain type of thing gives you another of that type of thing) is to assume that your transformed version doesn't have the property you need, and use that to prove that the original also doesn't have that property. Then if the original does have the property we want, so must the transformed version.

So, assume $f$ isn't a PRF. That means that there's an efficient algorithm with a function as its input that can reliably tell whether you gave it $f$ or gave it a random function as input, by evaluating its input at a bunch of points. You can modify this algorithm to tell $g$ apart from a random function -- because $f(x)=g(x+1)$, just tweak the algorithm so that every time it evaluates the function you had passed it at $x$, it instead evaluates it at $x+1$. If you run this algorithm with $g$ as input, it acts exactly like your original algorithm did with $f$ as input. If you pass it a random function as input, the random function is still random. So, this new algorithm can tell $g$ apart from a random function, and $g$ isn't a PRF.

Because any distinguisher for $f$ can be tweaked to make a distinguisher for $g$, it means that $g$ can only be a PRF if $f$ is, so if $g$ is a PRF then $f$ is a PRF. This kind of argument is extremely useful when building cryptographic functions using primitives; it even works when the properties of the underlying primitive and your construction are different (you show that an attack on property A of your construction lets you attack property B of the underlying primitive).


One time blinding threshold encryption? Paillier cryptosystem has self-blinding property.
(change one ciphertext into another without changing the content of its decryption)

Is there any threshold encryption scheme (or just encryption scheme) which provides one time blinding?

(One time blinding means that the number of changing is limited to one.)

Ok, here is a random idea I had; it needs further analysis, especially in regards to the security parameters.

It's based on RSA; I believe that there are ways to run RSA as a threshold scheme; I'll assume that you'll use one of those.

The public key will be the normal RSA parameters $N, e$, as well as an integer $C$.  The private key will be the RSA private key (and the integer $T$).

Definitions: we will call an integer $x$ smooth if all its prime factors are $< T$.  We will call an integer $x$ rough if all its prime factors are $\ge T$.

Encryption method: we first encode the plaintext as a rough integer $P$ between $\sqrt[4]{N}$ and $\sqrt[4]{N}/2$.  Then, the ciphertext is the value $P^e \bmod N$.

Blinding method: we take the ciphertext $C$, and select a random smooth value $\sqrt{N}/2 < S < \sqrt{N}$.  Then, the blinded ciphertext is the value $C^2 S^e \bmod N$.

Decryption method: we take the ciphertext $C$, and compute $D = C^d \bmod N$.  If $\sqrt[4]{N}/ 2 < D < \sqrt[4]{N}$, then $D$ is the resulting plaintext.  If $D > \sqrt[4]{N}$, then we divide out all the prime factors $< T$ from $D$, and then compute the integer squareroot (and if it's not a perfect square, decryption fails); the resulting squareroot is the plaintext.

Notes:

Blinding works because the blinded value $C^2S^e = (P^2S)^e \pmod N$, and as $P^2S < N$, RSA decryption results in the integer $P^2S$.
It should be obvious why blinding an already blinded value doesn't work.
Obviously, we need to specify the sizes of $N$ and $T$.  One requirement is to make the blinding recognization problem hard, that is, given two ciphertexts $C_1$, $C_2$, determine whether one the blinded version of the other.  There is a MITM attack available, such to be $s$-bits secure, there needs to be at least $2^{2s}$ smooth numbers below $\sqrt{N}$.  I suspect this will imply that $N$ will need to be larger than normally required for RSA, however that needs to be analyzed.  My instincts say that $N \approx 2^{4096}$ and $C = 10000$ should work reasonably, but again, real analysis is needed.
One thing that needs to be considered are possible weaknesses due to the homomorphic properties of RSA.  Even though we're not using a conventional padding scheme, I believe we're safe (because $T$ is large and rough), however that really does need analysis.
Of course, this doesn't work for $e=3$; the standard $e=65537$ should be fine.
We also need to spell out how to randomly select a large smooth value, but again, should be spelled out.
The process of encoding the plaintext as a rough integer (and decoding it at the end) is straight-forward.

On review, the idea isn't perfect; an attacker could generate a "weak blind" on an already blinded value by multiplying it by $(a/b)^e$ (for small $a, b$); this works if $b$ is a factor of the $S$ the blinding used.  I'll leave this answer open, in case someone sees a way to address this...


Constructing a custom protocol using well-vetted algorithms? For the reasons I cannot go into details, I need to design my own protocol and overall security system which will be used to establish secure data exchange between various devices (most notably desktops of all three major OSes, Android and iOS devices and Raspberry Pi, with the possibility to extend it to other embedded systems). Since I wouldn't dare to do my own crypto algorithms implementation, this implies that I have to rely on tried and tested libraries available for those platforms (i.e. OpenSSL, BouncyCastle, CommonCrypto, …) so I settled with what they all support - RSA for signing/authentication, DHE/ECDHE for session establishment, AES for encryption, PBKDF2 for key derivation and SHA2 for general hashing needs. The key sizes and complexity will depend on the hardware ability of targeted platforms.

Now, I've done a fair bit of implementations of existing protocols and I like to think that I know my way around cryptography and perils that await if not applied properly, however I wouldn't dare to consider myself a cryptography expert and thus I decided to query the hive mind. Of course, once everything completed it will be properly audited and tested, but for now I need to know if I'm on the right track, that I haven't done some glaring omissions and if it is possible to improve it even further.

The system I'm building should both cover the storage on devices and the communication between them and to preserve forward and backward secrecy.

For the storage part I plan to utilize AES in CBC mode, storing the randomly generated IVs with each individual encrypted file. The 'master' key itself will be randomly generated and also AES-encrypted using a key derived from the user's password using PBKDF2, stored along with the salt and iterations used in it. My main concern is the IV part as if generated randomly it might repeat thus compromising the encrypted files if they happen to be similar enough or even the same. It's quite a low chance buy I don't like leaving anything to chance so the question is - given that the IV is public knowledge anyway, is it safe to use incremental progression/timestamp as IV in this case?

The communication part will be a bit trickier as the devices will never communicate directly - instead the data exchange between them will be relied through a third party database to which they periodically connect, which is one of the prime reasons I'm designing my own protocol. If we except this oddity, the data exchange itself should function quite the same as if they were communicating directly, namely the devices will establish a session each time they 'contact' each other and then use the session key for encryption.

To establish a session I plan to use a variation of STS protocol adapted to this environment. The only oddity here is that in some instances only one of the parties involved in communication will posses the RSA key of the other so it won't be fully authenticated - my understanding is that even in this case no successful MITM attack can be performed as at least one of the parties will reject communication if the signature doesn't match. Is that a safe assumption?

Once DH/ECDH keys are exchanged an actual session AES key will be derived from them using SHA2 and the rest of the data exchange will be encrypted using that key, again in CBC mode - until the session expires, when the process repeats. I'm still not clear on how to approach the message integrity and authenticity verification - at first I thought that signing the message with the device's RSA key will be enough, but since it may happen that only one of the parties has the other party's certificate I might add a HMAC alongside with the exchanged messages as well. What would be a recommended, cryptographically secure way to handle that?

You might want to start by reading Lessons learned and misconceptions regarding encryption and cryptology.  I spotted 3 potential issues in your proposal that are explained there.

Instead of designing your own cryptosystem, you should try hard to use an existing well-vetted scheme, like TLS or DTLS for interactive communication, or GnuPG for storage or store-and-forward messaging.  The fact that communications are routed through a proxy server doesn't change this recommendation; you can still do end-to-end cryptography.

(If you are building your own protocol, you to use authenticated encryption, and deriving cryptographic keys from a passphrase tends to provide poor security.)

Since you haven't given us any specifics why you can't use existing schemes, it's going to be tough to provide you with more detailed advice.


Will AES-GCM smaller sized tag (mac) be included in larger sized tag I want to make sure that I understand AES-GCM correctly:

If I have:
key1, plaintext1, iv1, adata1 and requset tag size of 96 bits, and tag size of 128 bits, will the first 12 bytes of the 128 bits tag equal 96 bits tag?

Yes, that's what the standard mandates.

First we need to note that if you fix a key and an IV, then AES-GCM becomes fully deterministic, that is the same input will yield the same exact output.

Then we look into the standard, NIST SP800-38D (PDF), and look at the way the tag is generated.

$$T=\operatorname{MSB}_t(\operatorname{GCTR}_K(J_0,S))$$

which effectively tells us that the $t$ most significant bits of the tag output (which is the same for both invocations) are to be used for the tag.

Then we look up the semantics of the $\operatorname{MSB}_s(X)$ function which are:

  The bit string consisting of the $s$ left-most bits of the bit string $X$.


How to define secure pseudorandom functions? I was told that for both cases the PRF is strong/secure, but I cant find a proper way to define this. Personally i think only (b) is secure because $x$ is not as strong as $O^n$ for $Fs$. But if that was true, what would be the ppt algorithm which could break it?
Is it related to the fact that $F(x)$ is not pseudorandom since its values on any two points are correlated?

Consider yourself an adversary. You're given access to an oracle $O(\cdot)$. You're trying to determine if $O(\cdot)$ is actually random or $F'_s(\cdot)$ with some randomly sampled $s$.
a. Consider $O(0^n)$ and $O(1^n)$.
b. Consider $O(0^n)$
In each case, consider some special event $E$. If $O(\cdot)$ is truly random, what is the probability $p$ that $E$ occurs? If $O(\cdot) = F'_s(\cdot)$, what is the probability $q$ that $E$ occurs? Your distinguishing advantage is $|p-q|$.


OpenSSL - creating random elliptic curve and measuring performance I want to generate random elliptic curves (over $\mathbb F_p$ and $\mathbb F_{2^m}$) using OpenSSL, that's my task.

At first curves over $\mathbb F_p$. Now I am able to generate prime $p$, $a$ and $b$. Then I need to get random point and measure time of adding and multiplying points.

To get random point:

I need to know order of the group. So I should count it with Schoof–Elkies–Atkin algorithm, right?
I need to have generator (base point), right? So I have to find it. It can't be random point, but it should be point which generates as much as possible points on the curve, right? (depends on cofactor, if is it = 1, then generator generates all the points, if it is 2, then it generates 1/2 of points, etc).

I found I can find generator with this algorithm:

$|E(\mathbb F_p)| = k \cdot r$ with a prime $r$.
Choose a random element $x_0 \in \mathbb F_p, 0 < x_0 < p$.
If $x_0^3 + a x_0 + b$ is square in $\mathbb F_p$, we denote by $y_0$ a square root of $x_0^3 + a x_0 + b$ in $\mathbb F_p$. Otherwise we choose new random values $x_0$ until we succeed.
We may assume $1 \leq y_0 \leq p − 1$. $y_0$ may be computed using Shank’s RESSOL algorithm.
$(x_0, y_0)$ is a point in $E(\mathbb F_p) \setminus \{\mathcal O\}$.
If $k \cdot (x_0, y_0) \ne \mathcal O$, then $G := k \cdot (x_0, y_0)$ is a point of order $r$, $r \cdot G = \mathcal O$.

This algorithm is from this paper (PDF), page 11.

Is all what I wrote correct, or is there any other easier way how to get generator (base point) and order of the group? (Maybe there are some functions in OpenSSL but I didn't find it.)

EDIT: Exists some code in C of SEA algorithm? I need to generate elliptic curves (so I have to find the order of the group because I want to find base point) on devices with constraint resources (rasp pi etc). It have to be multiplatform. I thought I could copy some code to my appliacation.

Yes. The hard part is of course to find the order of the elliptic group and its factorisation. Ideally, if the order of the group is a prime number (use a primality test), you know that $k = 1$, and any point on the curve is a good generator.

That said, it is not because you have found an elliptic group with prime order, that it is a cryptographically safe group. For instance, if the order of the group equals p when you are working over $F_p$, you have a cryptographically weak curve.

There are other conditions that give rise to cryptographically weak curves.  Generating a cryptographically good curve is somewhat tricky.

If this is for a toy example, with relatively small curves for illustrative purposes only, then as others said, use Sage.


Point doubling with only one coordinate In many source codes that implement ECDH, there is a function that multiplies the base point of that curve with a constant. This function usually takes as arguments the constant and just one coordinate of the point.  All formulas for multiplying a point on an elliptic curve with a constant involves both coordinates of that point. Can anybody explain how those functions do their job?
For example, look here.
The function curve25519_generic multiplies the base point of curve25519 with the scalar. A point on curve25519 has both coordinates on 32 bytes, but the function takes just the x as an argument.

The Montgomery Powering Ladder for computing the scalar product of a point P on an elliptic curve (or in every other abelian group) only needs the x-coordinate of P.

It is used widely since it is believed to be secure against side channel attacks, which is not true in all cases-- for example, see this.

For further details concerning the Montgomery Powering Ladder, see the subsection "Montgomery's ladder technique" in this article

To compute $d\cdot P, P\in E(K)$ we have the following formulas which are used in MPL:

Let $P_{1}, P_{2}, P_{3}, P'_{3} \in E(K): y^{2} = x^{3} + Ax + B$

$P_{3} = P_{1} + P_{2}$

$P'_{3} = P_{1} - P_{2} = \left(x'_{3}, y'_{3}\right)$

$x_{3} = \dfrac{2\left(x_{1} + x_{2}\right)\left(x_{1}x_{2} + A\right) + 4B}{\left(x_{1} - x_{2}\right)^{2}} - x'_{3}$

As you see, the y-coordinate of P is not needed in this computation.

I hope my answer satisfies your need!