A multi-target attack on 128-bit ECDSA private keys I'm thinking about doing this as a project, but I'm not sure how I'm supposed to proceed.

So I have an 128-bit ECDSA, which would provide about 128 bits of security (if we do not use special methods like the baby-step giant-step algorithm or Pollard Rho's algorithm). I generate a list of 2^64 public keys, and I want to find the private keys to any one of them.

So essentially this is a multi-target attack on ECDSA private keys. With 2^64 targets (public keys), I would require 2^128/2^64=2^64 attempts on average to find a private key to any one of these targets.

I have a few questions:

(1) How long would it take for a computer to perform 2^64 ECDSA operations? Is 2^64 within the realm of possibility using commonly-available GPUs?

(2) I need to generate a list of 2^64 public keys (targets). Then I need to create a database for these keys, and index them (based on their x coordinate number size, in order to perform a structured search/lookup). Therefore, the size of this database would be bordering on several exabytes, which is completely infeasible using commonly-available resources. Is there any way to reduce the size of this database?

One $n$-bit ECDSA private key can be found from the public key with about $2^{n/2+1}$ group operations, by Pollard's rho, which is relatively easily distributed. Nothing more costly is worth consideration. For $n=128$, this is $2^{65}$ field operations and would be feasible with a large effort. This is why people use at least $\approx160$-bit ECDSA, and more like $256$-bit ECDSA or more nowadays.
It's a more interesting problem to determine if a multi-target attack can take sizably less time. I do not immediately see that it does.

How long would it take for a computer to perform $2^{64}$ ECDSA operations?

That depends a lot on:

The computer. This one is millions times faster than most others.
What's an operation. A full ECDSA signature at $n$-bit costs in the order of $n$ times more than a group operation, wich costs several field operations.
The $n$ parameter. For medium values, doubling it multiplies the cost of a field operation by like 3, of a full ECDSA signature by like 6.
The curve used. Binary curves allow faster implementation and attacks.
Competence of the attacker, which matters immensely.

Ultra rough estimate with my PC for $2^{65}$ group operations: $2^{31}\,\text{Hz}$, $2^3\,$cores, $2^7\,$cycles per field operation, we are talking $2^{65-31-3+7}=2^{38}\,s$, that's many centuries. We need too many PCs and too much energy.
Therefore the attack for $n=128$ has no practical interest, is feasible only at sizable cost, and it's better to run it as a mind or small-scale experiment.


What is a q-type assumption? I've seen the term "$q$-type assumption" used in a few papers without a definition. A Google search doesn't seem to come up with anything useful either (except the same papers without a definition). Could someone elaborate on what they are and how they compare to static assumptions?

Are there some other typical "types" or classifications of assumptions that one should know of?

PS: There doesn't seem to be a tag named "assumptions." Something like that should exist, but I don't have enough points to add it.

The classic standard assumptions (such as DDH, CDH) are not parametrized and always have constant size (are static). Consequently, the assumption when used in a reductionist proof is independent of any system parameters or oracle queries and only related to the security parameter.

In contrast, non-static ($q$-type) assumptions as already mentioned by Travis are parametrized (and actually a family of assumptions). They may be used in a static way (e.g., as 2-DBDHI), but if a reductionists proof relies on the non-static version, e.g., $q$-DBDHI, then $q$ is usually related to the number of oracle queries an adversary makes. For instance, if you have a signature scheme where a $q$-type assumption is used, then $q$ usually corresponds to the number of signing oracle queries an adversary makes and then the reduction works (you may for instance look at "Short Signatures Without Random Oracles" from Dan Boneh and Xavier Boyen, who reduce the security of their scheme to the $q$-SDH assumption). Consequently, the more signing queries an adversary is allowed to do, the larger the problem instance and usually the stronger the required assumption gets (observe that for static assumptions this does not influence the assumption itself). As Travis has mentioned some $q$-type assumptions can be converted to static assumptions such as subgroup hiding (typically in composite order bilinear groups).

Another class of assumptions which are typically seen to be stronger than $q$-type assumptions are interactive assumptions. Here, the assumption itself involves some oracle. A classic example are one-more assumptions (one-more RSA inversion, one-more CDH, LRSW assumption), where having $n$ times access to a "helper" oracle that solves some hard tasks on one of the $n$ inputs each, the assumption states that it does not help to solve the task on $m>n$ inputs. Another classic example for this type of assumption are knowledge of exponent assumptions, where solving some hard tasks implies some oracle (extractor) that extracts some value that the solver is implicitly assumed to know in order to solve the hard task. Interactive assumptions are non-falsifiable (you may read this paper) and thus people usually try to avoid them.


Get AES key from client request I get a request from a client who encrypts the message with the wrong AES key. Is there a way for me to know what AES key the client actually used? I understand I may get the decrypted msg which is likely to be wrong, but from what I understand, the key itself cannot be retrieved from the request sent by the client.

In other words, is there a way for me to do something like this -

if (client.aeskey != server.aeskey), print Error.

Please confirm if my understanding is correct.

To expand on what kasperd says in a comment. This sort of thing should be handled in the protocol. This would typically be done by adding message authentication code (MAC) in the traditional encrypt-then-mac paradigm or using authenticated encryption.

So then instead of doing if (client.aeskey != server.aeskey), print Error, you would be doing if (MAC(received_ciphertext, correct_key) != received_mac), print Error (in practice your crypto library that has built in authentication checks would do this for you and return an error).

As far as

  a way for me to know what AES key the client actually used

goes. There isn't a reliable way without additional assumptions (e.g., we assume that at most 2 bits were flipped).

We traditionally think of these designs as checking for modifications of the ciphertext, but if the incorrect key is used (say due to errors in the storage mechanism or whatever), it would also detect that. The benefit of doing this is you don't have to decrypt before realizing that something is wrong. Instead, you check the MAC and if that fails, you don't decrypt at all.

There are some practical things you should take into consideration. Your best bet would be to use a commercial library. The right one will depend on your setup and needs.

Warning, the absolute wrong way to do this would be to check the padding at the end of the plaintext (assuming you are using mode like CBC that requires padding), and then return an error if the padding is incorrect. This leads to a devastating attack known as a padding oracle attack.


What is the difference between order of base point and curve order in EC? When I was read about the elliptic curve cryptography I found some definition about domain parameter of  elliptic curve like the follow. But I did not understand something
$p$: prime number.
$a, b$: field elements, they specify the equation of the elliptic curve $ E$ over $F_P$,
$y^2  ≡ x^3+a • x+b  $
$G$: A base point represented by $G= (xg, yg)$ on $E (F_P)$
$n$: Order of point $G$ , that is $n$ is the smallest positive integer such that $nG = O$.
$h$: cofactor, and is equal to the ratio #E($F_P$)/$n$, where #E($F_P$) is the curve order.
My question
What's diffrence between  $n$ & #E($F_P$)? also
I think two are same value.
because #E($F_P$) is Curve Order where The number of points on the elliptic curve is called its curve order. and when we do #E * $G$ = $O$.
Is this right or not right?

What's difference between n & #E(FP)?

The difference is that $n$ is the smallest positive integer where $nG = O$; while you correctly state that $\#E \cdot G = O$, that doesn't mean that $\#E$ is the smallest integer that makes this happen.  There may be a smaller integer $n$; $n$ will always be a factor of $\#E$, however it can be smaller.

As for why we would want to make it smaller, that is, why would we want to have an $h = \#E/n > 1$, well, that's exactly what this question addresses.


Is CPU timing jitter a usable entropy source? In some virtualized environments, the only source of entropy available is CPU timing jitter.  Can one get enough entropy from this source for practical uses?  Also, is this secure against local side-channel attacks against unprivileged local attackers?

"enough" in this context means "enough to seed a CSPRNG" (256 bits?).
"unprivileged" means that the attacker cannot simply read the RNG state directly because of process or VM isolation.

The problem with CPU jitter is that it is difficult to pin down an accurate physical model of it that would allow you to calculate the entropy involved. Therefore entropy estimates have to largely be grounded on statistical testing, as in the document I linked in the comments.

As you may know, statistical testing alone can only ever give you an upper bound for entropy. What you need for secure random number generation is a lower bound, and that requires making more assumptions.

However, since you only need enough entropy to seed a PRNG, the answer to your question is almost certainly that it does have enough entropy. You can always collect timings for a very long time and feed it all as seed material to the RNG, and unless the jitter contains no entropy at all you will eventually have 256 bits' worth. How long is the question, with no single answer.

If you use a recent Linux kernel, you should be able to get entropy with all that figured out (or guessed...) for you, just by accessing /dev/random or /dev/urandom. In practice it is also often possible to get a small seed into the VM from outside, so you do not necessarily have to rely on the VM being able to generate entropy.


What is the difference between a cryptographic primitive and a functionality? In the context of papers using the UC framework, I have seen the same cryptographic tools refereed as cryptographic primitives and functionalities. Are the two terms interchangeable?

An example is here:

  Bulletin Boards and Smart Contracts are primitives which form the backbone of our result.

and

  We also assume that there exists a Smart Contract functionality that incorporates this ideal Bulletin Board.

It is difficult to answer this question without looking at the same papers you are looking at. Still, I interpret these concepts as fairly different, for reasons I will sketch below.

A function is common in mathematics, and can be written as some mapping $f : X\to Y$ of inputs to outputs. Many algorithms implement the behavior of functions --- they take some batch of inputs, and return outputs. Consider prototypical examples as being "sorting algorithms" or "graph algorithms" or "essentially any algorithm you learn about in an algorithms course".

Functionalities do not necessarily collect all of their inputs before starting processing them. Later inputs can depend on prior inputs, potentially in non-trivial ways. This is in particular important for interactive protocols, where for a two-person protocol with participants $P_1$ and $P_2$, $P_2$'s later inputs can depend on $P_1$'s prior inputs (potentially in an adversarial way). This is somehow the "core" of the idea, where other similar concepts (say streaming algorithms) often are not called functionalities because of the lack of multiple participants.
So functionalities can be seen as the mathematical abstraction which captures the notion of interactive algorithms.

A cryptographic primitive is some tuple of algorithms $(\mathcal{A}_1,\dots,\mathcal{A}_k)$ (which might each individually be a function or a functionality), along with certain conditions they must satisfy.
There are many conditions you can impose, but common ones are things like:

Correctness
Soundness
Indistinguishability of various quantities ("privacy" or "secrecy" conditions)

For example, symmetric-key encryption is often described as a triple of algorithms $(\mathsf{KeyGen}, \mathsf{Enc}, \mathsf{Dec})$ such that:

There is a correctness condition:

$$\forall k\leftarrow\mathsf{KeyGen}(1^\lambda), \forall m\in\mathcal{M}
 : (\mathsf{Dec}_k\circ\mathsf{Enc}_k)(m) = m$$
Where $\mathcal{M}$ is the message space of the algorithm.
There is a secrecy condition, namely that for $k\leftarrow\mathsf{KeyGen}(1^\lambda)$, and $m_0\neq m_1$, $\{\mathsf{Enc}_k(m_0)\}$ is (some form of) indistinguishable from $\{\mathsf{Enc}_k(m_1)\}$, where these quantities are distributions over the choice of random coins of encryption.

So we can view each of the individual algorithms as being functionalities, but them combined together with conditions they must fulfil as being a cryptographic primitive that we call "symmetric key encryption".

Note that one could technically view something like a sorting algorithm as a "cryptographic primitive with solely a correctness condition", but this is rather non-standard. We generally assume all algorithms must be correct, so only start describing things as cryptographic primitives when the condition is something like "correct in an adversarial context", or conditions such as "secret" (or other "more than just correct" conditions).

While I believe this viewpoint is fairly common, I don't know if it is universally agreed upon by all authors at all times, so particular questions you have about particular papers would still be easier to answer with a pointer to those papers.


DGK Cryptosystem Encryption Speedup Following @poncho's nice clarification of the RSA speedup here, let's see if I'm able to do the same in the case of the DGK cryptosystem:

We have pk = (n, g, h, u), sk = (p, q, $v_p$, $v_q$) which are generated as following:

we have 3 numbers, $k > t > l$
we pick u as the next prime greater than $2^{l+2}$ (having more than $l + 2$ bits)
we pick 2 random t bit primes, $v_p$, $v_q$
we generate p and q primes of length $k/2$ bits such that u and $v_p$ divide $p-1$ and u and $v_q$ divide $q-1$
we generate h of order $v_p*v_q$ modulo p and q
we generate g of order $u*v_p*v_q$ modulo p and q

Encryption: $E(m,r) = g^mh^r\pmod n$
Decryption: $E(m,r)^{v_p} = (g^{v_p})^m\pmod p$, which determines m uniquely, so we precompute all possible values of the right side (since the message space, u, is really small) and during decryption we just search for $c^{v_p}$ among the precomputed values. Later edit: The correction to the original paper states that $c^{v_p}$ uniquely determines m, so it's not necessary to use $c^{v_pv_q}$. I am not able to figure out how they came to this conclusion, but it does seem to work.

I know that there are a lot of details missing, but for those that are curious, I suggest reading the entire paper and the subsequent security correction (which replaces v with $v_p$ and $v_q$).

Now, we want to speed up the encryption process, since those exponentiations modulo n are rather slow, so we express $E(m,r)$ in $\mathbb{Z}_n^*$ as $E_p(m,r)$ and $E_q(m,r)$ in $\mathbb{Z}_p^* \times \mathbb{Z}_q^*$:

$E_p(m,r) = g^mh^r \pmod p$
$E_q(m,r) = g^mh^r \pmod q$

Now we apply the Chinese Remainder Theorem in order to obtain $E(m,r) \pmod n$. The formula used to achieve this is: $$\sum_{i} a_i \frac{N}{n_i} \left[\left(\frac{N}{n_i}\right)^{-1}\right]_{n_i}$$

So we have: $$E(m,r) = E_p(m,r)*q*(q^{-1}\bmod p) + E_q(m,r)*p*(p^{-1}\bmod q) \pmod n \Rightarrow$$

$$E(m,r) = (g^mh^r \bmod p)*q*(q^{-1}\bmod p) + (g^mh^r \bmod q)*p*(p^{-1}\bmod q) \pmod n$$

The above formula seems to make sense, right? Right?

Because further optimization is required, I need to somehow compute the above formula in two steps. More precisely, the random numbers can sometimes be generated in a different process, so I need the ability to split $E(m,r) = g^mh^r\pmod n$ in half:

first compute $E_{nonrand}(m,r) = g^m \pmod n$
then randomize: $E(m,r) = E_{nonrand}(m,r) * h^r\pmod n$

My intuition tells me that in this case I can still perform the encryption speedup and the formula should look something like this:

$$E_{nonrand}(m,r) = (g^m \bmod p)*q*(q^{-1}\bmod p) + (g^m \bmod q)*p*(p^{-1}\bmod q) \pmod n$$

$$E(m,r) = E_{nonrand}(m,r) * [(h^r \bmod p)*q*(q^{-1}\bmod p) + (h^r \bmod q)*p*(p^{-1}\bmod q)] \pmod n$$

I tested this formula and it seems to work, but I am unsure that I'm doing it right... Also, is it OK to skip the $\pmod n$ operation when computing $E_{nonrand}(m,r)$? It seems to me that it is redundant.

As it turns out, this is just a beginner question and I think I managed to figure it out. Since $E(m,r) = g^mh^r \pmod n$, I can just split it in two: $E(m,r) = (g^m \pmod n) (h^r\pmod n)$ and then apply the CRT trick on both sides, after which I can multiply the results together to get back the original:

$E_{nonrand}(m,r) = (g^m \bmod p)*q*(q^{-1}\bmod p) + (g^m \bmod q)*p*(p^{-1}\bmod q) \pmod n$

$R_{h}(r) = (h^r \bmod p)*q*(q^{-1}\bmod p) + (h^r \bmod q)*p*(p^{-1}\bmod q) \pmod n$

$E(m,r) = E_{nonrand}(m,r)R_{h}(r) \pmod n$

Can anyone think of any reasons why I should not skip the (mod n) reductions for $E_{nonrand}(m,r)$ and $R_{h}(r)$? It looks to me like they are redundant...


If you know the messages, and the results of HMAC(key, message) can you find the key? If the attacker has 1 billion 4KB (random-noise) messages and sha256-HMACs for those messages (all using the same key), can they calculate the key that was used, before the universe dies?

Not, that should be not possible, at least if you have a good key.

All this is only valid as long as SHA-256 is still a secure hash algorithm and not broken. To be precise, as long as HMAC-SHA-256 is not broken.

Does the attacker have any informations about the messages (other than the length and that they are "random-noise")? If he/she doesn't: No, there's no way an attacker could get the key in real life conditions. They would have to brute force HMAC-SHA-256, and that's not possible if you use normal computers with non-ignorable probability. Every message has far higher entropy than anything possible to brute force.

If the enemy knows all messages: Well, it's all about your key. In the past, there was a need to have a key for hashes, but the common structures of hashes were not suitable to just put the key before the message. HMAC was invented to solve this problem. It has some nice security proofs which basically say "It should not be possible to get the key as long as the hash function is still secure and the key good enough." - the RFC 2104 has more explanations and some links for further informations.

Well, is your key good enough? If your key is anything under 64 bit long and at least one message known by the attacker, than you have lost. Brute forcing 64 bit is not easy, but doable. If your key is longer than 64 bit (something like 80 bit or better 128 bit or higher) then you have to think about entropy. If your key is fully random and an attacker doesn't know any pattern about it, than is the entropy as high as the length in bit, but if your password is something like "password1234", than it's pretty easy to brute force, despite having 96 bit (for 8 bit per character). Good passwords are alone a pretty complex topic, so I won't include them in this answer. If you need to know more about secure passwords, use the search engine you like the most for something like "good password" or "choosing secure password".


understanding the block bits for DES I'm trying to understand cryptographic protocols, and I've started with the DES algorithm.

DES specs: it uses 64 bits for the plaintext, 56 bits for the key, with a result of the same 64 bits of ciphertext.

But encrypting on online websites I see a totally different thing.
Encrypting the string "hello" with the key "key" will get me the cipher text "ar635N/LqmY=".
Now, I used https://ethproductions.github.io/bytes/ to count the number of bits in a string, and seems like:

"hello" has 5 chars, totaling 10 UTF-16 bytes, which is 80 bits
"key" has 3 chars, totaling 6 UTF-16 bytes, which is 48 bits
"ar635N/LqmY=" has 12 chars, totaling 24 UTF-16 bytes, which is 192 bits

So, as you can see, we have here an input of 80 bits with a key of 48 bits and an output of 192 bits.

First of all, if you want to seriously learn cryptography, then do not use any online encryption sites. It seems most if not all are created by enthusiasts that just learned crypto and then wanted to do something interesting with it. Unfortunately that simply means that they are just propagating their very limited and often incorrect understanding of (block) ciphers and cryptography in general. Even if one of the sites was created by a good cryptographer, you would not be able to distinguish it from the rest.

One of the first things to learn before starting to learn cryptography is how - and when - to perform encoding / decoding. Basically there are two forms of encoding that convert byte- and character strings:

character encoding where a character is encoded to binary. Examples are ASCII, UTF-8 and UTF-16(BE/LE).
(binary) encoding where a octet string / byte array is encoded to a string consisting of characters. Examples are hexadecimals, base64, base64url.

For instance, ar635N/LqmY= is a base 64 string which encodes 8 bytes or 64 bits. Those bytes may not themselves represent a string, and assuming that they consist of 8 UTF-16 characters is obviously incorrect, if just because 8 UTF-16 characters take 8 * 16 = 128 bits at a minimum, not 64 bits.

The site you pointed to doesn't decode the base64, it just tries to character-encode the string to binary. For base 64 you could use e.g. this site (random one without ads). Note that humans are bad at reading bytes if they do not represent text, and ciphertext consists of pseudo-random bytes. So the site will return another encoding as well: hexadecimals. From hexadecimals it is easierto see any structure in the returned bytes.

To be able to take a "encryption" site seriously, the site should:

explicitly define which cipher is used (for DES, does it accept 3DES as well?)
show the key sizes that you can use
allow the key to be entered as hexadecimals
if it allows a password (a password is not a key), specify which Password Based Key Derivation Function is used (examples: bcrypt, scrypt, PBKDF2, Argon2)
allow you to input a given IV (and possibly create and display a random IV as an option)
specify the mode of operation that is used for the block cipher
specify the padding mode that is used for the mode of operation (if any)
indicate which configuration options are used (such as the hash of the digital signature, or the length of an authentication tag) instead of relying on unspecified defaults
specify the character encoding of the plaintext message (assuming the message is text instead of hex or base64)
specify the encoding of the ciphertext (directly displaying the random bytes doesn't make sense, some bytes do not translate directly into printable characters)

If any of these are not given it will leave you guessing on what is happening.

Furthermore, the site should:

indicate that the site is for testing only, actual plaintext or keys should not be entered
not make any simple crypto errors such as failing to distinguish between AES and Rijndael or reuse the key to generate an IV (the list is endless)
hopefully indicate that encryption using e.g. CBC is not secure for transport protocols
and finally, return correct results

These two lists will unfortunately rule out 99% if not all of the sites.

You're better off picking up the best crypto API for your favorite language / runtime and use that to explore.

As for your specific key issue: the site will probably add 00 valued bytes up to the key size. Or it could use spaces. Or it could use a cryptographic hash (and take the wrong, rightmost bytes if you're unlucky). All of which are insecure and show exactly how you should not use a block cipher.


why do we asume that in the registration process communication is over the secure channel? I was reading some research papers and saw that in Registration phase/process it is always assumed that communication is over the secure/private channel, whereas, all of the phases communication is happening over the public/open channel. What is the reason for this? on the basis of which parameter! we assume that the channel is secure/private insecure/public?
Thanks in advance.

Registration phase/process it is always assumed that communication is
  over the secure/private channel, whereas, all of the phases
  communication is happening over the public/open channel. What is the
  reason for this?

Well, the point of the registration phase is to register the client to the server, so that they can reach mutual authentication afterwards using the exchanged information and with minimal / no assumptions on the underlying channel.

If you assume the channel to be insecure for this process, what an attacker can do, is wait for you to enter the registration phase with the legitimate server, intercept the request, act like they are the legitimate server and at the same time register themselves to the real server.

Now if you connect after the registration stage, the attacker can perfectly fine be authenticated as "the real server" and intercept your entire traffic (and potentially forward it to the real server).


Collisions in the cyclotomic knapsack function I've been working my way through the paper “Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices” by Peikert and Rosen, and I've come across something that doesn't seem to make sense to me.  (Apologies if the level of detail in the following is inconsistent, I'm somewhat less than familiar with the context.)

Here's my problem.

What I'm understanding is a simple linear algebra thing: Take a subspace of $\mathbb R^n$, then reduce a vector in that subspace modulo a lattice, but there's not enough of restriction on the structure of the subspace and lattice that that should stay in the subspace.

In particular

$\mathbb Z[\alpha]/(\alpha^n-1)$ is identified with $\mathbb Z^n$ by considering the representative with degree less than $n$, and taking $b_0+b_1\alpha+\cdots+b_{n-1}\alpha^{n-1}\mapsto(b_0,b_1,\cdots,b_{n-1})$.

We are looking at a restricted collection of lattices $\mathcal{L}(B)\cap H_\Phi$ where $\mathcal L(B)$ is a cyclic lattice (that is, one that is an ideal in $Z[\alpha]/(\alpha^n-1)$, or equivalently that is closed under ${\rm rot}:(c_1,c_2,\cdots,c_n)\mapsto(c_n,c_1,\cdots,c_{n-1})$), and we define the subspace $H_\Phi$ of $\mathbb{R}^n$ to be $\mathbb{R}[\alpha]\Phi(\alpha)/(\alpha^n-1)$ the multiples of some $\Phi(\alpha)=(\alpha^n-1)/(\Phi_k(\alpha))$ where $\Phi_k(\alpha)$ is a cyclotomic polynomial.

Then, we take $y\in\mathcal L(B)\cap H$, and let $y'=y \mod B$, the vector in $B[0,1)^n$ with $y-y'\in\mathcal L(B)$, and it is claimed that $y'\in H_\Phi$.  As I understand things, however, this isn't true; take, for example, the following (general) counterexample:

Let $k=n$ for prime $n$.  Then we have $\Phi(\alpha)=\alpha-1$, and
\begin{align*}
  H_\Phi
    &=\left\{(b_0+\cdots+b_{n-1}\alpha^{n-1})(\alpha-1)\right\}\\
    &=\left\{(b_{n-1}-b_0)+(b_0-b_1)\alpha+\cdots+(b_{n-1}-b_n)\alpha^{n-1}\right\}\\
    &=\left\{(c_0,\cdots,c_{n-2},-(c_0+\cdots+c_{n-2}))\right\}.
\end{align*}
Then let $B$ be the standard basis for $\mathbb Z^n$, and take $y=(1/(n-1),\cdots,1/(n-1),-1)$, so that $y'=(0,\cdots,0,-1)$.  But clearly $y$ is in $H_\Phi$, but $y'$ is not.

I'm not really sure what's going on here, because it is claimed that $y'\in H$ more or less by construction, making me think I'm confused somewhere along the way with the notation, but I can't seem to find it.

I'm fairly certain that what I have written above is correct, as well as that that it is claimed in the paper I linked above (in the proof of claim 5.3) that $y'\in H_\Phi$. Can someone point me to where I'm going wrong?

Thanks for the question!  You are correct that there is a bug here.  Indeed, the sentence "choose $\mathbf{b}_i$ s.t. $\ldots$" makes no sense: the LHS is in $H$, but the RHS may not be.  Fortunately, there is a simple fix which guarantees $\mathbf{y}'_i \in H$. (This must have been what we intended in the first place, based on how the rest of the proof goes; see below.)

The fix: the proof of Theorem 5.1, Item 1, second bullet, should read: Let $\mathbf{y}'_i = \mathbf{y}_i \bmod \mathbf{B}'$ (not $\mathbf{B}$), where $\mathbf{B}'$ denotes an arbitrary basis of $\mathcal{L}(\mathbf{B}) \cap H$.  (Such a basis is easy to compute by linear algebra.)  That is, we sample a Gaussian over $H$, and mod it by a lattice contained in $H$.  So, we clearly have $\mathbf{y}'_i \in H$.

Similarly, in the proof of Claim 5.2 ("Notice that $\mathbf{y}'_i \ldots$") we care about $D_{H,s} \bmod \mathcal{P}(\mathbf{B}')$, not $\mathbf{B}$.  (Indeed, it doesn't make sense as currently written: Lemma 2.7 requires modding by a lattice contained in $H$.)

It looks like the rest of the proof goes through as written.

Let me also mention that subsequent works manage to avoid all this cumbersome "bookkeeping" associated with subspaces etc., by working with rings defined by irreducible polynomials (or more generally, in number rings).  See, e.g., Lyubashevsky-Micciancio ICALP 2006, Peikert-Rosen STOC 2007, and Lyubashevsky-Peikert-Regev EUROCRYPT 2010/JACM 2013.


Is there any digital watermark technology for raw text? I have a demand to protect my data which can accessed by my client privately.
My data is not in any document but in plain text, e.g., a JSON string.
I want to protect my data against being modified, then redistributing without my permission.

I researched online for a while, and concluded that,

there are digital watermark methods for protecting images, audio, videos or documents (pdf, MS Word doc or other format),
but there is no such methods for raw text.

I want to know if there is any cryptographic way to achieve my goal?

I assume the request for clarification of "Plain-Text" has to do with content, not that it's an ASCII or UTF string.

There is not a "Hello World!" string that I could make that you couldn't then copy and call your own, where I could 100% prove that it was mine to begin with. For example anyone can just delete a PGP signature wrapper.

However, if the content of your string is structured in a way that was uniquely identifiably yours then I would call that a watermark, as any change to the content of string would change its context. For example using a private RSA key to encrypt your string then coding it back into ASCII with Ascii85, or if your string contains obfuscated JavaScript, or even simply something you've published under a copy right

That should afford about the same level of watermark you'd see in the other media, but the thing is any media which can be displayed with out the watermark is by the reflexive property media that can be stripped of its watermark and not still remain self judicating. ie copy right it, or have context that's destroyed when changed.


Encryption scheme like RSA where encryption is the inverse of decryption In RSA, it is basically equivalent to use the private key $d$ to encrypt as it is to use the public key $e$ to encrypt. They are exactly inverses: $e=d^{-1}$.

I need to know, are there other public key schemes like this? E.g., I do not think Diffie-Hellman is like this.

What you seem to be looking for is a scheme like the following: It consists of two algorithms, a key generation algorithm $K$ and a "key use" algorithm $U$.

The key generation algorithm outputs a pair of keys $(k_0, k_1)$. The "key use" algorithm takes as input a key and an element from some set $S$ (which may depend on $k_0$ and $k_1$), and outputs an element of a set $S$, and satisfies $$U(k_b, U(k_{1-b}, s)) = s$$ for all key pairs $(k_0,k_1)$ output by $K$, all $b \in \{0,1\}$ and all $s \in S$.

Security-wise, for $b = 0$ and $b=1$, given a random $s \in S$ and the key $k_b$, it should be hard to find $t$ such that $U(k_b, t) = s$.

You can trivially turn this into a public key encryption scheme by choosing one of the keys as the encryption key and the other as the decryption key. Ditto for signature scheme.

To get secure schemes, you need to include padding schemes, hash functions or any of the usual stuff.

I don't off-hand know of any examples of such schemes, except for RSA with random exponents or RSA look-alikes. (RSA with small $e$ is not secure.) Diffie-Hellman is certainly not like this.

I don't know if this is a useful concept. It is somewhat similar to trapdoor one-way permutation, which you don't hear so much about anymore.


Is there a administrator key that can decrypt all ciphertexts encrypted with different keys by different persons in a group? here is the scenario:

$A, B, C, \ldots, Z$ are in a group with a administrator $Admin$,
each of the users in the group has his own key $Key_A, Key_B$, and so on...
everyone encrypt his own information with his own key,

but would it be possible to have a key such as the Admin would have the possibility to decrypt all the ciphertexts of all the users?

  I had a simple idea:

  the Admin share a master key with all the members in the group,
  all users register his identity at the Admin,
  the Admin generate every user's secret key for every user,
  the Admin share keys with all the users.

  but in this way the Admin will know all the users' keys, this is insecure.

Another solution (cf to @Raoul722 comment) is the following:

It is easily feasible with a mix of symmetric and asymmetric encryption.

Assume each user $k$ have a key pair: $(K_{pub}^k,K_{priv}^k)$.
The admin also have his key pair: $(K_{pub}^{admin},K_{priv}^{admin})$ where $K_{pub}^{admin}$ is known by all.

Encryption scheme for a user $k$:

generate a random key $K_{sym}$.
Encrypt your file with a symmetric encryption device such as AES with $K_{sym}$.
Encrypt $K_{sym}$ with assymmetric encryption (RSA, ECC...) with the
$K_{pub}^k$, let's call it $K_k$.
Encrypt $K_{sym}$ with assymmetric encryption (RSA, ECC...) with the
$K_{pub}^{admin}$ let's call it $K_{admin}$.

Decryption scheme for a user $k$:

Decrypt $K_k$ with his private key ($K_{priv}^k$), he will get $K_{sym}$.
Decrypt the file with $K_{sym}$.

Decryption scheme for a user $admin$:

Decrypt $K_{admin}$ with his private key ($K_{priv}^{admin}$), he will get $K_{sym}$.
Decrypt the file with $K_{sym}$.

The sole problem is where do you store the encrypted keys: $K_{k}$ and $K_{admin}$ (maybe in the meta-data of the encrypted files? :) )

About the key privacy: In this scheme, having a asymmetric scheme prevent the admin to know each user private key.

Note: this kind of scheme is useful in company in the following scenario. Assume that everybody encrypt his files. One happens to have a lethal accident (R.I.P.), how do you retrieve his work ?
The problem that will arise is the safe storage of the master key (usually off-line and sealed to prevent malicious usages).


Get permutations from password Are there any "good" ways to get a permutation from a password/pass-phrase?

If one, for example, wanted to get a permutation of letters from a password, how might one do that in a smart way? I would be interested in a way that from one password word would generate a given number, for example 7, permutations for use in an Enigma machine.

I understand that if the password is password one could simply make the alphabet

paswordbcefghijklmnqtuvxyz
so that the permutation would send
a to p to w to o to etc.

But this doesn't seem like a very smart choice. It would obviously be nice if the permutation generated is very different for two very similar passwords.

What are better ways of doing this?

Edit: This does not need to be implementable mechanically.

If I understand correctly, you want a function that for each input string $p$ assigns a permutation over an alphabet $L$.

If the number of elements in $L$ is small enough, the permutation set $P(L)$ will be enumerable. More precisely, $|P(L)| = |L|!$. There exists a surjective function $f:\{0,1\}^k \to P(L)$ that for each bit string $s$ of length $k$ assigns a permutation over $L$, where $k \gt log_2(|L|!)$. For instance, $f(s) = g(BS2I(s) \bmod n!)$ and

function g
  Input: Large integer
  Output: array [L] of L
  x := Input;
  for i := 0 to (n-1) do
    z[i] := i;
  for i := n downto 1 do
  begin
    t := x mod i;
    x := x div i;
    y[n-i] := z[t];
    for j := t+1 to i-1 do
      z[j-1] := z[j];
  end;
  for a in L do
    Output[a] := I2E(y[E2I(a)]);

will work, provided that $2^k$ is sufficiently much larger than $n!$ to make the bias insignificant. Note: Surjectivity follows from the observation that each $x$ in the range $0..n-1$ will result in a unique sequence of $t$ values. At each step, a change in $t$ will result in a different value from the remaining $z$ values being picked. The algorithm closely follows the conventional proof that the number of permutations of $n$ elements equals $n!$.

However, as pointed out by fgrieu in a comment below, a more efficient algorithm is:

function g
  Input: Large integer
  Output: array [L] of L
  x := Input;
  for i := 1 to n do
  begin
    t := x mod i;
    x := x div i;
    y[i-1] := i-1;
    y[i-1] := y[t];
    y[t] := i-1;
  end;
  for a in L do
    Output[a] := I2E(y[E2I(a)]);

The second algorithm will also output unique permutations for $x \in \{0..n-1\}$. Informally, this is because each permutation of $n$ elements might be expressed as a sequence of at most $n$ pairwise substitutions. This algorithms happens to result in sequences of $n$ such pairwise substitutions that are guaranteed to result in unique permutations.

To ensure that two related input passwords will not map to two related permutations, you first pass the password through a PBKDF (as suggested by fgrieu in a comment) before applying $f$. If $|L| = 26$ then $k = 256$ will be sufficient (because $log_2(26!) \lt 89$ the bias of $f$ will be significantly less than $2^{-128}$).

Hence:

Pass the input password $p$ through a PBKDF to produce a bit string $s$ of bit length $256$.
Convert $s$ to a 256 bit integer $x$ using a standard $BS2I$ function.
Map $x$ to a permutation over the 26 element alphabet $L$ using function $g$


How many of primitive point on the elliptic curve? In elliptic curves for cryptography, I know  $nG=O$, where $G$ is a base point represented by $G=(x_g,y_g)\ on\ E(F_P)$, where $n$ is Order of point $G$.
For example, $P(0,6)$ is a primitive point on the elliptic curve $y^2\equiv x^3+2x+2 \pmod{17}$.

I ask about points on elliptic curve. How many numbers point that is generator or (primitive point).

Is any point on elliptic curve is generator or no.

also. How can I determine this points?

In a group of size $n$ (e.g. an elliptic curve), the order of a subgroup generated by a group element necessarily divides $n$. We usually choose curves so that their order $n$ is prime; in that case, the order of a point must be either $1$ (the point is the "point at infinity") or $n$ (all other points). Thus, if $n$ is prime, then every non-zero point is necessarily a generator for the whole curve.

In general, if $n$ is not prime but you know its factorization, then you can test whether a point $P$ generates the whole curve in the following way: for every prime $k$ that divides $n$, compute $(n/k)P$. If none of these points is zero, then $P$ generates the whole curve.

(All of this applies to every finite group, not just elliptic curves.)


RC6 Key Size Understanding I need help to understand how RC6 works. Many sites show that the maximum key size of RC6 is 2040 bits (255 Bytes). I can also have 0..255 rounds and 4 times 32bits words in the 128bit block variant or 4 times 64 bits Words in 256 bit variant. For this question assume 20 rounds

If expansion massive S[0,�,2r + 3]  => max = 2*20+3=43 * 4bytes = 172bytes. If it is really possible to have a key consist of up to 255 bytes then array S is too small. Where does my calculation go wrong?

Input: User-supplied b byte key preloaded into the c - word array L[0,�,c-1]

Number r of rounds

Output: w-bit round keys S[0,�,2r + 3]

Procedure:

S[0] = Pw
for i = 1 to 2r + 3 do
    S[i]=S[i-1]+Qw

A=B=i=j=0
v=3 ? max{c, 2r+4}

for s=1 to v do
{
    A=S[i]=(S[i]+A+B)<<ɛ
    B=L[j]=(L[j]+A+B)<<<(A+B)
    i=(i+1) mod (2r+4)
    j=(j+1) mod c
}

[Copy of my answer in another community:] In the RC6 specification (see de.wikipedia.org/wiki/RC6) S[*] designates an array of 2r+4 round keys, whose size in bits you can choose in the range [0,2000]. It is not an array of 2r+4 elements (each a word of 4 bytes).


Good practices for AES key derivation and management I'm developping a device based on STM32L4x6. It is connected through BLE to a smartphone and it exchanges encrypted data with it. Data consists of health data of patients.

Encryption is AES-GCM 256 bits and I'm using the reference implementation provided by STMicro.

I have implemented a classical shared secret exchange mechanism using Diffie-Helman protocol on Curve25519. Right now I am using this shared secret directly as the AES key.

I know that I need to derive a "cryptographycally good" AES key from this shared secret.

I was planning to use HKDF-SHA512 for that, because it seems to be a widely used algorithm and also because a reference implementation is also provided by STMicro. Is it a good choice ?

I'm confused about the size and the nature of the salt to derive the key. Do you have any advice for that ?

From what I understood one can use HKDF-SHA512 to generate a key of 256 bits, do you confirm ?

Also regarding the derivation frequency : at what frequency should I derive a new key ?

Thank you

I know that I need to derive a "cryptographycally good" AES key from this shared secret... I was planning to use HKDF-SHA512 for that, because it seems to be a widely used algorithm and also because a reference implementation is also provided by STMicro. Is it a good choice?

Yes, it is. HKDF is standardized and well regarded.

  I'm confused about the size and the nature of the salt to derive the key. Do you have any advice for that?

If a random is already provided within the protocol you may want to use that. A random of 64 to 128 bits should be plenty. Anything over 256 bits is madness. Note that the salt is complementary; a salt of any size is better than nothing.

The salt must of course be known at both sides, so it will complicate the protocol somewhat if it isn't available yet.

  From what I understood one can use HKDF-SHA512 to generate a key of 256 bits, do you confirm?

Sure thing, you can just take the leftmost 256 bits. You could use 96 bits of the remaining bits for the IV.

  Also regarding the derivation frequency : at what frequency should I derive a new key?

That depends on the use case. For smart cards you may just derive the key once at the start of the protocol and simply halt if too much data is being processed, as smart cards are not meant to be continuously available. But if your secure channel of your transport protocol is just established once then you may want to reestablish after a certain amount of messages.

Hints on how to make sure that the keys are fresh are in chapter 8 of the GCM specification by NIST, specifically chapter 8.3 which specifies how GCM is to be used.

Beware that there are many pitfalls in creating a transport protocol; you may want to have a look at TLS 1.3 or even implement it directly. TLS 1.3 also is able to use GCM as well as HKDF.


Argon2 or scrypt instead of PBKDF2 with AES Is using scrypt or argon2 a better key stretching technique with AES compared to PBKDF2 or bcrypt with regards to
a quantum computer brute force attack. The brute force attack I'm referring to is trying to generate keys from lets say a million
passwords and trying them on an encrypted text to get the password. In other words, can a quantum computer scale up a memory intensive
hash generation with scrypt or argon2 compared to PBKDF2 or bcrypt?

Such quantom attacks are entirely theoretical, we are nowhere near having quantom computers brute force passwords. It is thus difficult to compare.
Argon2 might be harder to implement on quantom computers but also the others are so far from being practical it seems pointless to try and compare how these would fair against a mythical adversary. In general quantom computers can break passwords in a square root of the effort and that is true for all the mentioned algorithms.

However there are far more practical attacks to consider, mainly using GPUs and dedicated hardware. That is where the advantages of argon2 over bcrypt or PBKDF2-SHA1 for instance come into play. Argon2 requires not only CPU but also RAM, while the others hardly use memory. This deminishes the attacker advantage of dedicated hardware or GPUs.

I stillb consider bcrypt a safe option, but assuming you have available RAM you will get a better slowdown factor against a sophisticated adversary by using argon2.


Homomorphic encryption and approximated GCD I am reading the paper Fully homomorphic encryption over the integers (PDF). The paper reduced the security to the approximated GCD problem. My first question is whether the scheme proposed by the paper is semantically secure?

In the paper, the plaintext set is {0,1} and the scheme is asymmetric. I am now thinking about a symmetric setting in which the plaintext set is integers. For an integer $m_i$, the encryption is $c_i=pq_i+m_i$ and the decryption is $m_i=c_i\mod p$, where $p$ is the key and $q_i$ is some randomly chosen integer. It seems that this scheme is fully homomorphic (if the key is large enough). My question is that whether this scheme is secure at all? If so, what kind of security level I can claim?

This cipher is broken against chosen plaintext attack. Submit encryptions of 0 to obtain a set where each element is composed of p times some random q. Then, compute the gcd of some of the pairs until you acquire p.

If p and q are not prime, you will require more then two pairs.

You may be interested in the DoubleMod construction.


Why does the authenticated cipher CCM encrypt the MAC too? Suppose I have Encryption in CTR-Mode and a CBC-MAC. Why should I also encrypt the MAC?

In the documentation of NIST stands: "By encrypting T we avoid CBC-MAC collision attacks".

But I can not imagine an attack based on an not-encrypted MAC.
Can anyone give me an example of such an attack?

Let $M_k$ be CBC-MAC under the key $k$: for blocks $b_1, b_2, \dots, b_\ell$, $$M_k(b_1 \mathbin\| b_2 \mathbin\| \cdots \mathbin\| b_\ell) = E_k(\cdots E_k(E_k(b_1) \oplus b_2) \cdots \oplus b_\ell).$$

The message $m = m_1 \mathbin\| m_2$ collides with the message $m' = M_k(m_1) \oplus m_2$ under $M_k$, since

\begin{align}
  M_k(m_1) &= E_k(m_1), \\
  M_k(m_1 \mathbin\| m_2) &= E_k(E_k(m_1) \oplus m_2), \\
  M_k(M_k(m_1) \oplus m_2)
   &= M_k(E_k(m_1) \oplus m_2)
    = E_k(E_k(m_1) \oplus m_2).
\end{align}

If the CCM ciphertext for $m_1$ revealed $M_k(m_1)$, then an adversary could use that and the CCM ciphertext for $m$ to forge the CCM ciphertext for $m'$ since the CTR encryption preserves $\oplus$.  To thwart this, CCM encrypts the authentication tag too, with an additional block in the one-time pad generated by CTR.


Is this a Lamport signature? One-time public-private key pairs are used. The next public-private key pair to be used, is recorded with a proof c = sha3(nextPublicKey).

No, Lamport signature is a particular one-time signature scheme prescribing a particular method of verifying signatures, generating key pairs, and generating signatures.  You could use that technique to turn a one-time signature scheme such as Lamport's into a tremendously awkward stateful many-time signature scheme.


Public Randomness-Based Random Number Generator using Mobile Phone? I have an idea to create a True Random Number Generator that use randomness source from a smartphone sensors. My idea is to collect sensors data from a lot of smartphone using mobile apps and then the data is sent to the server to be processed using an algorithm to generate random number.

Is it a good idea to use that method to generate random number? and will it be better using a lot of device rather than just using one device only to generate random number? Can I call that method as Mobile sensor network?

Be careful about the phrase “True Random Number Generator”. There's a bit of hype in that phrase. You do not need to use a TRNG directly to do things like generate cryptographic keys — in fact, you should not, because all TRNG have biases, because even if the underlying physical process has a truly uniform probability distribution, it's impossible to build a perfect measurement apparatus. A good random number generator for cryptography is always hybrid: a cryptographically secure pseudo-random number generator ((CS)PRNG, also called a deterministic random bit generator ((CS)DRBG)), which is seeded by one or more entropy sources. A physical device whose purpose is to serve as an entropy source is sometimes called a “TRNG”, but a less misleading name is HRNG (hardware random number generator).

An entropy source needs to have two properties:

It needs to be unpredictable. It needs to depend on a physical process whose outcome cannot be predicted in advance. This is typically a either a chaotic physical process or a process with physically theorized unpredictability such as radioactive decay.
It needs to remain unpredictable even after the fact, i.e. its output needs to remain secret. An entropy source is no good if it's public. If your adversary can construct the same system state as you because they can read the same entropy sources, then they can generate the same keys that you're generating.

Obtaining entropy from outside is dodgy because it violates the second property. You have no way to know that the data you're collecting from smartphones is actually coming from a HRNG, and even if it is, you have no way to know that it's only sent to you and not leaked to anyone else.

Fortunately, if you do things right, then when you mix entropy sources, a bad source (not sufficiently random or not sufficiently secret) doesn't hurt: it'll contribute 0 to the total entropy of your system, but it won't nullify other, good entropy sources. So assuming that your server-side code is perfect and that at least one of your entropy sources is good, then the result is ok. The flaw in this argument is that code is never perfect.

All modern server hardware has a built-in HRNG. (If you don't trust it, you have no reason to trust the rest of the processor. So “I fear a backdoor in the processor's RNG” is not a valid argument.) Collecting additional entropy from outside has no benefit. It's a lot of infrastructure, meaning a lot of failure points and a large attack surface, for no benefit.

Gathering entropy in a distributed way like this does have a benefit for a very specific application: when you want to generate a public value which should be demonstrably random. In that case, allowing everyone to contribute their entropy, and using a public, deterministic way to combine all the submissions, does result in a demonstrably random value.


Elliptic curves with pairings at 128-bit security in libpbc? I am using Ben Lynn's libpbc to implement a BLS threshold signature scheme and I am aiming for 128-bit security (i.e., a forgery attack should take around $2^{128}$ tries).

I was wondering what curves in libpbc would provide this level of security?

There are some indications about discrete log security here but I'm not sure how to interpret them. (I don't know too much about elliptic curve cryptography.)

For example, a "type A" curve with a "base field size" of 512 bits and embedding degree 2 is said to have 1024-bit discrete log security in the link above. Does that mean a successful attack on that curve takes around $2^{1024}$ operations? Or does it mean an attack on that curve is equivalent to an attack on a group $G(q) \subset \mathbb{Z}_p^*$ where $|q| = 1024$ bits?

Any tips would be appreciated!

Later edit: A more precise estimate of the security parameter of libpbc's curves would be nice!

The security of pairing-based cryptography relies on the security of the elliptic curve (which is linked to the size of underlying finite field, or "base field") and of the finite extension field being used.

The "Dlog security" column in the linked page is the size of the finite extension field. Its security used to be comparable to the corresponding RSA security; 1024 bits would provide only 80 bits of security. However, The "Dlog security" of the extension fields used in pairings has changed with some recent research, which makes things even more complicated. See Updating key size estimations for pairings, which estimates, for example, that a BN curve with a base field of 451 bits and "Dlog security" of 5532 bits would provide 128 bits of security)

The "Base field size" is related to the elliptic curve security; in this case security is usually half of the field size (to be precise: half the size of the prime-order subgroup). The "type A" curve there would provide 256 bits of security; but since the corresponding Dlog security is only 80 bits, the overall security is only 80.

Considering that, none of the listed benchmarked curves in the page you linked to provide 128-bit security. However, libpbc does support generating curves with arbitrary sizes for some pairing types, so it is possible to generate a pairing with 128-bit security.


Can AES be used with a static key? I am making an embedded system for a project that uses AES.

As I cannot accommodate key generation (hardware constraints) I am using a static key. I can use another small algorithm to create dynamism and then pass it to the static AES.

I'm concerned about using a static key, is it safe?

AES - the block cipher - can be used to process a large amount of data. In that sense it is possible to keep a single static key. How much data is specified in this answer by Thomas on the Security.SE site: around $2^{64}$ blocks of data or 250 millions of terabytes.

Generally would want to keep to $2^{32}$ blocks of random data though ("only" 64 GiB of data) to make sure that the chance of collision remains low. How much you can actually encrypt depends in the end on the mode of operation used. For CTR mode you can for instance encrypt 64 GiB with a random 96 bit nonce $2^{32}$ times with a ~ $1 \over 2^{64}$ chance of collision as the input of the block cipher isn't random.

If the use of AES with a static key is secure therefore depends not on the block cipher but how the block cipher is used: in other words, the protocol or protocols in which it is used. It may be insecure because the mode of operation introduces constraints that are voided by your protocol. It may not be secure because replay attacks are possible, oracles exist, the combination of cipher mode and MAC mode are vulnerable to attack, the list goes on...

AES does certainly leak information if the same input block is fed into it twice. If that's an issue depends - again - on the protocol. Your small algorithm could possibly be used to generate nonces so that the input to the AES cipher is always unique.

That using such a scheme can be relatively secure is shown by memory cards such as DESFire (which, funny enough, may also use AES). These cards are generally provided with one or more symmetric keys that are static during the lifetime of the product. Of course all the devices use derived keys that are tied to some unique identity of the card, otherwise extraction of one key would be enough to destroy the functionality of all of the cards.

Still, if the master key (from which the device keys are derived) is lost from which the other keys have been derived such schemes are certain to run into some form of trouble or another. It is very tricky to perform key  management on static keys, and such schemes are fraught with danger. This is why asymmetric keys are commonly used with a PKI scheme to ensure validity. For such schemes the controlling device doesn't need to hold a master key.

Sometimes devices are also provided with multiple keys (for multiple master keys) in advance. That way the device may still be used with a new master key if one becomes compromised. Needless to say, invalidating a master key on the devices and moving to the next one is tricky at best (if you can detect compromise in the first place), but you could possibly provide key rollover for your protocol.

Needless to say, using a static key makes it very vulnerable against side channel attacks on the implementation. Compare this for instance with a secure channel which needs to be reestablished using fresh session keys any time the MAC authentication tag is invalid. Those keys are probably invalidated before you can find out anything interesting about them.


DES Subkeys in one box? Can one calc the 16 subkeys in DES in one step ? I mean that we create for example a new “box“ where we directly permute the key k in 16 subkeys

Yes one can, this is, for example, in Stinson's book "Cryptography and Security", 1st edition, from which I quote.

  We now display the resulting key schedule. As mentioned above, each round uses a 48-bit key comprised of 48 of the bits in K. The entries in the tables below refer to the bits in K that are used in the various rounds.

Round 1

  10
  51
  34
  60
  49
  17
  33
  57
  2
  9
  19
  42
  3
  35
  26
  25
  44
  58
  59
  1
  36
  27
  18
  41
  22
  28
  39
  54
  37
  4
  47
  30
  5
  53
  23
  29
  61
  21
  38
  63
  15
  20
  45
  14
  13
  62
  55
  31

Thus the round 1 subkey uses bits 10,51,...,31 in that order.


Efficient Robust Private Set Intersection Questions I am trying to implement Efficient Robust Private Set Intersection using additive ElGamal.

I am trying to run the full protocol mentioned in Section 3.4 on the following inputs:

$p = 17$ (prime)
$g = 6$ (generator)
$x = 5$ (private key)
$k = g^x \pmod p = 6^5 \pmod{17} = 7$ (public key)

Suppose the clients inputs are 1, 2. Then $P(x) = (x-1)(x-2) = x^2-3x+2$, and therefore the coeffiecients to encrypt are $(1, -3, 2)$. I chose $y = 10$ and so the encrypted values are:

$1$ becomes $(15,12)$
$-3$ becomes $(15, 1)$
$2$  becomes $(15, 4)$.

The Server Side Input Set $S=\{1\}$ and the random value $r0$ corresponding to $\{1\}$ is $r_0=2$.

With the above problem in context, I have some questions:

What does P 0,j refer to in Step 7. Can you please give an example?
In Step 8, suddenly variable i is introduced along with j. What does i, j, refer to?
In Step 8, ENC() function has a ; in between. How do we interpret ENC(a;b)?

In general, you might find it more useful to look at the full description of the protocol on page 137 of the paper you cite, rather than the general overview on the preceding pages.

To answer your specific questions:

From page 137, step 8 (which corresponds to step 7 in the general overview):

  "For each $y_j \in Y$, $S$ chooses a random polynomial $P_{0,j}$ of degree $k + k (\lfloor \log n \rfloor + 1)$ with constant coefficient equal to $0$..."

To choose a random polynomial, you just choose every coefficient (except the lowest one, since that's specified to be zero) uniformly at random from the field you're using.
From page 137, step 9:

  "For each $y_j \in Y$, for $1 \le i \le 10k(\lfloor \log n \rfloor + 1)$, using the sharing polynomials obtained in Steps 6, 7, 8, and a random value $r_{i,j}$, $S$ computes: $Out_{i,j} = $..."

See section 2, "Deﬁnitions and Building Block Protocols" on pp. 127–128.  It looks to me like the choice between using a comma or a semicolon to separate the arguments to $\rm ENC$ is merely a stylistic / typographical one: ${\rm ENC}(x,r)$ and ${\rm ENC}(x;r)$ should mean the same thing.
Yes, there presumably is, although I cannot absolutely confirm that for you without actually reading the whole paper.


How secure is reducing length and concatentation of hash? Let's say we have input data X and a hashing algorithm H that produces 256-bits of output (e.g. SHA256).

Now, let's take a second hash function G that produces 128 or more bits of output (say RIPEMD128 or SHA1). If we define our final hash function L := sub128(H(q)) + sub128(G(q)), where sub128 takes first 128 bits of the result and + is concat, so that the result is 256 bits again.

Is it now more, less, or about the same difficulty to Y such that L(X) = L(Y) compared to how difficult it is to find Y such that H(X) = H(Y)?

Actually, I believe that both sub128(sha256(q)) + sha128(sha1(q)) and sub128(sha256(q)) + sha128(ripemd128(q)) allow a forgery attack in about $O(2^{70})$ time; hence it would appear to be weaker than SHA-256.

Here's how it works: for both SHA1 and RIPEDM128, there are known ways to find collisions in about $O(2^{63})$ time or so; there are ways that take an intermediate state, and find two different message segments of the same length that both result in the same intermediate state after processing.  So, what we do is find 64 consecutive such different message segments; this gives us a $2^{64}$ wide collision; that is, $2^{64}$ distinct messages that all result in the same hash.  The effort involved is 64 times the basic collision attack, or about $O(2^{69}) time.

Once we have $2^{64}$ messages that are all collisions for SHA1/RIPEMD128 (and hence are collisions over the first 128 bits in the case of SHA1), we SHA-256 hash all of them; with good probability, we'll find a pair that collides in the first 128 bits of the SHA-256 hash.

This pair is your collision over your $L$ function...


Terminology: Is a block cipher in counter mode still considered a block cipher or is it classified as a stream cipher? I'm confused about what terminology to use. I see people referring to such a cipher-MOO combination using both terms.

A block cipher is a block cipher. But if it is used within counter mode it becomes a block cipher within a streaming mode of operation. The resulting cipher has the external properties of a stream cipher. The block cipher now acts as a stream cipher. But I would not call it a stream cipher, because that would probably fool readers that the cipher has the internal design properties of a stream cipher.

In other words, streaming modes such as CTR simulate a stream cipher, but it doesn't emulate it. Externally it does show it to have certain properties, but it is does not try to be one internally. For instance, the key remains protected by the block cipher, rather than by properties of CTR which defines how to perform the streaming.

For these reasons I would prefer a sentence like "using CTR mode lets you use a block cipher as a stream cipher" rather than "using CTR mode turns the block cipher into a stream cipher". You could use the term "stream cipher" after such a clarification, I suppose, in case you don't want to get stuck with "block cipher in stream mode of operation" which may be too large / descriptive in texts.


AES-256 GCM IV guidelines If I use for example AES-256 (GCM), and my message is bigger than 256 bit (broken into smaller 256 bit blocks for encryption), should the IV change for every 256 bits of the message?

The IV for GCM mode, in this case the thing we call the Nonce, is different from the IV used for the CTR mode inside of GCM.

Additionally as per the wording of your question, AES256 has a 256-bit key and a 128-bit block, not a 256-bit block, and encrypts plaintext in 128-bit increments.

For GCM, you MUST use a unique Nonce for every message. Inside GCM, the Nonce is turned into the CTR IV. If you look at kelalaka's answer, if the Nonce is 96-bits, the CTR IV is the exact same thing. If it is some other size, it converts it to a 96-bit IV using the referenced algorithm. CTR mode uses the IV plus a counter starting at 1 to generate the stream. The 96-bit IV plus the 32-bit counter equal the 128-bit input block to the cipher.

([     IV     ][ctr1]) -----> [AES] -----> ([      STREAM1      ])

The output 128-bit stream block is used to encrypt the plaintext blocks. If there are multiple blocks of plaintext, only one can be encrypted with a given counter, so it is incremented by 1, and the same operation is repeated to generate the next 128-bit stream block. If the final plaintext block is shorter than 128-bits, the unused stream bits are discarded.

MESSAGE = ([     PLAINTEXT1    ][     PLAINTEXT2    ][ PLAINTEXT3 ])
AUTHDAT = additional data to authenticate
LEN_T = desired length of authentication tag
L = length_64(AUTHDAT) || length_64(MESSAGE)
NONCE = 96-bits, therefore IV=NONCE
H = AES_K(0x00000000000000000000000000000000)
ctr0 = 0x00000001, ctr1 = 0x00000002, and so on

([     IV     ][ctr0]) -----> [AES] -----> ([      STREAM0      ])

([     IV     ][ctr1]) -----> [AES] -----> ([      STREAM1      ])
([     IV     ][ctr2]) -----> [AES] -----> ([      STREAM2      ])
([     IV     ][ctr3]) -----> [AES] -----> ([      STREAM3      ])

([     PLAINTEXT1    ]) XOR ([      STREAM1      ]) = ([     CIPHERTXT1    ])
([     PLAINTEXT2    ]) XOR ([      STREAM2      ]) = ([     CIPHERTXT2    ])
([ PLAINTEXT3 ])        XOR ([      STREAM3      ]) = ([ CIPHERTXT3 ])

CIPHERTEXT= ([     CIPHERTXT1    ][     CIPHERTXT2    ][ CIPHERTXT3 ])

H = GHASH(H,AUTHDAT,CIPHERTEXT,L)
TAG = truncate_LEN_T( H XOR STREAM0 )

As many blocks are generated as required to encrypt all the plaintext, as long as the limit of GCM is not reached, which is 549,755,813,632 bits, or 256 bits less than 64GiB, as explained here.


How can I take advantage of repeated patterns in non random RSA prime factors? I am researching vulnerable RSA moduli which are composed of primes generated with poor entropy. Having a list of these primes I searched for variable sized repeated patterns among them and I noticed the following:

DD93536E58A60B0F56BF95FAEDC7CA42A9C9809A0AAE2FC971C3D9963587ABCEAF2BAB479A68DDC9EFF0E98F0F5FD488A9DD08CC51C01E9A3CFE46CA10BF6AB5
DD93536E58A60B0F56BF95FAEDC7CA42A9C9809A2CF5B9957C2E6FD04E817F03D2E174BB79364A0FC0BF365807A1F9E3286A04EB90FBE9DD52B0A2F12222AB51
DD93536E58A60B0F56BF95FAEDC7CA42A9C9809ABB02D6D274A02869AF059E586EED6DC634FCC33C455504DD40FC43D23544AC4E8F2C5E5C64E3E7530C7EDB07
DD93536E58A60B0F56BF95FAEDC7CA42A9C9809ACEF6287DF02847947530B8CA9A125ACCB53EC922D6E9775A3B0169894ED5A46B281C17AF4583874B715B07BB

Four distinct primes have in common their first 160 bits. Apart from being obvious that these primes have been generated by a weak random number generator how can they be used to derive some other primes generated from the same RNG that are potential factors of other moduli?

Theorem 1 of "Implicit Factoring with Shared Most Significant and Middle_Bits" by Jean-Charles Faugère, Raphaël Marinier, Guénaël Renault from 2010 deals with factoring products of two primes where some fraction of the MSBs are common to one of the primes in each of the composites. If I read their bounds correctly, their method must only be useful for quite unbalanced primes.

"Let $N_1=p_1*q_1,N_2=p_2*q_2$ be two n-bit RSA moduli, where the $q_i$s are $\alpha$-bit primes and the $p_i$s are primes that share the $t$-most significant bits, If $t>2*\alpha+3$ then $N_1$ and $N_2$ can be factored in time quadratic in $n$"


RSA OAEP Error Detection Probability With reference to this question:

First, when using padding (PKCS or OAEP), if the ciphertext has errors in transmission we'll always get an error at the decryption process?

where the answer is:

Yes, with extremely high probability. This is basically a chosen-ciphertext attack and RSA-OAEP is fully immune to them, so the odds that you won't detect this attack (a.k.a. "error") are extremely low (below $2^{−128}$).

May I know how the $2^{−128}$ is computed? Is it true for RSA 1024 and 2048 bits?
Some Finding
With reference to https://tools.ietf.org/html/rfc3447, Chapter "3. EME-OAEP decoding", point g(as below):

g. Separate DB into an octet string lHash' of length hLen, a
(possibly empty) padding string PS consisting of octets with
hexadecimal value 0x00, and a message M as
DB = lHash' || PS || 0x01 || M.
If there is no octet with hexadecimal value 0x01 to separate PS from
M, if lHash does not equal lHash', or if Y is nonzero, output
"decryption error" and stop.  (See the note below.)

For the implementation of openssl, SHA1 is used and SHA1 is 20 bytes and implies the length of lHash(and lHash') is 20 bytes. Therefore, I will suggest that the probability of error rate is below $2^{−160}$. Can anyone have some contribution on this? thanks.
P.S.
From the source code for openssl(https://docs.huihoo.com/doxygen/openssl/1.0.1c/rsa__oaep_8c_source.html), the RSA_padding_check_PKCS1_OAEP(), line 152, it codes as below. I believe it is checking for if lHash does not equal lHash', or if Y is nonzero. Can anyone have a view on this? thanks.

if (memcmp(db, phash, SHA_DIGEST_LENGTH) != 0 || bad)

In OAEP we pad the message with $k_1$ zero bits and $k_2$ random bits. It's the zero bits which give you verification. The all or nothing gurantee means if you change anything you will flip all bits with probability 0.5 and the chances of getting $k_1$ zero bits by chance is 1 over $2^{k_1}$


How did someone discover N, order of G for SECP256k1? Could someone please explain, in simple and easy terms, how the creators did (or should have) derived the N, order of G for SECP256k1?

Its my understanding its derived from

p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

aka

p = 115792089237316195423570985008687907853269984665640564039457584007908834671663

and that the value itself, of N is

N = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

aka

N = 115792089237316195423570985008687907852837564279074904382605163141518161494337

I understand that (N-1) is the total number of valid points on the curve, but how was that determined without going through and trying to count them?

I have seen similar questions, but the answers are either using terminologies I don't understand and or don't contain a "simple" and "easy" explanation.

I understand that (N-1) is the total number of valid points on the
  curve

Actually no. $N$ is the number of points on the curve, $N-1$ is the number of non-trivial points, where the point at infinity $\mathcal O$ is the trivial point (because it is essentially the $0$ for curves).

  Could someone please explain, in simple and easy terms, how the
  creators did (or should have) derived the N, order of G for SECP256k1?

First, let's assume we already know the order of the curve, ie the number of points on it. Let's call this number $n$. It turns out that for secp256k1 $n$ is a prime. Now we know by Lagrange's Theorem the order of any subgroup (like the subgroup generated by $G$) of secp256k1 must divide $n$, so either have $1$ or $n$ elements. But the only element that generates a subgroup with one element is $\mathcal O$ (because $\mathcal O+\mathcal O=\mathcal O$) and thus $G$ must have order $n$.

But how do we find the order of the curve? It turns out that mathematicians have already solved this problem and found an algorithm to efficiently count the number of points on a curve without actually visiting every single one, it's called Schoof's algorithm. Now the details of this algorithm are very complex and thus I won't go into them here. If you really want to know, you can read the linked article and the references given at the bottom of the page.


How to generate a ciphertext independently decodable with multiple keys? Is it possible to encrypt a message in such a way that multiple keys can independently decrypt it?

In other words:

Having knowledge of $key_1, key_2 ...key_N$, which are different symmetrical keys, is it possible to generate a ciphertext that can be independently decrypted using either $key_1$ or $key_2$ or $key_N$, in such a way that the length of the ciphertext is less than directly proportional to $N$?

One way to do it is to generate a random, single-use key $K$ and encrypt (and preferably authenticate) the message with that. Store the (authenticated) encryption of $K$ under each of $key_1, …, key_N$ alongside the message. The required storage is $\Theta(N + \text{message length})$.

This is routinely done when transmitting messages using asymmetric encryption, for example when sending an email encrypted with PGP to multiple recipient. A the message is encrypted and authenticated with a single-use key, and the encrypted email contains the encryption of that key with each recipient's public key in addition to the ciphertext.


In a AES-CBC + HMAC architecture, Is it secure to send a second IV in a message to a device incapable of producing satisfactory random numbers? There are many threads here explaining the need of a random and unpredictable IV for the AES-CBC.

I am building a home automation system with security for a school project where a Raspberry Pi creates a separated WPA2 network to communicate with many ESP8266 Wi-fi modules via HTTP requests. Each new message from the central node is encrypted with a key and a newly generated(using "/dev/urandom") IV.

The message payload structure is:

plain-text IV || cipher-text || HMAC-SHA256

However, the answer of a GET request needs to be encrypted  too. From what I read, encrypting the answer with the same IV from the received request may not be the ideal.

So is it okay for the central node to send another IV, which the esp8266 is going to use for encrypting the answer?

And what is the best way to send this IV?

Inside the encrypted message(cipher), or
As plaintext, making the payload:

IV2 || IV1 || cipher || HMAC(hash of IV2 || IV1 || cipher)

And what is the best way to send this IV?

CBC IVs need to be unpredictable to attackers. If you just send them along your other IV they are no longer unpredictable, hence encrypting them as well would be the way to go and should provide reasonable security.

  plain-text IV || cipher-text || HMAC-SHA256

What you are doing here is the infamous Mac-Then-Encrypt with CBC. This is a really bad idea. A really, really, really bad idea. This is the source of many attacks on TLS. Please, learn from the past mistakes done with TLS and use a pre-made authenticated encryption mode, such as EAX or CCM, or at least Encrypt-Then-Mac with CTR.


Combining multiple cryptographic keys to generate an encryption key We have a system that has several SecretKeys (for example, one for a user, and one for us). We want to encrypt data in a way that requires all of those keys to be available in order to decrypt.

I think that the correct way to do this is to use a key derivation function of some sort to merge the source SecretKeys together, and use the result a the encryption key.

Given that all of the source keys are cryptographically generated SecretKeys using the following (apologies in advance if this isn't the right :

KeyGenerator generator = KeyGenerator.getInstance("AES");
generator.init(256);
return generator.generateKey();

is it safe to just use a cryptographic hash of the source keys, or is that potentially introducing a vulnerability somehow? Like this:

SecretKey secretKey1 = ...
SecretKey secretKey2 = ...
SecretKey secretKey3 = ...

MessageDigest md = MessageDigest.getInstance("SHA-256");
md.update(secretKey1.getEncoded());
md.update(secretKey2.getEncoded());
byte[] digest = md.digest(secretKey3.getEncoded());

SecretKey mergedSecretKey = new SecretKeySpec(digest, "AES");

The database we are working with doesn't support native encryption, and we are only encrypting a very small number of fields.

Related (but no helpful responses): Using multiple cryptographic keys for encryption?

As long as the total entropy (unpredictability measured in units of bits) of the inputs is at least as large as the derived key size then it is okay in practice.

Reasons why it might not be good in theory (but really is harmless):

In theory you lose a tiny bit of entropy due to collisions. (Small enough not to ever ever ever matter for short inputs, acceptable mainstream hash functions, and greater than 128 bits of output.)
If someone hashes a known value together with a uncertain low entropy input, then reveals that value, an attacker can then enumerate likely values for brute forcing the low-entropy input value. Since the inputs are secret keys (with high entropy) and since the output is kept secret, it is no concern.
Some hash functions could be designed to be resistant to collision, first preimage, and second preimage attacks. But that doesn't guarantee the output is pseudorandom. It's okay because SHA-2 has enough scrutiny to believe it's practically a random oracle. And even if collisions or minor biases are found some day, the fact that inputs contain long random uniform bit strings means it won't effect key derivation.

I assumed your SecretKeys are symmetric shared secret (uniform full entropy) keys. (I don't know why you would want to combine shared secret keys to make a shared secret key and why the process that made the input keys can't be used.)

You can also hash public keys (but they add zero entropy because of their publicness) and Diffie-Helman style shared secrets. Key exchanges in protocols like TLS can use key derivations that are a function of inputs including a DH shared secret, public authentication keys, and protocol handshake details fed to a hash function to generate symmetric keys used for encryption and authentication.


Linear Related Message Attack on RSA I have a question about this attack: Oded Yacobi and Yacov Yacobi, A New Related Message Attack on RSA (in proceedings of PKCS2005).

Given $e$ linear related messages encrypted with RSA:
$c_i = ({x_i}^e \bmod N)$

where, $x_i = a_i*x + b_i$,

the author claims that given the $a_i$'s and $b_i$'s values, it is possible to obtain the original message $m$. He shows that for the case of $x_i = x + b$, but I can't see how is the general form to apply this attack for messages $x_i = a_i*x + b_i$.

More specifically, I'm having difficulties in calculating the $p_k$ values presented in section 2.2.

Thanks!

The ability to recover $x$ in the latter case is a direct consequence of RSA's homomorphic property and the ability to recover $x$ in the former case.

Suppose you are given the equations (with $c_i,a_i,b_i$ known):

$$c_i=(a_i\cdot x+b_i)^e\bmod N$$
$$\iff c_i=(a_i\cdot x+a_i\cdot b_i\cdot a_i^{-1})^e\bmod N$$
$$\iff c_i=a^e_i(x+b_i\cdot a_i^{-1})^e\bmod N$$
$$\iff c_i\cdot a^{-e}_i =(x+b_i\cdot a_i^{-1})^e\bmod N$$
$$\iff c_i' =(x+b'_i)^e\bmod N$$

With $b_i':=b_i\cdot a_i^{-1}$ and $c_i':=c_i\cdot a^{-e}_i$ which both only depend on known quantities, as you can always find multiplicative inverse $\bmod N$ (or if you can't in one instance, you can factor $N$) and you know $e,c_i,a_i,b_i$.

So you can use the ability to recover $y$ from $g_i=(y+f_i)^e\bmod N$ to recover (using the above equations) $x$ from $c_i=(a_i\cdot x+b_i)^e\bmod N$.


Prepend information about encryption implementation to the stored data I want to preface this by saying i will not be using any of this code/information in a live project, this is only for learning/fun (so I welcome some speculation)

I was looking at how the PHP crypt() function works, and i had an idea. crypt() prepends a few characters at the start of the hash it creates that convey information about how the hash was created (algorithm used, number of rounds, etc...). This gives a beneficial side effect of being able to check if the hash was created up to a certain standard (check if it was hashed with a minimum amount of rounds) and rehash it if it was not.

I had the idea to use this idea for symmetric key encryption (AES128) as well. It would allow me to very simply enforce a "minimum security level" that i can increase at any time and run on my entire database, and it will re-encrypt any data that does not meet the standards. Changing cipher, salt-size, hashing algos, rounds for PBKDF2, etc. will be much easier to do and much faster to implement, the only thing that would be kept secret is the key.

The exact data i wanted to include is:

Salt Size
MAC Size
Number of rounds used for PBKDF2
The hashing algorithm used to create the MAC (ex. SHA512)
The hashing algorithm used for PBKDF2 (ex. SHA512)
The cipher algorithm used in the encryption (ex. AES128)
The mcrypt mode used in the encryption (ex. CBC)

Essentially the hash would look like 128|64|1000|SHA512|SHA512|rijndael-128|cbc|CipherText

So please, tell me why I'm stupid!

This is fine. Be sure to verify all the values and include them when computing the MAC.


Isaac nth number from run Is there a way of getting the nth random number from a particular seed run in ISAAC?  i.e. one day run a selection of 256 numbers and the next day run from the 256th number to get the next 256 random numbers?  I presume no as I haven't been able to and I've tried everything I can think of but there may be a mathematical solution.

No, that won't work, and we don't even need to assume anything about the security of ISAAC to prove that.  A simple counting argument is sufficient.

Basically, the internal state of the ISAAC cipher consists of slightly over one kilobyte of data (consisting of an array of 256 32-bit integers initialized using the key/seed, plus three additional 32-bit values that don't depend on the seed).  On each call to the isaac() function, this internal state is mixed in a somewhat complicated way, and also used to compute a kilobyte of pseudorandom keystream output (also represented as an array of 256 32-bit integers).

The important part here is that, in order to compute the next kilobyte of output, you need to know the entire kilobyte of internal state.  While the output of ISAAC does not directly expose this internal state, in principle it might be possible for an attacker with unlimited computing power to reconstruct the whole internal state from the previous kilobyte (or more) of the output.  However, if you only have a single 32-bit integer of the output, then there's no way to do that even in principle — there are many, many possible internal states that could've produced those 32 bits of output, and each of those states will yield a different further keystream.

Now, there's one notable exception to this: if you know that ISAAC was seeded poorly, so that there are less than $2^{32}$ distinct possible seed values, then you can simply try each of these seeds and see which one produces the same 256th output integer that you observed.  This is because the entire ISAAC internal state is initially generated based on the seed input, so that a limited number of possible seeds implies an equally limited number of possible states.

(Note that, depending on the number of possible seeds, you might get more than one match, but probably not too many more.  In particular, for $n$ possible seeds, the expected number of coincidental extra matches is $\lambda = n/2^{32}$, and the actual number of extra matches observed is approximately Poisson distributed with rate $\lambda$.  This distribution is not specific to ISAAC in any way; any sufficiently random-looking map from $n$ possible inputs to $2^{32}$ possible observed outputs will have approximately the same statistical behavior.)


How should I address message size limits in RSA encryption? I am making an end-to-end encryption software program in Java using RSA. I am using BigIntegers and its number theory methods. (I know this is a very slow approach, but I just want to learn to the concept of encryption through this). I have a lot of questions, feel free to only answer as many as you'd like.
I have most of the encryption done already but I have questions about the size limitations of RSA and its technical details.
Say I generate primes p and q for my RSA which are of bit length 256 and 257.
According to my intuition on the number theory behind it (using modulus) and a lot of test cases, I should be able to safely encrypt and decrypt any number with bit lengths L < 513 (256+257) without losing information. Is this correct and will work 100% of the time? Also if L happens to be a 5-bit number, its encrypted version will still be around ~512 bits long?

I want to abstract my BigInteger (Java class) encryption to encrypting any byte[] of data. My plan is to split the byte[] into 512-bit (64-byte) chunks and encrypt those chunks by converting them to a BigInteger and then encrypting them. Is this a good idea? How is it done in industry?

Should I make the bit length of p and q smaller/larger and make the encryption chunks size smaller/larger to optimize performance?

Also, after I encrypt a number, the encrypted version ranges anywhere between 0 and 512 bits. How should I added padding to this byte[], in order to keep them of uniform size, for easy decrypting? Should I just add 0's to the most significant bit side and pad until it is always 512 bits?

Thank you so much for the help in advance!

I should be able to safely encrypt and decrypt any number with bit lengths L < 513 (256+257) without losing information. Is this correct[?]

No.  The RSA operation $x \mapsto x^e \bmod n$ is unfit to ‘encrypt’ even short messages directly.

Here is what you should do:

Pick a hash function $H$ up front, like SHA-256 or SHAKE128, and bake it into your program.  (Don't let users pick it—users have even less of an idea of what's up.)
Pick a symmetric-key authenticated cipher up front, like AES-GCM or NaCl crypto_secretbox_xsalsa20poly1305, and bake it into your program.  (Again, don't let users pick it.)
To encrypt a message $m$, which is a bit string of arbitrary length, for public key $n$:

Choose an integer $x$ with $0 \leq x < n$ uniformly at random.
Compute $y = x^3 \bmod n$.
Compute $k = H(x)$, where $x$ is encoded as a bit or octet string in some standard way, e.g. little-endian.
Encrypt $m$ using your authenticated cipher under the key $k$, giving a ciphertext $c$.
Send $y$ and $c$.  $y$ is called the encapsulation of the key $k$.

To decrypt a ciphertext $c$ with key encapsulation $y$:

Solve $y \equiv x^3 \pmod n$ for $x$.  (E.g., compute $x = y^d \bmod n$ where $d$ solves $e d \equiv 1 \pmod{\phi(n)}$, or compute $x_p = y^{d_p} \bmod p$ and $x_q = y^{d_q} \bmod q$, and then combine using the Chinese remainder theorem, etc.)
Compute $k = H(x)$.
Decrypt $c$ using your authenticated cipher under the key $k$.

If decryption fails, drop it all on the floor and stop here.  (If you skip this step, you are setting yourself up for efailure.)
Otherwise, it returns a message $m$, which is the plaintext message you return in the end.

This system—generating a symmetric key $k = H(x)$ for uniform random $x$ and concealing it as $x^3 \bmod n$—is called RSA-KEM, and it is an example of a public-key key encapsulation mechanism, which can be generically composed with an authenticated cipher to get public-key (anonymous) encryption.

  Also if L happens to be a 5-bit number, its encrypted version will still be around ~512 bits long?

With the system above, the ciphertext overhead is 128 bits for the authenticated cipher (or more, if it's a particularly inefficient authenticated cipher), plus the size of your modulus $n$, no matter how long the message is.

You should not use 512-bit moduli.  They have been breakable in practice by the public for decades.  You should use at least 2048-bit moduli.  More details.

Alternatively: Just use NaCl crypto_box, or libsodium crypto_box_seal.  Faster, smaller, safer than RSA!


One-time pad encryption of ASCII characters I can't understand a question I came across in a course.

  You observe three ciphertexts all resulting from encryption of ASCII
  plaintexts containing English letters and spaces only, using the
  one-time pad and the same key. The 10th byte of the first ciphertext
  is 0xA8, the 10th byte of the second ciphertext is 0xED, and the 10th
  byte of the third ciphertext is 0xBD. What is the 10th ASCII character
  of the third plaintext?

I XORed 0xA8 and 0xBD and got 00010101
I XORed 0xED and OxBD and got 01010000
so clearly 0xED is a space and 0xBD is a character.

What I don't understand is why it is the letter 'p'.

Thank you in advance.

So you were really close. You are right that the 3rd ciphertext's 10th byte(0xED) in the 3rd message is a space. So we know 0x20 in hex is a space in ASCII. So now to find the 10th byte of the key you need to xor 0xED and 0x20 to get 0xCD(which is the 10th byte of the key). Well now that you know the key, you can xor the 10th byte of the 3rd ciphertext 0xBD with 0xCD. So you get 0x70 in hex and 'p' in ASCII.


Entropy of a random message chosen by an adversary from a subdomain Assume we have a set of random bit strings: $S=\{s_1,...,s_n\}$, where each of them is of length $\lambda$ ($s_i\leftarrow\{0,1\}^{\lambda}$).

We give the set $S$ to an adversary who picks one of the set elements at will and outputs it. Let's $s'\in S$ be the adversary's choice.

Question: What is the entropy of $s'$?

You did not define what the probability that $s_i = s^\prime$ for each $i$. Therefore entropy is undefined.

The definition of (Shannon) entropy is:

$$H = - \sum_{i} p_i \log_2 p_i$$

When you determine every non-zero probability $p_i$ then come back and enter those numbers into the formula.

Knowledge of $|S|$, the elements of $S$, or $\lambda$ is insufficient for calculation purposes. In different contexts (even if $S$ and $\lambda$ are the same), the probability of each message can follow a different distribution. The entropy depends only on what that distribution is. Therefore, the entropy of $s^\prime$ can be different depending on context.

Examples of the different contexts:

We care about the adversary's ability to guess $s^\prime$. This is trivial. The adversary picked the number. The adversary is certain what that number is. Certainty means one outcome has a probability of exactly one. The only non-zero $p$ is one. Entropy is zero because the log of one is zero.
A first party ("us") sends the set $S$ to a second party. The second party picks an element of that set. The first party wants to guess it before the adversary reveals it. The entropy can be at least zero bits and at most $\log_2 {|S|}$ bits. Exactly what value that entropy is depends on what the probability distribution is that describes which element the adversary picks.
The above scenario, except the first party tries to guess the number after the the second party reveals it to them. The entropy is zero. The first party is certain what that value is. $p = 1$
The first party chooses a set. A second party chooses an element of that set. A third party is supposed to guess what element was chosen with no knowledge of what choices the first or second party made. The entropy, $H$ satisfies, $0 \leq H \leq \log_2{|S|} \leq \log_2 (2^\lambda)$ The exact value depends both on the distribution of possible $S$ values the first party may choose and the distribution describing which element the second party may choose from any given set. See "joint entropy".


AES CBC in need of multiple IV's, possible to avoid creating duplicate iv's by using resulting cipher text 16 bytes as next iv? I saw a little close to these questions but not exactly.

Encryption method AES-256-Rijndael-CBC:

if we have multiple cipher chunks that look like this:
{iv}{cipheredchunk}{chiphered chunk}{chiphered chunk}....

I earlier got noted that we should never use the same IV for other chunks since chunks could be identical, so we need something like this:

{IV+cipheredchunk}{IV+chiphered chunk}{IV+chiphered chunk}...

My question is, is it okay to avoid adding a bunch of 16 bytes long random IV for every chunk, maybe we could use one fully random IV for the first chunk, and for next chunk use the first 16bytes of that chunk as iv for next block?

Do we keep the safety of the encryption?

Edit:

Every "Ciphered Chunk" is a completly finished encrypted message in AES256 CBC.
So if we for example have the whole plaintext message to encrypt of "abcdefghijk" and we say that every chunk is 3 letters/bytes then we do:

AES256CBC encryption on "abc" -> ciphered text("Ciphered chunk")
AES256CBC encryption on "def" -> ciphered text("Ciphered chunk")
AES256CBC encryption on "ghi" -> ciphered text("Ciphered chunk")
AES256CBC encryption on "jk" -> ciphered text("Ciphered chunk")

The reason i am doing this instead of ciphering the whole plaintext at once is since i am dealing with incredibly large files of many GB which no program or computer can handle at once.

So im trying to cipher small parts of the file in AES256 CBC mode and basically append them next to each other :)

You can indeed avoid having an explicit IV for each chunk in favor of an implicit one, and using the previous encryption's last ciphertext block is indeed one way. But:

You almost certainly need authenticated encryption that provides not just confidentiality but also message authenticity. Read up on the EFail attack, one of whose causes is CBC-based encryption software that doesn't protect ciphertexts from tampering (or more precisely, does so in an inadequate fashion).
Once you add the message authenticity requirement, it becomes very hard to escape ciphertext expansion (ciphertexts longer than the plaintext) because the ordinary way to achieve it requires you to include a message authenticity tag for each chunk. You can tune the overhead by upping the size of each encrypted chunk, but that of course increases how much memory you need to encrypt/decrypt one.

Be aware that what you're trying to do carries countless pitfalls and that it's much less risky if you use a library written by cryptography experts or, at the very very least, copy one of their designs (and copy it successfully). For example, recent versions of the popular Libsodium library include an encrypted streams and file encryption module that's designed to safely perform precisely this sort of constant memory chunked authenticated encryption, but do it carefully:

  This high-level API encrypts a sequence of messages, or a single message split into an arbitrary number of chunks, using a secret key, with the following properties:

  Messages cannot be truncated, removed, reordered, duplicated or modified without this being detected by the decryption functions.
  The same sequence encrypted twice will produce different ciphertexts.
  An authentication tag is added to each encrypted message: stream corruption will be detected early, without having to read the stream until the end.
  Each message can include additional data (ex: timestamp, protocol version) in the computation of the authentication tag.
  Messages can have different sizes.
  There are no practical limits to the total length of the stream, or to the total number of individual messages.
  Ratcheting: at any point in the stream, it is possible to "forget" the key used to encrypt the previous messages, and switch to a new key.

  This API can be used to securely send an ordered sequence of messages to a peer. Since the length of the stream is not limited, it can also be used to encrypt files regardless of their size.

  It transparently generates nonces and automatically handles key rotation.

Your CBC-based approach won't achieve all of this.

That said, just for theory's sake, an alternative way of avoiding ciphertext expansion in CBC is to use a second key and ECB encryption to generate implicit IVs from a counter or nonce.  First you generate and share or derive two block cipher keys $k_1$ (for IV generation) and $k_2$ (for encryption), and a public nonce $\mathrm{IV}$. Then for each numbered chunk $m_1, \dots, m_n$, you encrypt each block this way:

$$
\begin{align}
\mathrm{IV}_1 & = \mathrm{AES}_{k_1}(\mathrm{IV} \oplus 1) \\
c_1 & = \mathrm{AES\text-CBC}_{k_2}^{\mathrm{IV}_1}(m_1) \\
& \vdots \\
\mathrm{IV}_i & = \mathrm{AES}_{k_1}(\mathrm{IV} \oplus i) \\
c_i & = \mathrm{AES\text-CBC}_{k_2}^{\mathrm{IV}_i}(m_i) \\
& \vdots \\
\mathrm{IV}_n & = \mathrm{AES}_{k_1}(\mathrm{IV} \oplus n) \\
c_n & = \mathrm{AES\text-CBC}_{k_2}^{\mathrm{IV}_n}(m_n)
\end{align}
$$

Since the recipient knows $k_1$, $k_2$ and $\mathrm{IV}$, and can also count, they can reconstruct the $\mathrm{IV}_i$ values without the sender having to transmit them.