Anonymity problem after voting with blind signatures In a distributed voting system (all the messages are public, but signed and maybe encrypted/blinded), having:

$d$, $e$, $N$ — registrar key params
$m$ — msg
$r$ — random blinding factor
$m'$ — blinded msg
$sm'$ — signed blinded msg
$sm$ — signed msg

When person received $sm'$ from the registrar, and unblinds it — he receives $sm$. He then sends it to the system anonymously for counting.

So, at the end registrar will have $sm$, and can read $m$.

Finally the problem

Registrar can in cycle try to do $sm'_i \cdot sm_j^{-1} \pmod N$ to find some $r_k$.
Then compare $m \cdot r_k^e \pmod N$ with with every $m'$.
If values match — person which sent $m'$ can be deanonimized as it is not hard for registrar to keep information about all $m'$ and linked persons.

It will take some time to process all the combination and depends of number of voters, but it works (tested simplest scenario).

Is there any mistake, or is it possible to overcome this problem with some trick?

The problem is, that you are actually checking a tautology and this is no danger to deanonymization. Let me explain it to you with a simple example of 2 signatures:

Lets say we want to blindly sign distinct messages $m_1$ and $m_2$ with distinct randomness $r_1$ and $r_2$.

Now during the blind signing you produce the transcripts (I omit $\mod N$):

$m_1'=r_1^e m_1$, $sm_1=r_1 m_1^d$ and
$m_2'=r_2^e m_2$, $sm_2=r_2 m_2^d$

and the final message signature
pairs are $(m_1,sm_1=m_1^d)$ and $(m_2,sm_2=m_2^d)$.

Now, lets apply your strategy:

lets look at one case where you start from one of the final signatures, say $(m_1,sm_1)$ and check it against both transcripts of the blind signing process  (and the second case is analogous due to symmetry):

$sm_1' sm_1^{-1}= (m_1^d r_1) (m_1^d)^{-1} = r_1$ and

$sm_2' sm_1^{-1}= (m_2^d r_2) (m_1^d)^{-1} = r_1'$

now you have two candidates and lets check it with every $m_i'$:

$r_1^e m_1 = r_1^e m_1 = m_1'$ and
$(r_1')^e m_1 = ((m_2^d r_2) (m_1^d)^{-1})^e m_1 = (m_2^d)^e r_2^e (m_1^{-1})^{ed} m_1 = r_2^e m_2 = m_2'$

So, now you have checked all transcripts of the blind signing process against the signature of the first message and with your candidates you have found out
that the first message corresponds to both transcripts with exactly the same probability. So you have learned nothing. As said above, the
same argument (due to symmetry) applies to the other case and you can easily generalise this to more messages.


AES cache-timing attacks and nonce-based operation modes As I understand it, AES cache-timing attacks exploit the execution time variations due to cache hits/misses, especially the ones depending on the SBox look-up tables which are key-related.

To mount such an attack, does an attacker need to have knowledge of the algorithm input? If so, are such attacks still relevant against operation modes such as CCM or GCM where the input nonce has a specific format and might be not transmitted (at least a part of it)?

In the paper of Daniel J. Bernstein one can read:

  By considering table lookups in (e.g.) the last AES round, develop an
  attack that works with highly structured AES inputs (as in, e.g.,
  counter mode) rather than random-looking AES inputs (as in, e.g.,
  CBC).

Have related works been published yet?

There are multiple ways you can get the key in attacking AES.

Let's say you have the known cipher-text, $ct$, and a list of all S-box lookups used in the last round of AES (maybe from a cache-attack).

We know that $ct$ is equal to $k \oplus y$, where $y$ is the intermediate state after the last S-box computation.

Now, we can go through each byte of $ct$, and for each byte $ct_i$ we attempt a possible key value $k_i$ for each value 0x00-0xff. Then we can get a possible $y_i = ct_i \oplus k_i$. If we run an inverse S-box computation on this $y_i$ and it is contained in the list of S-box lookups we received earlier, then we know that this $k_i$ is a possible byte for the key $k$.

If we do this operation many times through many runs of AES, then we can develop a table of possible $k_i$ values for each byte in $k$. We can use the mode of each key byte $k_i$ to build our correct key $k$. The accuracy of this attack obviously increases with more runs of AES.

As seen in this attack, you do not need to know the input of AES, only the output $ct$ and some last-round S-box information.

Hope this helps.


Renewing session key I have a system which (should) never shut down, there are keep alive messages every 30 seconds and normal traffic is very variable, might be a few KB/sec might be nothing more than the keep alive message.

Normally one would create a new key when you start a new connection but since our connection could (should) be up for weeks or months there is not standard re-negotiation for a session key.

My question is how much time should be between the generation of a new session key? should it be every day at midnight? or would that make the system vulnerable if the negotiation for a session key is always on the same time (or after a set time frame). Does TLS have something for this?

extra
Renewing a masterkey for our scenario is a bit tricky, we could do this by going to all the devices and manually setting it, something we would like to avoid. But it will be necessary to renew a master key once in a while, how often should you do that? given that it will be quite difficult to do.

EDIT
There is no DH or ECDH, well not in the first versions anyway. I am trying to push it (and certificates). A problem the company has is that we assume DH and ECDH will take to much time on our devices (we only have a few milliseconds to work with (about 10 to 15 ms) ) and I have not looked into the DH and ECDH times. on our Renessas controler (about 100 Mhz)

Note: Until told otherwise this answer will assume the following things:

The "Master-Key" is secure. (unextractable, 128-bit+ entropy)
Ephermal (EC-) Diffie-Hellman is available and secure (keys unextractable, 2048 bit DH / 256 bit ECDH available)
The random number generator used is secure. (i.e. not just relies on the time, e.g. it's a cryptographically secure RNG, which should be available and used by a good TLS implementation)

Now the answer:

You don't have to renew keys if the above points apply.
If the assumptions apply all keys will be unbreakable (for at least a decade).

Well it looks like you want to have forward secrecy and to get this you may want to renew session keys every now and then. If possible I'd suggest renewing the session key after each time some sort of "action" is finished.If you don't have something like this "action" or "large chunk" you may want to renew keys at regular intervals. If the above assumptions apply rekeying at static intervals shouldn't be a problem. As Interval I'd suggest: "As often as possible" which may translate to something in between an hour and a day.

For completely renewing the session key TLS does have a feature called "renegotiation". You can trigger such a handshake whenever you need a new key.

Concerning the renewal of the master-key:

If the above assumptions apply you don't have to renew the keys. Renewing the keys is of interested if you believe that the key might be extracted. Depending on how easy that is you may want to re-new rather often than less. If you're Device is tamper-proofed or you're encrypting the key using ephermal data I'd say that once in a year up to once a decade is ok. If you're device is planned to be used for more than 50 years you may want to consider using 192-bit keys.


Mutual aggreement to decode file I have a question about mutual agreement to decode a file

How could you choose to decode a file only if more than half the people present (let's say 6 out of 10 ) say Yes.

And there is only one key, in what form should the key be stored.

The obvious solution would be to use secret sharing: the file $F$ is encrypted using a secret key $K$, and $K$ is secretly shared between the $n$ parties, so that if at least $t$ parties reveal their share, the key $K$ can be reconstructed, while if less than $t$ parties reveal their share, the key $K$ remains perfectly hidden: Secret sharing can be constructed from simple interpolation methods, see Shamir's secret sharing scheme.

An issue of the above method is that, once the key $K$ is reconstructed, everyone knows it, so a fresh new key should be generated and shared between the parties for each file that we want to encode. A better solution, where many files can be encrypted using the same key, and so that a sufficiently large group of parties can decrypt a given file without leaking anything about the remaining encrypted files, is to use threshold encryption. A public-key threshold encryption scheme allows everyone to encrypt a file, but the decryption is performed as an interactive protocol between parties holding shares of the secret key. We know construction of such schemes from most standard cryptographic assumption, such as DDH.


Recovery of RC4 key when S-box 0 stage or 1st stage known I've been exploring around, trying to understand if such thing is even possible. I have some RC4 ciphertext which I know it's plaintext and I would like to extract the key just from cipher and plaintext. While reading through "RC4 Stream Cipher and it's variants" by Goutam Paul I came a cross (4.1.1) PRGAreverse algorithm on p.65 (Chapter 4.1) providing candidates for S by supplying to it a state of S and state number:

As both KSA and PRGA are deterministic, I guess this PRGAreverse algorithm should work but I'm having difficulties understanding the probability for each candidate. I mean, let's say I get 5 candidates for S[i], i=0, then how should I know which is the right one without trying to use it against the ciphertext nor plaintext?

I have some RC4 ciphertext which I know it's plaintext and I would like to extract the key just from cipher and plaintext.

That turns out to be a hard problem; the only practical way known is to brute force the key, and see if you can find a key that generates a keystream that is consistent with the known plaintext/ciphertext.

That is infeasble if the key is large; however it's the only known method that has much of a chance at all of working.

  While reading through "RC4 Stream Cipher and it's variants" by Goutam Paul I came a cross (4.1.1) PRGAreverse algorithm on p.65 (Chapter 4.1) providing candidates for S by supplying to it a state of S and state number

If what you have is the plaintext and the ciphertext (and nothing else), this algorithm doesn't help you.  The reason it doesn't is that it assumes that you know the state of the internal permutation S at some point; the plaintext/ciphertext doesn't give you that.  The best known algorithm for recovering the permutation given what you have turn out to be totally infeasible for standard RC4; you'd be better off attempting a brute force of the key.


Sites to find crypto intermediate values Does anyone know of any sites where intermediate values of multiple crypto algorithms (not just the famous ones), including hashes, can be found? I don't just mean intermediate values of encrypting. I'm also looking for intermediate values of the key generation algorithms as well. Hopefully, the initial values can be changed, or at least are not just strings of 0's, since many algorithms use little endian notation, which doesn't appear in strings of 0's.

The previous sentence means:

The mars cipher works with little endian values. In ibms's test vectors, the values are 0000000000000.... so when I input my key into mars, I get {0,0,0,...,0}. Fine.

Now if the test vector were 1234..., now what happens? If there are intermediate values for the key/encrypt/decrypt algorithms, I would know if the test vector were already in little endian, or if I have to change it to ... 34 12?

Normally, test vectors, in particular test vectors for intermediate values, are to be found with whatever is the "official specification" for that algorithm. MARS has not been blessed with a standard (few algorithms are), so the "official specification" is what IBM distributes, in particular the MARS package (compressed archive).

This package contains the specification itself as a PDF file (in MARS/Algorithm/mars.pdf), sample implementations, and test vectors (in the MARS/Test_Values/ directory). In particular, have a look at the ecb_ivt.txt file, which contains some "intermediate values".

As a more generic rule, when faced with low-quality or inexistent test vectors ("low-quality" meaning, e.g., that there are some hexadecimal bytes but without clear endianness rules), the usual method is to find a "reference implementation" and sprinkle printf() statements throught its code, so as to get the intermediate values. I recommend using the Java code, which, in practice, will run you into much less trouble than any C code (that's the benefit of the strictness of the Java platform).

The NESSIE project was a big effort at analyzing many cryptographic algorithms, and it produced a large amount of test vectors for all those algorithms. This is a good source (but MARS was not submitted as "NESSIE candidate" so no luck there, in the case of MARS).

If all else fails, you can always send an email to the function author. Most function authors are researchers who will gladly help you out.

On the question of endianness, in particular in C, I strongly recommend against trying to play games with the memory representation, such as using a union between a sequence of bytes and an integer type. Such games limit portability and, more importantly, tend to break in awful ways in the presence of an optimizing compiler (because of strict type aliasing analysis). Instead, use generic encoding and decoding "functions", which you can later on optimize with inline functions and macros, and possibly inline assembly, if you detect a machine and compiler on which you know a smarter and cheaper implementation is possible. As an illustration, have a look at sphlib, which is a library implementing many hash functions in C and Java. In the C code, all the endianness "smartness" is concentrated in the sph_types.h file, which defines uniform names for the integer types and encoding/decoding functions (e.g. sph_dec32be() for 32-bit big-endian decoding).


Why does Birthday attack work only with random messages and not with chosen messages? Considering unkeyed hashing functions, I studied that the birthday attack can only work generating random messages and not with messages chosen from the attacker, but I didn't understand why. For example if there is a trade contract between two parties A and B where A states to sell a warehouse to B for 10.000 dollars, and the attacker (e.g. A) wants to modify this document and insert 100.000 instead of 10.000 dollars (I denote this document with D), why can A not generate a huge number of possible modified documents (for instance modifying space, dots, commas, etc. of D) and trying to find a collision between all possible modified documents and the original document?

Birthday attacks do indeed work also for messages chosen by the attacker. For example, consider the case that I want to get a collision between a letter of recommendation and a letter that I was fired. I can prepare $2^{n/2}$ letters of the first kind and $2^{n/2}$ letters of the second kind, and then we expect there to be a collision between a message of the first kind with a message of the second kind. Note also that it's not hard to prepare such letters. All you need is a number of ways of replace enough words. For example, consider "[Mr. | Dr. | Prof.] [Yehuda | Y.] Lindell was employed as a [security | cryptography] consultant in our [company | organization]." This sentence can be written 3 x 2 x 2 x 2 =24 different ways (and this is just one short sentence).

I would also like to note that it's even possible to carry out a low memory birthday attack on meaningful messages. But, I'll leave working that out to you as an exercise.


Is it possible to trim some encrypted values under fully homomorphic encryption Suppose we have $N$ encrypted values under homomorphic encryption (BFV/BGV ..), and we know that $M$ of them are below $t$. Is it possible to remove those $M$ values?
It is known that some methods (e.g. homomorphic comparison) can out put $N$ encrypted $1$ or $0$s denoting whether the value is above $t$ or not, but I need to crop those below $t$, leaving $N-M$ encrypted values.
Edit: I understand it's not possible to directly remove the $M$ values, but is it possible to output $N-M$ new encrypted values, whose plaintext is exactly those $N-M$ values above $t$.

As long as you can design a circuit to do it, then yes. There are a few ways to do this. One is to build a sorting network and output the highest $N-M$ values.


x509 CA trust question I'm trying to understand the logic of CAs, trust and client certificates. I have a general understanding but am having a tough time bridging some gaps.

In a hypothetical situation a software system might be composed of n machines. I want to generate a custom CA for this system and have it self signed. The CA would consist of a certificate and a private key. The private key would (I assume) stay private on one machine, be used only for making other certs and not be used for any inter machine communication. From what I understand, each machine that will have a certificate created in this way has to have the public key of the CA in order to validate itself AND other machines that it tries to communicate to/from.

To generate the CA key, I make a private key as normal and self sign it. That will generate a private key AND a certificate. To make client certificates I make a private key and then a signing request using the certificate of the CA.

Here are my questions about this:

Is the certificate of the CA actually the public key? If not, does it contain the public key?
Does every machine that needs to communicate need to have a local copy of the CA certificate in order to validate other certificates?
Were my assumptions incorrect or incomplete?

Thanks for any help and understanding!!

For concreteness, let's take the concrete case of RSA.  You generate your keys -- will consist of a public key -- two numbers (N, e) and a private key (N, d) so that if you use c = m^e mod N to encrypt an RSA message you can use m = c^d mod N to decrypt it.  (In reality its not quite so simple, you have to worry about hybrid encryption, padding, constant-time modular exponentiation).

Certificates will contain the public key, plus data describing the organization, all of which is generally cryptographically signed -- typically by another trusted entity, except for self-signed certificates which are signed by their own public-key.  To sign someone's certificate (which I will call cert) you need the private key S = Hash(cert)^d mod N.  However, to verify that a signature is correct you only need a public key, by checking that S^e mod N is the same as the hash of the original cert.

So to answer your questions:

Certificates are not the public key, but contain (1) the public key along with (2) other identifying information (who the organization is, what resources the certificate should be used for), and (3) a signature from some other trusted organization.
If you want to validate the certificate for say https://crypto.stackexchange.com, your browser (or OS) needs to ultimately follow a chain of trust to a certificate it knows and trusts.  That is the certificate served by stackexchange is valid for *.stackexchange.com is validated to belong to Stack Exchange, Inc. operated out of New York, NY.  It was signed by DigiCert High Assurance CA-3 (who presumably validated the identity of Stack Exchange).  The DigiCert High Assurance CA-3 intermediate Certificate Authority was itself signed by DigiCert High Assurance EV Root CA.  The public certificate for DigiCert High Assurance EV Root CA is self-signed and your OS or web browser needs to have it to be able to trust it (e.g., for an OS may be stored: /etc/ssl/certs/DigiCert_High_Assurance_EV_Root_CA.pem or for a web browser /usr/share/ca-certificates/mozilla/DigiCert_High_Assurance_EV_Root_CA.crt).
I think you had the gist of it.  You create one CA with a CA certificate (acting as a public key + more data) that you share widely, and a private key kept secret only used to sign other certificates.  When one of your machines (call it M) needs a certificate - private-key pair (e.g., to do SSL), then M creates their own private key and a certificate signing request (CSR) -- basically an unsigned certificate (technically it is self-signed - to ensure it wasn't tampered prior to being signed by the CA).  The CSR is securely sent to the computer with the CA's private key, which signs the CSR to create a signed-certificate which is sent back to M.  Now M can create use the certificate plus its own private key to setup SSL connections.


How does authentication work differently between asymmetric and symmetric cryptography? Must Bob and Alice establish a 'connection' before a symmetric or asymmetric encryption scheme is secure? If so, is there ever some expected plaintext whose decryption authenticates the users?

In addition, could anyone recommend a good introductory book or paper on cryptography for a beginner like me?   Thank you very much.

A start would be the Wikipedia article about Authenticated Encryption, and the GCM mode is an AE-mode for block ciphers.

Additionally to the key, IV and cypher text you need the authentication tag, which is generated during the encryption process.

Decryption reconstructs the tag and compares it two the original. If they do not match, the decrypted text is invalid.


Is it possible to multiplex TLS connections by SNI metadata without knowing any keys? Imagine the following communication diagram:

C1-----\ /--B1
C2------P---B2
...----/ \--...

We have multiple C(lients), call them C1, C2, etc. They connect to a single P(roxy), using the SNI extension of the TLS protocol. The proxy uses the SNI metadata to decide, to which backend (B1, B2, etc) the connections should be forwarded to.

The proxy has no information about the used keys, thus it has no way to intercept/eavesdrop the transfered data. More clearly: the backends are using heavily client/server certs which are used for authentication/authorization. This information can't be lost by an (unneeded) decrypt/re-encrypt by the P.

On this reason, the P(roxy) has to

do the TLS handshake, until the SNI information arrives,
choose the required B(ackend),
replicate the TLS handshake to it,
and then do the common bi-directional forwarding as proxies work in general.

The question is: is it possible with TLS, if the P does not know any of the keys?

is it possible with TLS, if the P does not know any of the keys?

Sure. SNI is part of the ClientHello message extensions, which is the first TLS message the client sends. At this point you do not yet have key material on the client side to encrypt this in all cases and even for session resumption, SNI is usually included to tell the server which old key material to use.
Though it may be that this setup breaks in the future if and when encrypted SNI (currently only a draft standard) is enforced.
A (rather minimal) example implementation of such a multiplexer is the dedicated slt package, but this functionality should be achievable with most standard reverse proxy setups, e.g. Apache.


Why Addition Mod 32? I was looking at the algorithm for Twofish, and I noticed that in some places a XOR is used, but in others, they use "addition modulo-32." What makes modulo-32 special? Why not always use XOR? Why not always addition mod 32?

The combination between addition modulo $2^{32}$ (not modulo $32 = 2^5$) - indicated by $\boxplus$ in the diagram - and XOR (i.e. bitwise addition modulo $2$) - indicated by $\oplus$ - makes the algorithm more non-linear.

Each of them for itself is a linear operation, but over different groups (addition in $GF(2^{32})$ vs. addition in $Z/2^{32})$, and the combination is slightly non-linear over both groups.

Why modulo $2^{32}$? This operation is already implemented in many processors (Java's int addition is this, for example), and this makes implementation easy and efficient.

The later Threefish cipher used in Skein takes this to a new level, its nonlinearity depending exclusively on this simple combination, in a really large number of rounds.


Is this function a secure PRF? I have a PRF function $F(k, F(k,0)) = 0$.
So that means, $k \times F(k,0) \rightarrow F(k, 0)$.

I hope you can help me understand if the function $F(k, F(k,0))$ is a secure PRF or no?

Thanks for considering my request!

I read the question as asking if $F$ can be a PRF, given that it is such that $F(k, F(k,0)) = 0$.

Assume you are given a black box that implements a function: given some input $x$, it outputs a result $y$, such that the same input $x$ always give the same output $y$. It is given that one of the following holds:

0: The box is a random oracle (equivalently: implements a Pseudo-Random Function); that is, the box outputs a random $y$ when given a new $x$, and otherwise outputs the same $y$ that it has output for that previously submitted $x$;
1: The box outputs $y=F(k,x)$ for some fixed unknown $k$, with $F$ your function such that $F(k, F(k,0)) = 0$.

You are free to use the box. Can you design an experiment to determine, with high confidence, which of 0 or 1 holds? If yes, what's that experiment? The definition of an experiment should include what input(s) it submits to the box under test, and what it performs with the box's output(s) and any other quantity that it manipulates in order to reach a decision/result that can be only be either 0 or 1. Such experiment would allow to recognize $F$ from a PRF, that is prove that $F$ is not a PRF.

More formally: you need to exhibit an experiment better than random at distinguishing 0 from 1, and prove that by showing it gives positive advantage (or, even more formally, non-vanishing advantage when the bit size of $F$ grows). The advantage (given by an experiment) is the difference between odds that the experiment concludes that 1 holds when 1 holds, minus odds that the experiment concludes 1 holds when 0 holds
$$Adv=\Pr[\,\text{Exp}(1)=1\,]-\Pr[\,\text{Exp}(0)=1\,]$$
where the parenthesis after $\text{Exp}$ contains the situation in which the experiment is run. Reversing 0 and 1 leaves the advantage unchanged.

Many texts define the advantage with an absolute value: this addition is only there to fix an experiment that guesses wrong better than random, and consequently to allow simplifying the description of experiments by only telling the principle used to make some decision, leaving the decision itself unspecified.

Defining the experiment clearly is the first step in a proof involving computing its advantage. In the context, experiment has alternate names: algorithm is more formal; I find adversary  more descriptive of reality, but it is known to create confusion with advantage.


Very basic modular example This is a very basic question, but I cannot get it right. I'm working on a basic asymmetric encryption example.

So $(m^e)^d  \equiv m \pmod n$
(at least with the premise of m < n, I suppose)

If I choose:

m = 14   (my message)
n = 19
e = 3
d = 13  -- because $3 \cdot 13 ≡ 1 \pmod{19}$

Then I encrypt
$14^3 ≡ 8 \pmod {19}$

But I decrypt
$8 ^ {13} ≡ 8 \pmod {19}$

What am I doing wrong?

EDIT My logic behind this is:

$m^e ≡ m' \pmod n$

if $e \cdot d≡1 \pmod n$ then

$m'^d ≡ m \pmod n$

Because $(m^e)^d = m^{e \cdot d} ≡ m^1 \pmod n$

Trying to follow as reference Burt Kaliski's The Mathematics of the RSA Public-Key Cryptosystem, the question has the following issues:

The question selects $n=19$ as a prime, rather than as the factor of two distinct primes $p$ and $q$ ($p=5$, $q=11$, $n=55$ in the reference); this is however not disastrous, and we'll adapt the reference by taking $n=p$ and ignoring $q$.
The question uses $d$ such that $e\,d\equiv1\pmod n$, when nothing suggests that in the reference; the reference uses $e\,d\equiv1\pmod L$ with $L=\operatorname{lcm(p-1,q-1)}$, and with our adaptation that becomes $L=n-1$, thus the relation between $e$ and $d$ should be
$$e\,d\equiv1\pmod{(n-1)}$$
The question ignores the stated requirement that $e$ is relatively prime to $p-1$ and $q-1$ (meaning: $e$ shares no prime factor with either $p-1$ or $q-1$); with our adaptation this becomes that $e$ is relatively prime to $n-1$. It follows that $e=3$ is an invalid choice for $n=19$, since $3$ divides both $e=3$ and $n-1=18$.

If we keep $n=19$, we can use $e=5$, find $d$ such that $e\,d\equiv1\pmod{18}$, e.g. $d=11$. Then $c=m^e\bmod p=14^5\bmod19=10$, and $m'=c^d\bmod n=10^{11}\bmod19=14=m$, as expected.
Note: I use $c$ for the ciphertext as in the reference, and $m'$ for the the result of the decryption.

This is an application of Fermat's little theorem, which states that if $p$ is prime, then for all $m$ not divisible by $p$, it holds that $m^{p-1}\equiv1\bmod p$.

Notice that since we chosed $d$ with $e\,d\equiv1\pmod{(n-1)}$, it holds that $e\,d=k(n-1)+1$ for some integer $k$.

Now, the way we computed $m'$, it holds that
$$\begin{align}m'&\equiv c^d&\pmod n&&\text{ using }m'=c^d\bmod n\\
&\equiv{(m^e)}^d&\pmod n&&\text{ using }c=m^e\bmod n\\
&\equiv m^{e\,d}&\pmod n\\
&\equiv m^{k(n-1)+1}&\pmod n&&\text{ using }e\,d=k(n-1)+1\\
&\equiv {(m^{n-1})}^k\,m&\pmod n\\
&\equiv 1^k\,m&\pmod n&&\text{ using FLT}\\
&\equiv m&\pmod n\\
\end{align}$$
Note: when using the FLT, we rely on $n$ prime, and $m$ not divisible by $n$, which holds.

Since $m'=c^d\bmod n$ it holds that $0\le m'<n$. We have $0<m<n$ and $m'\equiv m\pmod n$, hence $m'=m$ Q.E.D.

An incorrect assumption made in the question's reasoning is that it would hold that $m^i\bmod n=m^{(i\bmod n)}\bmod n$; that's false in general, and a proof is given by the computations in the question.

What really holds is that $m^i\bmod n=m^{(i\bmod\lambda(n))}\bmod n$ where $\lambda$ is the Carmichael function, and $m$ is coprime with $n$ or $n$ is square-free. The later holds in RSA. In the reference $n=p\,q$ with $p$ and $q$ distinct primes, and $\lambda(n)=L=\operatorname{lcm}(p-1,q-1)$.

Standard notation, used in this answer (but not the reference, which omits parenthesis in the first notation): for $w>0$

$u\equiv v\pmod w$ means that $w$ divides $u-v$
$u=v\bmod w$ means that $w$ divides $u-v$ and $0\le u<w$.


Key Generation for TOTP in TLS So lately I've been studying the TLS Protocol. In particular, going through RFC 2246, section 7.4.7.1, i.e, RSA Encrypted Premaster Secret Message, I encountered:

  If RSA is being used for key agreement and authentication, the
  client generates a 48-byte premaster secret, encrypts it using
  the public key from the server’s certificate or the temporary RSA
  key provided in a server key exchange message, and sends the
  result in an encrypted premaster secret message. This structure
  is a variant of the client key exchange message, not a message in
  itself.

On the server side I have decrypted a “.key.enc” file using the server RSA private key. The output is as follows:

otpauth://totp/381151134?secret=X2WXGSZ5LSZ66TX6AGL4DIJ6XJAAEJQ2ZUJDM4KJFNWAJOD4GI7Q

I've also read that 46 bytes out of the 48 bytes are randomly generated. However, I believe I'm getting something wrong here since evidently there is no sign of 46 bytes of randomness in the output file.

As far as I know 381151134 is called a “label”, “TOTP” stands for “Time-based One-Time Passcode” and “OTPAUTH” determines the authentication scheme.

Can someone point out what I might be missing or getting wrong here?

Besides that, I have another related question:

The IBM Knowledge Center states…

  For server authentication, the client uses the server's public key to encrypt the data that is used to compute the secret key.

… but they don’t provide any detailed information on how that’s done.

Can you additionally point me to a reference paper or some documentation that describes how the secret X2WXGSZ5LSZ66TX6AGL4DIJ6XJAAEJQ2ZUJDM4KJFNWAJOD4GI7Q
is generated? I do know that this is Base32 encoding. However, I'm specifically asking about the steps before the encoding, possibly the use of a 256 bit output hash algorithm (such as SHA256) since there are 52 Base32 characters.

EDIT:
Based on a comment my question seems vague in its current form. Further details:

I have been able to generate TOTP codes using the SECRET. I was able to authenticate to a server using the SECRET. Therefore, I guess the SECRET is a HMAC key. The main problem here however is that, how is the SECRET generated. Regarding the connection to TLS, the previous link from IBM Knowledge Center sounds informative. In addition, as I mentioned above the OTPAUTH link was encrypted with a RSA public key and sent to the server. I (may erroneously) believe this is part of the handshaking process in TLS

You seem to be confusing a few things here, mainly OTP schemes and TLS.
There really is no strong relation between the two, except for maybe the case that more often than not, you use OTP schemes over TLS.

The IBM Knowledge Center links makes a reference to the pre-master secret which is encrypted using the server's public key and then used (along with client's and server's nonces) to derive the actual master secret in TLS.

In OTP schemes, the shared secret is usually generated at random with the appropriate length and then encoded for better handling.

With common RSA connections, the server doesn't actually look at the pre-master secret and just takes what you give him. More often than not, he doesn't care what it actually is.

The fact that the OTPauth string was encrypted using the server's key was probably meant as a security measure to enforce access to the server's private key to be able to give out / verify OTPs. Or it may indeed as suggested be an try to let the client pick the shared OTP secret so not all clients are screwed in case of a partial leak of the secrets.

The numbers before the secret should encode usage parameters and / or give the secret a name for further processing.


Proof of the standard pseudorandom generator + XOR encryption scheme in Goldreich Reading Goldreich's Foundations of Cryptography II, I found this proof for the security of the common pseudorandom generator + XOR encryption scheme (Proposition 5.2.12 in the book):

  Assume you have a secure pseudorandom generator $g \colon \{ 0,1\}^n \to \{0,1\}^m$, and you construct your encryption scheme in the standard way by XOR'ing the output of $g$ to a message of length $m$. To prove that this is one-message-IND-secure, Goldreich proceeds as follows:

  Assume, for the sake of contrdiction, that there is an adversary $\mathcal{A}$ (really a poly-sized circuit in the book, but that is not important here) against this encryption scheme, such that for $x,y \in \lbrace 0,1 \rbrace^m$, $U_n \in \lbrace 0,1 \rbrace^n$ and
  polynomial $p$ we have: $$ |Pr[\mathcal{A}(x \oplus g(U_n)) = 1] -
 Pr[\mathcal{A}(y \oplus g(U_n)) = 1] > \frac{1}{p(n)}.$$
  Observe that for $U_m \in \lbrace 0,1 \rbrace^m$ we have: $$  Pr[\mathcal{A}(x \oplus U_m) = 1] = Pr[\mathcal{A}(y \oplus U_m) =
 1].$$
  Then, WLOG: $$ |Pr[\mathcal{A}(x \oplus g(U_n)) = 1] - Pr[\mathcal{A}(x \oplus U_m) = 1]| > \frac{1}{2p(n)},$$ which
  contradicts the security of $g$ (since we can distinguish its output
  from random).

My question

How do you get to that last inequality in step 3? In particular, how do you derive the term $\frac{1}{2p(n)}$?

The inequality is obtained by a distance argument.

Consider two points $X,Y$ on the real line. Taking another point $Z$, you have $|X-Z| + |Y-Z| \geq |X-Z+Z-Y| = |X-Y|$.

Applying this "triangle" inequality to your equality 1, we have for any $z \in \mathbb{R}$,
$\begin{array}{l}
 \bigl\lvert\Pr[A(x\oplus g(U_n))=1] - z\bigr\rvert
 + \bigl\lvert \Pr[A(y\oplus g(U_n))=1]- z\bigl\rvert \\
 \geq \bigl\lvert\Pr[A(x\oplus g(U_n))=1] - z + z - \Pr[A(y\oplus g(U_n))=1]\bigr\rvert \\
 = \bigl\lvert\Pr[A(x\oplus g(U_n))=1]-\Pr[A(y\oplus g(U_n))=1]\bigr\rvert \\
 > 1/p(n). \\
\end{array}$

By setting $z = \Pr[A(x \oplus U_m)=1] = \Pr[A(y \oplus U_m) = 1]$, we have
$\begin{array}{l}
 \bigl\lvert\Pr[A(x\oplus g(U_n))=1] - \Pr[A(x \oplus U_m)=1]\bigr\rvert \\
 + \bigl\lvert \Pr[A(y\oplus g(U_n))=1]-\Pr[A(y \oplus U_m) = 1]\bigr\rvert \\
 > 1/p(n). \\
\end{array}$

The one of two absolute values is bigger than $1/(2p(n))$.
Therefore, WLOG, you obtain your equation 3.


How to encrypt this using caesar cipher? I recently had an exercise that read:

  Encrypt the message "easy question" using Caesar Cipher defined as:
  C=E(P)=(Pi+3) mod 26

What is this formula and how to solve it?

The formula reads:

C: ciphertext of a character
E(P): encryption using Caesar of plaintext character =
(Pi + 3) mod 26: index of character in alphabet, plus 3 (the key) and then  modulus 26, the size of the alphabet

So basically for A you encode the value to 0 and add 3, which gets you the value 3, which decodes back to D. For Y you use 24, add 3 and get 27. However, when you do mod 26 you get the value 2, which decodes back to B. So basically you go 3 characters to the right, wrapping around to A after you've reached Z.

Decryption is simply the reverse.


Openssl & RSA : how many public exponents are possible? I would like to know if it is possible to set the public exponent we want with "OpenSSL RSA" or if it is really limited to 2 possible exponents:

3
65537

If yes, why ?

The public exponent of a RSA key is, nominally, an odd integer $e \geq 3$. Any such integer can be used with RSA, although not necessarily with any modulus $n$: $n$ and $e$ must be such that $e$ and $\phi(n)$ are relatively prime to each other. This is why $e$ cannot be even: $\phi(n)$ is even, so it can never be prime to another even number. Apart from that, any odd integer can be theoretically encountered as a public exponent (not $1$, but some implementations will accept it nonetheless, although it is very weak).

A specific implementation of RSA may be more restrictive. OpenSSL appears to have, by default, the following limitations:

The modulus $n$ must not be larger than 16384 bits.
The public exponent $e$ must not be greater than $n$.
If $n$ is larger than 3072 bits, then $e$ must fit in 64 bits.

These conditions (especially the third) are fairly arbitrary, but so it is. In fact, you want to be even more restrictive, because of interoperability. For instance, the default RSA implementation in Windows (CryptoAPI) cannot process RSA public keys where the public exponent does not fit on 32 bits.

There is no known security advantage to large public exponents over small public exponents. However, there is a quite plain performance advantage to using small exponents, and the smaller the better. Which us why $e = 3$ should be preferred. Using $e = 65537$ is a well-entrenched tradition, for no real good reason (even with $e = 65537$, RSA public-key operations are still quite fast, so it does not matter much in practice).

"65537" was selected for several reasons:

Its binary representation contains mostly zeros, which gives a small performance advantage in a square-and-multiply algorithm (you still need to do 16 squarings, but only one non-squaring multiplication).
It is prime, which is good for some key generation algorithms: for a RSA key, you need to generate two big primes $p$ and $q$, such that $e$ is relatively prime to $p-1$ and $q-1$. By choosing $e = 65537$, you can generate $p$ and $q$ without caring about $e$, and just start over if the "relatively prime" condition turns out not to be fulfilled (happens with probability $1/65537$ for each prime, so quite rarely).
It is bigger than $3$, which appeases people.

None of these reasons is really strong. Public-key operations in RSA are fast anyway; and $e = 3$ is the fastest you can get. If you really need ultimate performance for public-key operations, then $e = 65537$, while being about the best 17-bit exponent you can find, is still substantially slower than RSA with $e=3$. Not that it really matters most of the time (private-key operations are where performance issues usually are; and if you really need the extra cycles for public-key operations then you should use Rabin signatures, not RSA).

Prime generation can take into account the public exponent, e.g. you can generate candidate $p$ values as $p = 3r+2$ where $r$ is an odd random integer; this ensures that $p$ will not be a multiple of $3$ and that $p-1$ will be relatively prime to $3$ too. This process can be extended to ensure that not only $p-1$ will be relatively prime to your pulbic exponent of choice, but also that the candidate $p$ will not be a multiple of 2, 3, 5, 7, 11, 13... which will make bad candidate pruning faster.

The qualms some people have about $e = 3$ are the consequences of an old piece information that got corrupted along the way and turned into a myth. See this answer for details.


Ed25519 cryptanalysis and backdoor? I am looking to implement Ed25519 for decentralized identity at scale.

Has Ed25519 has gone through rigorous cryptanalysis?

Could there be a backdoor in the algorithm?

if Ed25519 has gone through rigorous cryptanalysis

It is based on Curve25519 which has gone through extensive cryptanalysis. The Ed25519 signature scheme as well is being heavily reviewed and adoption is rapid. There are already a number of papers on the algorithm itself, as well as a few papers on specific implementations. Every part of the algorithm and design decisions are justified in the paper introducing it.

  if there are any possible backdoor in the algorithm?

The algorithm is based on simple* and easy to explain parameters. This is explained here, where various ECC curves are compared and contrasted. Compared to many other common curves, Curve25519 does not use any long, strange, inexplicable parameters like some other curves do. Ed25519, naturally, uses the same curve with the same explainable curve parameters: $y^2 = x^3 + 486662x^2 + x$, modulo $p = 2^{255} - 19$. These parameters are all justified in the relevant paper introducing the curve. Compare this with, say, the NIST curves which all have very strange, long, and unexplained parameters.

Additionally, the algorithm was designed by Daniel J. Bernstein, a cryptographer who is well-known for going to court and fighting against the government when it tried to weaken cryptography. It is not designed by a nameless cryptographer or pushed by a sketchy group.

* Simple if you're familiar with elliptic curve mathematics.


What signature aggregation schemes support valid single signature is exist in aggregation signature? For example, there are three signers, A, B, C:

A: PK(a) SK(a) MessageA SignatureA
B: PK(b) SK(b) MessageB SignatureB
C: PK(c) SK(c) MessageC SignatureC

and generate a signature aggregation : SignatureAgg.

Is exist a method to check that if SignatureB contains in SignatureAgg, and do not know SignatureA and SignatureC.

If $A,B,C$ are the three strings, then one could let

$$f(A,B,C) = Hash(A)\,||\,Hash(B)\,||\,Hash(C)$$

where $Hash$ is a publicly known one way permutation.  Then, one can compute $Hash(B)$ and check if it is equal to one of the blocks of $f(A,B,C)$.  Since $Hash$ is one way, knowing $B$ and $f(A,B,C)$ does not leak information about $A$ and $C$.


differential cryptanalysis cipher for the final round I have a problem to find the sub-key.
The  system is…

For each round, we make the following stage:

We add the round key $K_i$.

Substitution : we have 8 blocks of 4 bits, and an S-box takes each block.
S = [7,3,6,1,13,9,10,11,2,12,0,4,5,15,8,14]

Permutation : circular shift of 2 to the right.

I choose the differential $\Delta(1 \implies 4)$ because after the permutation the differential trail is $\Delta(1 \implies 4 \implies 1)$.
I coded in C, the algorithm to find the $K_5$, the sub key after 5 rounds.
plainText[m] is a random message and plainText[m+1] is plainText[m] ^ 1(difference).
 0000   0000   0000   0000   0000   0000   0000   0001
------ ------ ------ ------ ------ ------ ------ ------
| S1 | | S2 | | S3 | | S4 | | S5 | | S6 | | S7 | | S8 |
------ ------ ------ ------ ------ ------ ------ ------
 0000   0000   0000   0000   0000   0000   0000   0100
                                                    \
 0000   0000   0000   0000   0000   0000   0000   0001
------ ------ ------ ------ ------ ------ ------ ------
| S1 | | S2 | | S3 | | S4 | | S5 | | S6 | | S7 | | S8 |
------ ------ ------ ------ ------ ------ ------ ------
 0000   0000  0000    0000   0000   0000   0000   0100

I tested the function of encryption and decryption, it operates normally.
The problem is that I get a uniform array, because when I decrypted message, the differential trail is good for all the keys while normally this should not always be the case for any key for a message.
For example:
plaintText[i]=7584 and plaintText[i+1]=7585(7584 XOR 1).

In my code, for key=0,u=69b900ca and up=645100ca and tmp=2b131dd4 so beta=4. For key=1,u=69b900ca and up=645100cb and beta=4. The problem is that for any key, I get the same beta.


How to calculate the number of Linearly active Sbox I cant understand the concept of linearly active sbox. In the case of differential analysis it is more easy to understand the concept of 'active sbox'
Also how the increase in number of (linearly) active sbox improves the security of cipher

If any generic software programs are available to calculate the number of active sboxes, just by giving sbox functioning and permutation pattern?

I highly recommend reading Howard Heys's Tutorial on Linear and Differential Cryptanalysis available online (google is your friend) for a detailed explanation for the SPN case.

In brief, if a linear expression $a\cdot x+ b\cdot S(x)$ is used then all the output wires that correspond to 1 bit in the vector $b$ turn on the Sboxes they are connected to in the next round. It's best to start with one active Sbox in the initial round to turn on as few Sboxes as possible in the next round (by choosing $a$ and $b$ so that $b$ has a minimum Hamming weight but at he linear expression has a large bias).

See also the answers to this question and this one.

AES turns on the maximum number of Sboxes in a different way, since there are no bit permutations but a diffusion matrix. See a nice explanation in this answer.


Difference between function $f$ in eval and dec of homomorphic authenticated encryption In the homomorphic authenticated encryption, as described 1, there are Eval and Dec PPT algorithms:

In Eval, f is the function to be performed on the encrypted data. However, I need to know why it is used in Dec algorithm?

The key-word "authenticated" mean that Dec is has not just a decrypting functionality. It should also check the validity of the computation made. that's why it takes as input the function $f$. Read more in details the paragraph "4.4 Authenticity".


Explaining the reason of radically more accuracy while using different set of hash functions instead of same set of hash functions on some operations So I am looking for an explanation of an experiment.
In this experiment, I took a set of k hash functions. Say the total number of data points I am working on is d. Call an algorithm A which used that set of hash functions to do some operations on d data points and have modified them to a matrix B.It is mentionable that algorithm A introduces a bunch of randomization. So applying algorithm A different times with same set of hash functions and same set of data points will produce different results. Now we apply algorithm C on that matrix B and get a result, call it D.
So this is the summary of what I am trying to do in short.
Now I can do this multiple times in two ways-

I take a set of k hash functions in the beginning. Now I run algorithm A with the same
set of hash functions and on the same set of data points n times and produced n different matrixes and averaged the respective elements of those matrixes to produce a final matrix, call B'. So in short, the (i,j)th entry of the matrix B' is the average of (i,j)th entry of n matrixes we got before. Now , we run algorithm C on matrix B' and get a result D
I take a set of k hash functions, run algorithm A, generate matrix B and then run algorithm C on matrix B to produce result D. Now, I run this process multiple times, every time with a different set of hash functions and then average all such Ds and produce D'
Interestingly, process 2 gives just radically more accurate results and I don't know how to explain this behavior. One thing to mention, I was using sha256 in this experiment.
I hope to get help from kind people out here in order to solve this.
Thanks in advance!
Edit: This has been used for some differential privacy operations and the results accuracy is being measured by comparing with the ground truth
Edit2: By indicating that I used k different sha256 hash functions, I meant that I just generated k seeds and appended them before the string I am tryna hash, for example,

hex_num = hashlib.sha256((str(seed[i])+str(d)).encode('utf-8')).hexdigest()

Hope it is clear now

A possibility is that algorithm A is randomized, but at least one of the following holds

the source of randomness used is poor (e.g. tends to repeat), and using several sets of hash functions fixes that, merely by introducing more of the randomness necessary for accurate results (whatever that means) of the overall procedure.
there is no randomness fed into the input of at least one of the hash functions in a set, therefore changing that hash function adds some of the beneficial randomness.


NIST elliptic curves behaving anamolous in OPENSSL benchmark I tried to collect some benchmarks on NIST elliptic curves using charm library. The charm library is just a wrapper over OPENSSL. I experimented with prime192v1 (P-192), secp224r1 (P-224), prime256v1 (P-256), secp384r1 (P-384) and secp521r1 (P-521) curves. I calculated the time required to

(1) sample one group element,

(2) multiply 2 random group elements and

(3) exponentiate a group element with a random value in range [1, order of group].

Here's my code.

from charm.toolbox.ecgroup import ECGroup, G, ZR
from charm.toolbox.eccurve import prime192v1, secp224r1, prime256v1, secp384r1, secp521r1
from time import time
group = ECGroup(secp521r1)
count = 10000

g = []
a = []
t = time()
for i in range(count):
    g.append(group.random(G))
print("Random in G ", time()- t)

for i in range(count):
    a.append(group.random(ZR))
t = time()
for i in range(count):
    g[i]**a[i]
print("Exp in G ", time() - t)

t = time()
for i in range(count):
    g[i]*g[i-1]
print("Mul in G ", time() - t)

Here are the results. The benchmarks have many anamolies that I could not explain. For P-224 curve, it took unreasonably long time for sampling random element. For P-224 curve, if it takes 2.27microseconds for multiplication, then it should take at least 224*2.27microseconds (roughly 0.5ms) for exponentiation. But exponentiation is much faster. Exponentiation is unreasonably faster even for P-256 and P-521 curves as well. Can anyone please explain why this is the case?

Here is what's likely going on:

Charm represents Elliptic Curve points in affine coordinates, that is, explicit (x, y) values
When doing a single point addition, OpenSSL adds the two points (internally coming up with a point in projective coordinates) and then converts them back into affine coordinates.  Then final conversion involves a modular inverse operation, and so is moderately expensive (more expensive than all the other operations combined).
When doing an point multiplication, OpenSSL takes the point, and does a series of point additions/doublings, keeping the point in projective coordinates.  Then, at the end, it converts the point back into affine coordinates (which involves the modular inverse).  However, you end up doing a single modular inverse, even though a number of point additions/doublings were done.

Hence, because the point multiplication avoids the intermediate modular inverses, it runs faster than expected.


Is there such a thing as perfect CPA security? Consider the following experiment.

If we require that $$\operatorname{P}\left( \mathcal A \text{ succeeds} \right) = \frac{1}{2}$$ for any adversary $\mathcal A$ in order to call the scheme $\Pi$ perfectly CPA secure, can such a scheme exist?

It would seem like this definition cannot be met since the adversary can use the oracle access to compute $\text{Enc}_k(m_i)$ for $i=1,2$ as many times as necessary until one of them coincides with $c\leftarrow \text{Enc}_k(m_b)$, at which point $\mathcal A$ knows what $b$ is. Is my thinking correct?

The CPA indistinguishability experiment definition that you give is taken from Katz & Lindell's textbook.  In my copy (2nd Ed.), it's on page 74.

  It would seem like this definition cannot be met since the adversary can use the oracle access to compute $\text{Enc}_k(m_i)$ for $i=1,2$ as many times as necessary until one of them coincides with $c\leftarrow \text{Enc}_k(m_b)$, at which point $\mathcal A$ knows what $b$ is. Is my thinking correct?

One thing you're missing is that earlier the chapter stipulates that only probabilistic polynomial time (PPT) adversaries will be considered.  Earlier in the chapter (pp. 49-50):

  However, when it comes to the computational power of the adversary, we will from now on model the adversary as efficient and thus only consider adversarial strategies that can be implemented in probabilistic polynomial time.

So the first problem with your adversary is that you've not demonstrated that it is a PPT algorithm.  Significantly, if the number of calls to the encryption oracle is an exponential function of one of the security parameters (as brute force guessing algorithms tend to be), then it's disqualified.

The second problem is that the encryption algorithm is also PPT (see Definition 3.7, p. 52), which means it's probabilistic—it's allowed to make random choices.  This means that you can't assume it's the oracle is mathematical function—calling $\text{Enc}_k(m)$ multiple times with the same $m$ can (and should!) produce different results.


simple multiplication in GF(8) I am trying to do multiplication in the GF($2^3$) defined by the irreducible minimum binary polynomial $X^3+X^2+1$. I want to multiply $A(x) * B(x)$ where $A(x) = x$ and $B(x) = x^2$. The multiplication is easy, and I get the result: $C'(x) = x^3$ However, I am confused on how to do the modulo in $X^3 + X^2 +1$. I am convinced that it can be done by XOR'ing in long division: $1000 \oplus 1101 = 0101$. Is this the correct result then: $101$?

Yes, you are correct.

The modulo operation (in general, not only over polynomials) is defined such that this is always true:

$A \equiv A + B\ \  (\bmod\  B)$

Thus, if $A = X^3$ and $B = X^3+X^2+1$, that implies that $X^3$ is equivalent to the sum of $X^3$ and $X^3+x^2+1$, which is $X^2+1$, which is represented by $101$.


Finding Galois LFSR and its initial configuration Suppose recursion for output of Galois LFSR is $u_1=u_3=u_4=0$

What kind of taps are here, and initial state? How to uncover this information?

In general, you're missing both the polynomial (taps) and some symbols, so there is no unique solution.

The LFSR is determined by its generating polynomial and thus its degree/length/taps. If the LFSR is 5 bits or more in length you're out of luck, you need 5 equations so 5 bits of information for any hope of solving this.

If it is 4 bits long, and primitive, you're in general out of luck again in the absence of any extra information, since all loadings, and in particular both states
$$(s_1,s_2,s_3,s_4)=(0,s_2,0,0)$$ with $s_2$ arbitrary are possible.

However, if $s_2=0$ this will give a trivial LFSR of all zero output, so if you're not in this setting you can assign $s_2=1$ and proceed, if the LFSR is 4 bits long. Then you might try all possible primitive LFSRs (there are 2 of length 4) and have 2 candidates.

If it is 3 bits or less, again, if the all zero state can be ruled out, you can proceed by trying all primitive LFSRs and in fact now you have 4 bits of info (4 symbols after ruling out all zero state) for a $L=3$ so you should be able to determine the LFSR uniquely if it is primitive (there are 2 here).


S-boxes are not linear I am reading about S-boxes.

By looking for the reason why the S-boxes are not linear, I found the following:

The mappings $B \mapsto S(B)$ are all non-linear, since it holds

$S(000000) \neq 0000$

We notice that at each of the 8 S-boxes $S_1, S_2, \dots, S_8$ , the number at the upper left-hand corner is not equal to zero and so $S$ cannot be linear.

Could you explain to me why at the S-boxes the number at the upper left-hand corner is not equal to zero ?

I don't believe you're really asking 'why did they select an SBox with 0 being mapped to something other than 0"; essentially, that's what the designers picked.

Instead, it is "why does $S(0) \ne 0$ prove that S is nonlinear".

And, the answer to that is, yes, it does, but only pedantically.

A function $S$ is linear if $S(a) + S(b) = S(a + b)$ for every $a, b$ (and some reasonable addition function "+", generally, we use bitwise xor).  (And, this isn't quite sufficient if the range of $S$ is infinite, we never have to worry about that in crypto).

Now, if we select $a = b = 0$, this simplifies to $S(0) + S(0) = S(0+0) = S(0)$; or $S(0) = 0$.

Hence, if $S(0) \ne 0$, we know that the definition of linearity doesn't hold in all cases.

On the other hand, in crypto, when we talk about linear functions, we often really mean affine; the definition of this is $S(a) + S(b) = S(a + b) + c$, for all $a, b$ and some constant $c$ (which is independent of $a, b)$.  The reason we're interested in this is that essentially all the mathematical tools an attacker can use against a linear function also work against an affine one, and so we tend not to make a strong distinction.

And, just looking at $S(0)$ won't tell you if a function is affine, as we have $S(0) = c$, and $c$ can be any value.  If + is bitwise xor, you need to examine at least 4 values to prove that an Sbox is not affine.


Simply put, what does “perfect secrecy” mean? I would like to ask for a clear (but maybe not so deep) explanation of what the term "perfect secrecy" means.

As far as I have researched and understood, it has to do with probabilities of assuming that a certain variable will be the key for a certain cipher text. And unless I'm confusing some concepts, the one-time pad is the only cipher known to have perfect secrecy, since no amount of resources would be enough to break it.

My notions of probability are kind of weak, which is why I don't understand most documents that speak of it.

Perfect Secrecy (or information-theoretic secure) means that the ciphertext conveys no information about the content of the plaintext. In effect this means that, no matter how much ciphertext you have, it does not convey anything about what the plaintext and key were. It can be proved that any such scheme must use at least as much key material as there is plaintext to encrypt. In terms of probabilities, it means that the probability distribution of the possible plaintexts is independent of the ciphertext.
We contrast this with semantic security, which I define by quoting the seminal 1984 paper of Goldwasser&Micali:

Whatever is efficiently computable about the cleartext given the cyphertext, is also efficiently computable without the cyphertext.

For two examples, I quote my answer to this related question:

When used correctly, the One Time Pad (OTP) is information-theoretic secure, which means it can't be broken with cryptanalysis. However, part of being provably secure is that you need as much key material as you have plaintext to encrypt. Such a key needs to be shared between the two communicants, which basically means you have to give it to the other person through a perfectly secure protocol (eg by hand/trusted courier). So, actually it just allows you to have your trusted meeting in advance, rather than at the time of transmitting the secret information.
To illustrate this, consider what happens if one tries to brute force OTP? Since you have allowed an attacker infinite computational resources, he can keep guessing keys and calculating the appropriate plaintext until every key has been tested. Supposing the message was $b$ bits long, this would leave him with $2^b$ possible keys, each of which would generate a unique plaintext, making $2^b$ plaintexts. What is important here is that this means they would have candidate plaintexts corresponding to ever possible bit-string of length $b$. This means, even if you knew the message was "Meet me at the stadium at 2?:15" (where ? is 0,1,2 or 3), you still wouldn't have any idea what the ? was, because the possible plaintexts would contain this string with every possible value of ?.
Most cryptographic methods we use now are computationally secure. There are lots of different ways to do this, and I'll just sketch at a few of them. We might come up with a reduction to a problem conjectured to be hard (eg the Diffie-Hellman Problem or Discrete Log Problem). That is, we prove that "If you can break my cipher, you can solve [hard-problem]", meaning our problem is at least a difficult to solve as [hard-problem]. So, if the problem is indeed hard to solve, so must cracking our encryption be.


Is the private key of a private/public key pair also a symmetric key? I think I've got a fairly good (practical, not mathematical) understanding of symmetric versus asymmetric cryptorgraphy, so the difference between those is not the question.

In a local discussion someone said the private key (of a private/public key pair) would also be a symmetric key.

It was my understanding that this is not true, but I've not been able to find an authoritative answer to that question.

I found places that document "what has been encrypted using one key of the private/public key pair can only be decrypted with the other key of the pair."

Since the private key must be kept private with no exception for the concept to work, it would not hurt if it also was a symmetric key.

Thanks
Peter

In a local discussion someone said the private key (of a private/public key pair) would also be a symmetric key.

Well, not quite.  If we're talking about public key encryption (there are other flavors of public key cryptography), what is correct is that "what has been encrypted with the public key can be decrypted with the private key".

What this means is that to encrypt, you need the "public key".  That is, unless the private key had enough information for you to deduce the public key, you couldn't actually encrypt, and so it wouldn't work as a symmetric key.

Now, practically speaking, in most public key cryptosystems, the private key does have enough information to deduce the public key. However there is at least one example were it doesn't; large exponent RSA; where both exponents $e$ and $d$ are chosen to be large (and you don't insert the CRT parameters into the private key). With this system, given $N$ and $d$ (which is all the private key has), you cannot efficiently recover $e$ (and hence cannot encrypt, even though you can decrypt).

Of course, a public/private key pair, when considered as a unit, will work as a key in a symmetric system.  We do run into the practical issues that it is a hideously bad symmetric system (as any public key cryptosystem is slow and has huge ciphertext expansion, compared to any realistic symmetric cryptosystem), but it would work.

As a side note: if your document states:

  I found places that document "what has been encrypted using one key of the private/public key pair can only be decrypted with the other key of the pair."

Then either the document had context that stated that it was specifically talking about RSA, or it was written by someone who doesn't know what they're talking about.  Most public key cryptosystems cannot be described this way; they do not provide any way that allows talking about 'decryption' (recovering the original message) with the public key.  RSA can be described as a 'trap door' permutation (if you ignore padding, which in practice you can't), and so could many multivariate signature schemes (although those are mildly obscure); hardly anything else can be.


Increased CRC collision probability when adding bits to input message The Scenario

I have a message string I need to transport over a wireless network that may be unreliable. This message string is about 100 bits long, and is packaged with an 8-bit CRC. When the message is received, it's validated with the CRC and unpacked. I would like to add a few "message version" bits to the message, but there's no room available.

Solution Attempt

Since I can't add a version number to the message, I would like to add the message version bits to the input string when computing the CRC, but only transmit the basic message and CRC as before (without the version bits). When the message is received, I'll compute the CRC for Version 1. If it fails, I'll try computing the CRC for Version 2. If that fails, the message has been garbled. If either one succeeds, then I know the version number.

Question

The problem is that I need to prove (or at the very least, convince myself with math) that increasing the bit number of the input message doesn't significantly increase the probability of a CRC collision.

I do not need a perfect answer here, since I understand that network simulation and choice of the CRC polynomial play huge roles. I'm using 0x2F for my 8-bit CRC polynomial, if that matters. For network error, I think it's reasonable to assume the error noise is really random (unless you think otherwise... all advice welcome).

My Attempt

Source: http://web.mit.edu/course/16/16.682/www/leca.pdf (See section "Performance of CRC")

When using the equations in this document, I find that the probability of detecting a transmission failure depends only on the number of bits in my CRC (r=8, in this case), so P = 1 - 2^(-r) = 99.6%. But surely the input bits matters in some way, right? I've seen this in other papers too, but I can't figure out if a simplification is being made. Help!

Thanks!

First of all, if your goal is to keep the garbled messages to "once every hundred years", well, you already don't meet that goal, even before the change.  With an 8 bit CRC, a random change has a probability 1/256 of being accepted; hence if your wireless network has a transmission error at least once every three months (which, to me, sounds like an unrealistically reliable transmission mechanism), you get an undetected garbling more often than "once every hundred years".

Now, what you're doing is effectively assigning two different CRC (or hash) values for each message; when you receive a message and its CRC (hash), you'll accept the message if either of those two hash values appear in the received CRC field, and reject the message if it's any of the other 254 values.  Hence, you're reducing the probability of undetected error from 1 in 256 to 1 in 128.  The actual values of the bits don't really change this, as long as we model the garbling process as 'random'.

Now, the CRC algorithm has the nice property that if the error is limited to an n-bit burst (that is, all bits outside of that n-bit region are received correctly, with n=8 in your case), then it'll always detect the error.  This is a nice property if the garbling process will tend to affect only limited portions of the entire message.  However, I don't see how you can maintain that property (even with n=7), while maintaining backwards compatibility (which I suspect is important).

So, the bottom line is that your idea will make undetected errors more likely; however you're already not meeting your stated goal.  You may need to rethink this protocol more drastically if your reliability requirements are a hard requirement.


Breaking the 40 bit DVD CSS stream cipher This is from the transcript of Dan Boneh's Coursera Crypto course
https://www.coursera.org/learn/crypto/lecture/mQAkP/real-world-stream-ciphers

So it turns out this is easy to break in time roughly two to the
seventeen. Now let me show you how. So suppose you intercept the
movies, so here we have an encrypted movie that you want to decrypt.
So let's say that this is all encrypted so you have no idea what's
inside of here. However, it so happens that just because DVD
encryption is using MPEG files, it so happens if you know of a prefix
of the plaintext, let's just say maybe this is twenty bytes. Well, we
know if you XOR these two things together, so in other words, you do
the XOR here, what you'll get is the initial segment of the PRG. So,
you'll get the first twenty bytes of the output of CSS, the output of
this PRG. Okay, so now here's what we're going to do. So we have the
first twenty bytes of the output. Now we do the following. We try all
two to the seventeen possible values of the first LFSR. Okay? So two
to the seventeen possible values. So for each value, so for each of
these two to the seventeen initial values of the LFSR, we're gonna run
the LFSR for twenty bytes, okay? So we'll generate twenty bytes of
outputs from this first LFSR, assuming—for each one of the two to the
seventeen possible settings. Now, remember we have the full output of
the CSS system. So what we can do is we can take this output that we
have. And subtract it from the twenty bites that we got from the first
LFSR, and if in fact our guess for the initial state of the first LFSR
is correct, what we should get is the first twenty-byte output of the
second LFSR. Right? Because that's by definition what the output of
the CSS system is. Now, it turns out that looking at a 20-byte
sequence, it's very easy to tell whether this 20-byte sequence came
from a 25-bit LFSR or not. If it didn't, then we know that our guess
for the 17-bit LFSR was incorrect and then we move on to the next
guess for the 17-bit LFSR and the next guess and so on and so forth.
Until eventually we hit the right initial state for the 17-bit LFSR,
and then we'll actually get, we'll see that the 20 bytes that we get
as the candidate output for the 25-bit LFSR is in fact a possible
output for a 25-bit LFSR. And then, not only will we have learned the
correct initial state for the 17-bit LFSR, we will have also learned
the correct initial state of the 25-bit LFSR. And then we can predict
the remaining outputs of CSS, and of course, using that, we can then
decrypt the rest of the movie.

I don't understand what he means by the sentence which I have bolded - "Now, it turns out that looking at a 20-byte sequence, it's very easy to tell whether this 20-byte sequence came from a 25-bit LFSR or not."
How do you tell this whether the 20-byte sequence came from a 25-bit LFSR?

There is a Berlekamp-Massey algorithm that constructs the shortest LFSR for a given binary sequence.
For an LFSR of length $L$ given $2L$ output sequence from the LFSR, it is enough to construct the LFSR. To construct a 25-bit LSFR, 50 bits is enough. Note that, the algorithm doesn't need to know the taps. It just constructs the minimum LFSR that can produce the given sequence.
Looking at the 20-byte (160-bit) you can make sure that the remaining 110-bits are output from the LFSR. We don't expect that with a negligible $1/2^{110}$ probability the LFSR will succeed to produce the random bits.
To Study the LFSR's

Solomon W Golomb's book Shift Register Sequences: Secure And Limited-access Code Generators, Efficiency Code Generators, Prescribed Property Generators, Mathematical Models (Third Revised Edition), is advised.


Cryptographic Arithmetic Toolbox/Software This term I have many cryptography courses treating finite fields.
I was wondering if there is any good software that could help doing basic operations in galois fields etc.
I already googled but found nothing appropriate.

What I would need:
A tool/software that can calculate in arbitrary galois fields gf(p^n)

(+,-,*,/,gcd, inverse)

In addition to that I would need a function to generate an irreducible polynomial for a given field. (parameters could get big e.g. 2^100)

I already considered matlab generating a irreducible polynomial for gf(2^103), but computation takes too long.

Do you have any recommendations and do you know any good programs for calculation in finite fields?

Thanks.

You can use Sage or MATLAB. Among the two sage is free and uses python as the programming language.


Sigma protocol: witness hiding I am working on an assignment and I am stuck with the last part of proving witness hiding for the protocol.

I have previously proved it is witness indistinguishable, and it has q (primer number chosen as in Schnorr's protocol) different values for the witness.

The protocol goes as follows:

To prove the witness hiding it is hinted to show two things:

1.) if an adversary computes a valid witness (w1', w2') for a conversation it will be a different one with a high probability

I assume this is just due to that fact of witness hiding, e.g. the conversation tells noting about which of the q different witnesses was used.

2.) But if such a different pair is computed, one can compute the dsicrete log of g1 base g2.

I am pretty much stuck on this part.

I get to a point where I have an equation like this
$$
g_1^{w_1}\cdot g_2^{w_2} = g_1^{w'_1}\cdot g_2^{w'_2} \text{ mod p}
$$

But where to go from here...

The second point is very simple:
if you have $w_1, w_2, w'_1, w'_2$ so that $g_1^{w_1} g_2^{w_2} = g_1^{w'_1} g_2^{w'_2}$, then $$g_1^{w_1-w'_1} = g_2^{w'_2 - w_2},$$
and having $g_2 = g_1^{x}$ for some unknown $x$,

$$g_1^{w_1-w'_1} = g_1^{x(w'_2 - w_2)},$$
or equivalently
$$w_1 - w'_1 = x(w'_2 - w_2)\mod q,$$

where $q$ is an order of the group.

Finally, $$x = (w_1 - w'_1)(w'_2 - w_2)^{-1}\mod q$$

The first your point is rather due to witness-indistinguishability property


Who calculates the private exponent $d$ in RSA? Who calculates the private exponent $d$ in RSA? Only $(n, e)$ are public and to calculate $d$ (with $d$ being the multiplicative inverse of $e$ with respect to $\phi(n)$), the receiver need $\phi(n)$.

So how is the receiver getting $\phi(n)$ and if the receiver is not getting $\phi(n)$ then who is calculating $d$?

In RSA, the owner of the private key calculates $d$, unless otherwise stated.

In public key cryptography, including RSA:

The public key allows to encipher or/and verify signature.
The private key allows to decipher or/and sign.
Unless otherwise stated it is assumed that the owner/holder of the private key has generated both that private key and the public key, and does not reveal the private key.
In practice, some device (computer, HSM, Smart Card..) and code does that task, perhaps under supervision of some person not the holder/owner of the private key (which might be a computer, sometime not the one used for the generation); this is typically ignored in cryptography, and considered part of computer security.
Unless otherwise stated it is assumed that, somewhat, all public keys get known to all, without alteration or impersonation of who their owner is.
In practice, this is often done using digital certificates.


Difficulty of breaking RSA for a given key size Is it true that breaking a 1024-bit RSA key is as difficult as breaking a 128 bit symmetric key (e.g. AES)? I know that breaking a RSA key is equivalent to factoring the modulus $N$. To factor it, you  have to see if any number between $2$ and $N/2$ divides $N$, right? But that would still be much greater than $2^{128}$ trials (which is the worst-case scenario for cracking a 128 bit AES key).
Then, how is breaking a 128-bit AES key the same as a 1024-bit RSA key?

No. Breaking a 1024 bit RSA key is not as difficult as breaking a 128 bit symmetric key. The consensus is that it is considerably less difficult, perhaps more comparable to breaking a 80-bit symmetric key, which is $2^{48}$ times less difficult than breaking a 128-bit key; that's a lot less difficult (a hundred million million times less difficult).

The reason is that breaking a 1024 bit RSA key can be attempted using an integer factorization algorithm, without exhaustively trying divisors. For the state of the art, see this article on the current factorization record.


Is format preserving encryption suitable for use with words or names? Is it possible to use FPE to encrypt names and language words like 'Bob' 'the' 'tree', in order to preserve both length and format (like keeping characters within a certain range like A-Z a-z)

The only way I can think of at the moment is to reduce each character to it's decimal value  and encrypt that.  But that doesn't seem very secure (wouldn't each character map to exactly the same value each time?)

The obvious way to FPE strings of $N$ characters of [A-Za-z] is to treat the string as a base-52 value (with each character being a digit, say, A=0, B=1, ..., y=50, z=51); do a base conversion of that to an integer between 0 and $52^N-1$; use a standard FPE technique to encrypt that value into another integer between 0 and $52^N-1$, and do a base conversion back into a string of $N$ characters of [A-Za-z].

Because you're encrypting the string as a whole, you don't have the data leakage you would have if you encrypted each character individually.


PKCS#11: Can C_GetMechanismInfo() return CKR_OK on a disabled mechanism? According to PKCS#11 v2.20, "C_GetMechanismInfo obtains information about a particular mechanism possibly supported by a token." Does that mean C_GetMechanismInfo() can return CKR_OK on a temporarily disabled mechanism? For example, if C_GetMechanismList() does not return CKM_MD5 in the result then is it OK for C_GetMechanismInfo(CKM_MD5) to return CKR_OK?

The caller may invoke C_GetMechanismInfo for a mechanism that does not appear in the list returned by C_GetMechanisList, where the latter "... is used to obtain a list of mechanism types supported by a token".

I believe that's the reason they added the adverb possibly.

I am not sure what you refer to as "temporary disabled". To me, if the token is not in a state that allows a certain mechanism (temporarilly or permanently), C_GetMechanismInfo should return CKR_MECHANISM_INVALID or at the very least not CKR_OK.


What is CCM -- Counter Mode Cipher Block Chaining Message Authentication Code Protocol CCM puts together two different modes of operation (at least in the name). Does it mean data is encrypted using counter mode and then encrypted using CBC; kind of a double encryption?

CCM puts together two different modes of operation (at least in the
  name). Does it mean data is encrypted using counter mode and then
  encrypted using CBC; kind of a double encryption?

Yes, kinda.
With the CCM mode of operation, you authenticate your data first using CBC-MAC which is, well, basically CBC on the data to be authenticated.

Now on the combination of ciphertext and tag you apply the CTR mode to conceal the contents. While you do "double-encryption" here, you only send the full result of the CTR mode and only the very last block from the CBC mode (encrypted using CTR). The latter one is the tag with which the recipient can verify the integrity of the message.


Is this an error in the Pinocchio Protocol paper I am going through the Pinocchio protocol paper and I need 2 clarifications in the section Protocol 1 (Verifiable Computation from strong QAP). The part that explains the Verify process, which contains this expression:
$$e(g^{v_0}.g^{v_{io}}.g^{v(s)}, g^{w_0}.g^{w(s)})/e(g^{y_0}.g^{y(s)},g) = e(g^{h(s)},g^{t(s)})$$.

since $e:G \times G \to G_T$, what is the definition of the division operation as shown in the expression above, wrt $G_T$?
If my understanding is correct, the first term in the first pairing should be $g^{v_0}.g^{v_{io}}.g^{v_{mid}(s)}$ instead of $g^{v_0}.g^{v_{io}}.g^{v(s)}$

The first part of the question is answered in the comments. Regarding the second part, yes, indeed, you are right! It's a typo in the Pinocchio paper, Section 2.3. Protocol 1., you also linked. The problem is that the left hand side of the verification equation enumaretes the I/O related coefficients twice in the left wire polynomial, V, therefore $g^{v_0}.g^{v_{io}}.g^{v_{mid}(s)}$ should be instead of $g^{v_0}.g^{v_{io}}.g^{v(s)}$ in the first argument of the first pairing.

However, in the original version of the protocol, see the end of Section 3.1., this typo error is not present.


ECDSA Public Key generation Referring to both

Wikipedia page and
ECDSA-cert paper

I can understand that, given $\mathcal{E} = \mathcal{E}(a,\,b,\,\mathbb{F}_{2^m})$ as our elliptic curve on $\mathbb{F}_{2^m}$ group

$G \in \mathcal{E}$ is a generator of the group, i.e. $\exists n: n\times G = O$
$n$ is the order of point $G$ with respect to the group
choosen randomly $d_A\in[1,n-1]$ as a private key,
$Q_A\triangleq n \times d_A$ is the public one.

Got it, but in the "Key pair validation from Bob" process, I see that $Q_A$  must respect these bounds:

$Q_A \neq O$ (trivial)
$Q_A \in \mathcal{E}$ (trivial)
$Q_A\times n = O$

I can't really understand the last thing. I'm not very acquainted with EC algebra, but comparing $Q_A\times n = O$ with $n\times G = O$ seems the same thing, so I would conclude that $Q_A=G$, which is clearly false.

What am I missing?

Actually you have a bug in your step of key generation, it should be $Q_A=d_A \times G$ and you want to have a point $G$ of large prime order $n$ such that the ECDLP is hard on the group.

The last check ensures that the public key $Q_A$ is a point of order $n$. If this is the case, then $Q_A\times n = (d_A \times G)\times n = d_A\times(n\times G)=d_A\times O=O$.

This check seems simply to rule out the generation of public keys that lie in a small order subgroup (and thus could be easy to break) - which makes no sense if you have a prime order group but can happen if you have an almost prime order group (you have subgroups of order of divisors of the cofactor). Just a mechanisms to check if the key generation did not generate such a key for you (it should not happen in practice that you generate such a keypair), but the implementation may be messy and you can check that with this test.


question on encryption of multiple distinct messages When I study symmetric encryption, it is quite straightforward to understand the following: in the presence of eavesdropper, simply using a PRG $G(k)$ and XORing multiple messages won't provide indistinguishability in the similar fashion as for a single message.

But what happens for multiple distinct messages? Will a simple PRG $G(k)$ provide indistinguishability?

I know there is discussion on deterministic CPA-secure schemes which could use synthetic IV, etc. But do we really need to go that far?

What is the difference? the distinct messages make the (key, message) pair distinct already? does it depend on how we define indistingushability?

Thanks!

It does not work either. There are a few counter examples:

Let $x=G(k)$ be the key stream, which I understand you want to use to encrypt multiple messages

1 $m_1=0^l$ and $m_2=r \in\{0,1\}^l$, once you encrypt $m_1$, the ciphertext $m_1\oplus x = x$ is exactly the key stream, that can be used to decrypt the ciphertext of $m_2\oplus x\oplus x=m_2$. Note $m_1$ and $m_2$ are distinct.

2 Let $m \in \{0,1\}^{l-1}$, $m_1=m||0$, $m_2=m||1$, $m_3 =r \in\{0,1\}^l$, then given the ciphertext of $m_1$, in a CPA game, the adversary can easily distinguish $m_2$ and $m_3$. All 3 messages are distinct.

The main problem is that distinct means the messages are not equal, but nothing more on their distributions. Therefore, it is insufficient to ensure the indistinguishability of ciphertexts.

When you use an iv, which is a long enough random string, the iv is used as input to $G$ (well I am abusing the syntax a little bit), so you have $G(k,iv)$ which produces a different and independent key stream per iv.


Is $G$ a secure PRG? Is the following function a secure PRG?

  Given $F$ is a secure PRG and $k$ is choosen random from key space $K$.

  $$G(x) = F(k,x) \oplus F(k,x \oplus 1^s)$$

My solution is $x \oplus 1^s = x'$ so $G(x)$ becomes $f \oplus f'$ with $f = F(k,x)$ and $f' = F(k,x')$. Clearly $f$ and $f'$ are PRG, i.e. generate random strings; and $\oplus$ of these will be random.

Correct me if I am wrong.

To give this question its deserved answer, I’ll repeat what Ricky Demer noted in his comment:

$$G(x \oplus 1^s) = F(k,x \oplus 1^s) \oplus F(k,x \oplus 1^s \oplus 1^s)  \\
\downarrow  \\
F(k,x \oplus 1^s) \oplus F(k,x \oplus 1^s \oplus 1^s) = F(k,x \oplus 1^s) \oplus F(k,x \oplus 0^s)  \\
\downarrow  \\
F(k,x \oplus 1^s) \oplus F(k,x \oplus 0^s) = F(k,x \oplus 1^s) \oplus F(k,x)  \\
\downarrow  \\
F(k,x \oplus 1^s) \oplus F(k,x) = F(k,x) \oplus F(k,x \oplus 1^s)  \\
\downarrow  \\
F(k,x) \oplus F(k,x \oplus 1^s) = G(x)$$

As tylo commented: This shows G is not a secure PRG.


EAX cipher mode with nonce equal header I am using EAX AEAD with an 8-byte message header which carries a 32-bit sequence number, a message length, and some other bits that I don't mind exposing.  Assuming the sequence number never repeats for the same key, is there any security difference between treating that as a 4-byte nonce with 4 bytes of "associated data" or just calling it an 8-byte nonce and skipping any MAC calculations on the header?

The following picture shows EAX:

As you can see there is a OMAC calculation (or CMAC as it is usually called) over both $N$ (the nonce) and $H$ (the header / associated data). With regards to security it doesn't matter where you place the nonce and the other data in the header.

I'll not go into the security of XOR'ing the calculated OMAC values for nonce, header and ciphertext. EAX has a security proof, as long as that holds the cipher should be secure.

It would be best to treat the nonce and the rest of the header separately, as that would be the expected way of treating the input data. It also allows you to pre-calculate the header's OMAC value if it remains static. Note that you could remove the size of the plaintext from the OMAC calculation. You could calculate size of ciphertext + tag, and verify that.


How to stop an attacker from repeating the same ciphertext? I have this situation where a PC is connected, via RS-232, to a certain hardware module that controls industial machinery.

The hardware is supposed to receive commands to turn on or off these machines, and the same command may need to be sent multiple times in a span of a single minute. Now, I am very new to cryptography, so I will be programming this hardware with an already pre-existing library that supports AES-128, AES-192 and AES-256 in ECB and CBC modes.

The problem I'm facing is that a potential attacker can very easily gain access to the transmission line and just probe it for the message being sent, and then use this information to send commands that can compromise the industrial machinery.

Let's say that the PC encripts a message like "MACHINE1 ON" using AES-256 with a secret key that the hardware module knows. Since the command is always the same, using AES in ECB mode will result in the same ciphertext, meaning that the attacker can just repeat the same ciphertext in order to turn the machine on.

Now, CBC encryption makes use of an IV to randomize the ciphertext, but the problem is, how will both the PC and hardware module know the IV? If the PC generates a truly random IV and encrypts the command with it, there's no way the hardware module will be able to decrypt the message without it.

So it thought that maybe the PC should transmit the IV to the hardware, using ECB mode, and then transmit the command encrypted with that IV, but we're back to square one, because an attacker can just repeat both ciphertexts and the hardware will just accept it (is this considered a replay attack?).

I've read a little about MAC and how it allows to verify if the sender has not changed, but how does it apply to this scenario? Would it even help? If not, what techniques could one use in a situation such as this?

Keep in mind that there is very little variety in the messages that will be send to the hardware module. The hardware module is also capable of generating truly random numbers, and it replies to the commands with a simple "OK" or "Invalid command" messages. These should also be encrypted to ensure an attacker gets as little information as possible.

EDIT:

I also read that sometimes, the IV is sent at the beggining of the encrypted text, so that the receiving end knows that the first N bytes correspond to the IV and can decrypt the message. Isn't this also vulnerable to the same replay attack?

Wouldn't it be better to implement some kind of "handshaking", where the hardware is the one to generate the IV and send it to the PC, the PC modifies the IV in a deterministic way, and then sends the messages using that modified IV? The process would then repeat each time the PC needs to send a command, and as long as the hardware doesn't generate the same IV twice, everything would be safe, right?

I'm sorry if this question is all over the place, I'm very confused about criptography and I'm being asked to implement something that I have almost no clue as to how it works. Any help would be much appreciated.

Your question appears to be conflating the ideas of IV and antireplay protection; actually, they don't have anything to do with each other.

The IV (in CBC mode) is a randomly selected value chosen by the encryptor; it can be sent along with the ciphertext (as we don't care if the attacker knows it).  It's there so that if we decide to send the same message twice (or send two similar messages), the ciphertexts look completely unrelated (and hence the attacker doesn't gain any information).  It doesn't help with antireplay; however, it was never designed to.

As for antireplay (rejecting identical messages), well, there are two standard ways for addressing it.

The first way is to have the receiver remember which messages it has already received.  That can be easier than you might think; if the sender includes a sequence number (which it increments each time it sends a message), the receiver can just check that with the last sequence number is saw; if it hasn't increased, it can reject the message.  Now, this might have an issue that, for you, doesn't make it work; when either system restarts, how do both sides know which sequence number to use?  When we use this strategy, we reset the sequence numbers to known values when we initially negotiate keys; it sounds like you're using configured keys, and so that doesn't work.
The other strategy would be a challenge/response protocol; we have the receiver send a value (which can be random); and then the sender includes that value in the encrypted message, and then the receiver checks to see if the value in the message matches the value it sent out.  In your case, it might look like this:

  PC: "I want to send you a command"

  Device: "OK, use the value 0x314159"

  PC: "Turn MACHINE1 on; value 0x314159; reply with value 0x271828"

  Device: "OK, command accepted; value 0x271828"

Note that the first two messages don't really need to be encrypted; there's nothing useful that the attacker can learn from them.

I included the reply value (chosen by the PC) so that the attacker can't simulate the device accepting the command when it really hasn't.

The third issue is "how do you make sure that the attacker can't gain anything from modifying the messages".  Obviously, an attacker that can change arbitrary messages can forbid any communication (by simply jamming the RS-232 signal); cryptography can't solve that problem; the best it can do is to make sure that's all the attacker can accomplish.

You mention a MAC (Message Authentication Code); that's the correct solution for this problem.  For each encrypted message, you would compute the MAC (which is the function of the message and a secret key); you send this value along with the encrypted message and the IV.  When the device receives it, it also computes the MAC, and compares the value it computes with the value in the encrypted message.  If the two values are the same, it knows that the message was not modified.

Without this, it's possible that an attacker might be able to modify encrypted messages; for example, he might be able to modify an encrypted "Turn Machine 1 on" message into an encrypted "Turn Machine 2 on" message.  It strikes me that avoiding such a possibility is worth doing.

With the resources you have, the easiest MAC would be a CBC-MAC.  To implement this, you would take your message (including the IV), prepend the message length if you support variable length messages, and then ask your CBC hardware to encrypt it, using a fixed IV (all 0's work), and a different AES key than you use to perform the actual message encryption.  Then, you take the ciphertext, and discard everything except the last 16 bytes; that's your MAC.

The receive side would do the exact same thing; they'd take the received message (not including the MAC), possibly prepend the length, and ask their hardware to encrypt it (yes, encrypt, not decrypt) with the same fixed IV, and look at only the last 16 bytes of the resulting ciphertext, and compare that with the MAC included in the received message.


AES-GCM: Verification before Decryption I am looking at ChaCha20Poly1305 WolfSSL. It is noted that the ChaCha20Poly1305 AEAD construction has the property, that it only outputs the plaintext, if the verification of the MAC (Authentication Tag) was successful.
I am asking myself whether AES-GCM also can provide this (from a security perspective quite important) property. However, when looking at the mode diagram of GCM, it seems like the Authentication Tag is calculated successively using information from each ciphertext block. Therefore, the cipher must be decrypted in order to verify its integrity?

Therefore, the cipher must be decrypted in order to verify its integrity?

No, there is no such requirement.  As you state, the authentication tag is calculated from the ciphertext blocks, however, the receiver does not have to decrypt anything to get the value of the ciphertext blocks - he gets those directly.
One of the things that appear to be confusing you is that the diagram is the processing that occurs during encryption, not decryption.
For GCM decryption, the authentication block is validated this way: he takes the ciphertext (and the AAD), and repeatedly does MULTH and ADD [1] operations, then he MULTH and ADDs the AAD/ciphertext len, and then a MULTH and ADD of the processed nonce.  No decryption of ciphertext need to be done.
[1]: I say "ADD" even though it is really XOR; we're working in $GF(2^{128})$, and so field addition is xor.


What characteristics define a function to be a block cipher I'm trying to understand what characteristics or properties make the result of a function a block cipher. I understand that for a function to be a block cipher it has to be invertible and can't be a one-way function.

What I don't get is how to compute a cipher. So for example, I have the following cipher: $F_k^r(m) := r(k,m)$. Now $r$ is defined as a random compression function such that $r: \{0,1\}^{3n} \rightarrow \{0,1\}^n$. The length of $k$ and the number of bits for the message $m$ are both $n$, i.e. arbitrary.

What I don't know is how to compute the cipher and why it may potentially not be a block cipher? I think it isn't a block cipher because you are starting with $3n$ and then getting an output $n$ in the random compression function. But I think I am going wrong something.

I know I am getting close in better understanding it, I just kindly need someone to clarify the cipher and why it may not be a block cipher

The Wikipedia definition states;

  In cryptography, a block cipher is a deterministic algorithm operating on fixed-length groups of bits, called a block, with an unvarying transformation that is specified by a symmetric key

  A block cipher consists of two paired algorithms, one for encryption, E, and the other for decryption, D. Both algorithms accept two inputs: an input block of size n bits and a key of size k bits; and both yield an n-bit output block. The decryption algorithm D is defined to be the inverse function of encryption.

Your $F_k^r(m) := r(k,m)$ with $r: \{0,1\}^{3n} \rightarrow \{0,1\}^n$ is not a block cipher since:

The input block size and the output block size are not same as in the Wikipedia definition. Therefore you cannot define the inverse (decryption). With the key concerned, the input space must be $2^{2n}$, not $2^{3n}$ and output space must be $2^{n}$.