Practical usage of S/KEY The One-Time-Password (OTP) topic became quite popular in the recent years. But unlike the well-known HOTP and TOTP standards I haven't heard about any applications/systems implementing and using the S/KEY standard. Are there any?

There is OpenBSD, where you can use S/KEY for login-purposes.

Check the OpenBSD – Frequently Asked Questions:

  8.10 - S/Key

  S/Key is a ``one-time password'' authentication system. It can be useful for people who don't have the ability to use an encrypted channel which protects their authentication credentials in transit, as can be established using ssh(1).

  WARNING: One-time password systems only protect authentication information. They do not prevent network eavesdroppers from gaining access to private information. Furthermore, if you are accessing a secure system A, it is recommended that you do this from another trusted system B, to ensure nobody is gaining access to system A by logging your keystrokes or by capturing and/or forging input and output on your terminal devices.

  The S/Key system generates a sequence of one-time (single use) passwords from a user's secret passphrase along with a challenge received from the server, by means of a secure hash function. The system is only secure if the secret passphrase is never transferred over the network. Therefore initializing or changing your secret passphrase MUST be done over a secure channel, such as ssh(1) or the console.

  OpenBSD's S/Key implementation can use a variety of algorithms as the one-way hash function. The following algorithms are available:

  md4
  md5
  sha1
  rmd160.

  …


Paillier subtraction for negative result I am trying to figure out subtraction on Paillier.

From what I read so far, given $m_1$ smaller than $m_2$ ($m_1<m_2$)
I can compute $E(m_2-m_1)$ as $E(m_2)\cdot E(m_1)^{-1}$ where $E(m_1)^{-1}$ produce $-m_1$ when decrypted.

What is unclear to me is if I can calculate $E(m_1-m_2)$ which should result in a negative number when decrypted.

In Pailler encryption, it holds for all messages $m_1$ and $m_2$, and whatever randoms[*] are used by encryption, that:
$$\begin{align}
(m_1+m_2\bmod n)&=D(E(m_1)\cdot E(m_2)\bmod n^2)&&\text{and}\\
(m_1-m_2\bmod n)&=D(E(m_1)\cdot E(m_2)^{-1}\bmod n^2)
\end{align}$$
where the modular inverse $E(m_2)^{-1}$ is computed modulo $n^2$, that is in $\Bbb Z_{n^2}^*$.

If $0\le m_2\le m_1<n/2$ then we have
$$\begin{align}
m_1+m_2&=D(E(m_1)\cdot E(m_2)\bmod n^2)&&\text{and}\\
m_1-m_2&=D(E(m_1)\cdot E(m_2)^{-1}\bmod n^2)
\end{align}$$

When the sign of $m_1-m_2$ is unknown, we can define a modified Pailler cryptosystem. Encryption is unchanged, or/and we can compute $E(m)$ as $E(m\bmod n)$ when $m$ is negative. Decryption is modified to $D'(c)=[D(c)]_n$ with
by definition $[x]_n=((x+\lfloor n/2\rfloor)\bmod n)-\lfloor n/2\rfloor$.

Whatever random[*] is used by encryption, if $-n/2<m<n/2$, then $D'(E(m))=m$; and for all messages $m_1$ and $m_2$:
$$\begin{align}
[m_1+m_2]_n&=D'(E(m_1)\cdot E(m_2)\bmod n^2)&&\text{and}\\
[m_1-m_2]_n&=D'(E(m_1)\cdot E(m_2)^{-1}\bmod n^2)
\end{align}$$
If $-n/4<m_1<n/4$ and $-n/4<m_2<n/4$ then we have
$$\begin{align}
m_1+m_2&=D'(E(m_1)\cdot E(m_2)\bmod n^2)&&\text{and}\\
m_1-m_2&=D'(E(m_1)\cdot E(m_2)^{-1}\bmod n^2)
\end{align}$$
I fail to find who first extended Paillier encryption to subtraction, or/and to signed values with that variant $[x]_n$ of the $x\bmod n$ operator; but this is simple and natural enough that my guess is it has been independently rediscovered several times. The notation $[x]_n$ is often used in homomorphic encryption, at least since Craig Gentry and Shai Halevi Implementing Gentry's Fully-Homomorphic Encryption Scheme (extended abstract in proceedings of Eurocrypt 2011).

[*] Restrict the random integer $r\in\big[0,n^2\big)$ used by encryption to be coprime with $n$; that's overwhelmingly likely if $n$ is hard to factor.


Is this an example of a Feistel cipher? Have tried to create simplest example. A,B,C,D are 32-bit unsigned, as is k[4]. P is an expansion type p-box of 256 "random" 32-bit values. Assume key-whitening and multiple rounds/keys

#define b0(u) ((u)&0xff)
#define b1(u) (((u)>>8)&0xff)
#define b2(u) (((u)>>16)&0xff)
#define b3(u) (((u)>>24))

// rounds...
A += P[b0(D)^b1(D)^b2(D)^b3(D)] ^k[0];
B += P[b0(A)^b1(A)^b2(A)^b3(A)] ^k[1];
C += P[b0(B)^b1(B)^b2(B)^b3(B)] ^k[2];
D += P[b0(C)^b1(C)^b2(C)^b3(C)] ^k[3];
k+=4
// end rounds

Also, is there a term for this specific method? (besides just "weak")

This is a simple 128-bit block cipher, reversibly changing a 32-bit word of the state at each of 4 steps shown. It is very similar to an unbalanced Feistel cipher, except that the change of state is with += rather than the conventional ^=. In the context that deviation has three consequences, with the first rather desirable:

It creates alternation of ^ and + in the diffusion pattern.
Decryption is less similar to encryption than in a Feistel cipher (I guess the decryption code use uses -= ).
Hardware implementation would be slightly bigger/more power hungry, perhaps even slightly slower; but 1 more than compensates, and that's a non-issue in software.

To hope for security, there must of course be MUCH more rounds than shown. We have not even reached full diffusion (nothing in B or C influenced the outcome of A ). As a crude reference, AES-128 modifies its full state 10 times (discounting the initial XOR with a subkey); and Speck-128-128 modifies it 16 times. Security will depend a lot on the number of rounds, on a sensible choice of table P, and on the key schedule (producing the array k of subkeys from the actual key).

Note: Implementation in software is likely to suffer from data cache timing dependencies and other cache-related side channels, due to indexing in P at data-dependent indexes.

Note: as pointed by Poncho (correcting my mistakes), this cipher generates an even permutation; but that's not a weakness, since that reveals 1 bit of information only after $2^{128}-2$ input-output pairs are collected.


Can a PRNG with a fixed amount of entropy always be detected? Given a fixed seed (i.e. no ongoing source on entropy), is there (practically or theoretically) any PRNG algorithm that can generate an infinite sequence of random numbers such that an observer cannot detect that it is a PRNG rather than a genuinely random source ?

All widely adopted cryptographically secure PRNGs seem to use entropy collectors to supplement, but it's not clear if that's actually a required for any CSPRNG.

The reasoning behind this question is: If a hardware or software RNG has been compromised such that it's seeded with a known key and the RNG doesn't use any additional real entropy source, will there always be an external method of detecting that it's not a real random source.

No, there is no reliable way to detect such shenanigans (through external testing), if the adversary is sufficiently sophisticated and has the power to embed backdoors in the hardware you are using.

If the PRNG is specified to be a deterministic algorithm, then in principle one can run the PRNG on a known key and compare its output against the output from an independent implementation.  NIST calls such a PRNG a "deterministic random bit generation" (DRBG) algorithm.  In effect, you can use black-box testing of it to check that it seems to be working correctly, under testing conditions.

However, there are some major shortcomings in this testing-based methodology for checking the PRNG implementation.  Just because the hardware works correctly under test conditions doesn't necessarily mean it will work correctly when you need it to.

One problem is that there's no way to verify that the hardware is actually deterministic.  For instance, the hardware might behave correctly almost all of the time, except that under certain special environmental conditions, it behaves incorrectly.  Those special environmental conditions might be arbitrarily hard to find during testing: e.g., the backdoor might be activated immediately after receipt of a network packet containing a magic 128-bit value (or some other "secret knock").  There's basically no good way to detect this kind of backdoor with black-box testing.  Therefore, in practice, if you're concerned about backdoors in the hardware, you're not gonna be able to verify that the hardware PRNG is secure merely through external testing.

This problem is not limited to PRNGs; this problem is universal.  This is true of all the hardware you use for computation.  If your CPU has a backdoor, you're hosed -- period.  There's no good way to verify that your CPU is free of backdoors, through external methods.  That's life.


Security of simple xor and s-box cipher? What weaknesses (or strengths) do block ciphers based on only key xor and s-box have when operating in CBC mode?

A cipher's internal primitive might be a simple as this:

$C = S[M \oplus k]$, where $C$ is ciphertext, $M$ is the plaintext message, $k$ is the key and $S$ is an S-box.

Assume the follwoing:

The key $k$ is sufficiently large and is random.
The initialization vector used by CBC is random.
The block size is reasonable, e.g. 128 or 256 bits.
The S-box is chosen such that correlation bias between $S[x]$ and $x$ is low.
The S-box is chosen such that $S[a]$ and $S[b]$ are independant for any random $a$ and $b$.

EDIT: Completely re-written to be more general, removing all specific implementation details.

Here's the original custom scheme, which was considered too broad to be a valid question:

$k$ is a 256-bit key, $S$ is a 16-bit S-box that has some set properties.

The cipher operates in CBC mode (as you'll see in the second step), has a block size of 256 bits, and operates as follows for a total of 16 rounds:

$k_r = rot(k, r)$, where $k$ is the key, $r$ is the round number and $rot()$ is a circular shift operation.
$C_n = S[M_n \oplus k_r] \oplus C_{n-1}$ where $n$ is the block number (assume $C_{-1}$ is the IV)
Select $a = 3(r+n) \space mod\space 256$
Select $b = (k_r \space\& \space 255) \space mod\space 256$
Swap the bits $C_n[a]$ and $C_n[b]$
$C_n = S[C_n]$

Let a "block cipher" be defined with a fixed S-box $S$ (i.e. a permutation of some space) and a key $K$ (same size than a block), such that the encryption of a block $M$ is $C = S[P\oplus K]$. Everybody knows $S$ and can apply and invert it (that's a "S-box", not a "key" -- if the S-box is "key dependent" then the S-box is itself a block cipher in its own right, and that's another question). Since the key has the size of a block, blocks are supposed to be large enough to defeat exhaustive search on the key (say, we use 128-bit blocks).

Hence, given a single known plaintext block and the corresponding ciphertext, an attacker can trivially recover $K$: $K = S^{-1}[C] \oplus M$. This is weak unless you ever encrypt a single block with a given key, in which case this is just One-Time Pad. The S-box here is a red herring: as a generic rule, any fixed public permutation for which either the input or output is known can be "removed" at will, so it adds nothing to security. For instance, in DES, the "Initial Permutation" and the "Final Permutation" (which swap bits around in a 64-bit word) can be abstracted away from the security analysis, because anybody can apply and unapply them. Without the S-box, we get $C = M \oplus K$, the well-known equation for OTP.

Since a fixed permutation is as good as gone when it operates on known values, and since we usually consider that the attacker knows some plaintext/ciphertext pairs, this means that a S-box, to be useful, must be "isolated" from both plaintext and ciphertext. So we can imagine the following design:

$$ C = K \oplus S[M \oplus K] $$

This is what @Ethan suggests to study as an exercise (except the he talks about 16-bit blocks, hence a 16-bit key, which is trivially undone through exhaustive search; here, let's assume that $C$, $M$ and $K$ are sequences of 128 bits). If you look at the slides that Ethan points to, you will learn that this is a special case of a more generic construction from Even and Mansour, which goes like this:

$$ C = K_2 \oplus S[M \oplus K_1] $$

with two $n$-bit keys $K_1$ and $K_2$. John Daemen has then shown that although the total key material length is $2n$ bits, you get much less security, actually no more than $2^{n/2}$. With $n = 128$, that's "64-bit security", a rather low value against today's technology (64-bit exhaustive key search is expensive but has been done at least once with thousands of machine and 5 years of computation). With $n = 256$, we could hope for 128-bit security, albeit with 512 bits of key material.

However, there are two important points about that:

The subkeys $K_1$ and $K_2$ should be unrelated. Using the same key for both, or simply keys which admit simple algebraic relations, may allow for many additional attacks.
The $2^{n/2}$ bound is for a generic S-box, i.e. a permutation taken at random over all the permutations of $n$-bit blocks. But the S-box is computable. There exists a rather compact piece of code which can run it in both directions. Yet, there are $2^n!$ permutations of $n$-bit blocks, which implies that the minimal representation of a random permutation will need, on average, at least $2^{264}$ bits, if $n = 256$. This is ludicrously high (it will not fit in the known Universe). Conclusion: an actual implementation of that cipher will use a specific S-box out of the very limited set of S-boxes than can be computed by some code which fits in a few kilobytes of opcodes and constant arrays. The S-box necessarily has some structure. Structure might be exploitable, and often is. The $2^{n/2}$ theoretical strength may then be hard to reach in practice.

So the Even-Mansour scheme is not "secure enough". What do cryptographers do in such a situation ? They add more rounds ! So we are talking about something like:

$$ C = K_5 \oplus S[K_4 \oplus S[K_3 \oplus S[K_2 \oplus S[K_1 \oplus S[K_0 \oplus M]]]]] $$

for, say, 5 rounds. How many rounds do we need ? This depends on the specific unavoidable structure of $S$, and also on how "different" the $K_i$ are (we would, in practice, generate the $K_i$, dubbed "subkeys", from a master key $K$ through a deterministic process -- the "key schedule" -- which itself will have some potentially exploitable structure). We want the whole thing to be decently efficient, so we cannot add thousands of rounds, and we must cope with a relatively simple $S$.

Down that road lies... the AES itself. With 128-bit blocks and a 128-bit master key, the AES uses 10 rounds, hence 11 subkeys. Each round $S$ is a combination of a few operations, some linear (in a given vector space over $\mathbb{F}_{256}$), and an internal fixed permutation over 8-bit blocks (what the AES specification calls "the S-box", but not what we call $S$ in this text !). The AES is believed secure for what it is meant to be. It has raised a few concerns about "related keys": pairs of keys which induce the corresponding AES instances to behave in a related way, which can be detected; nothing serious for encryption, but something to watch for if you want to use the AES as part of, say, a hash function. This is due to the mathematical structure in the key schedule. The Whirlpool hash function is a hash function derived from the AES, and the first thing the Whirlpool designers do was to replace the AES key schedule with something with less exploitable structure (but also slower).

Summary: designing a block cipher as a sequence of XOR with (sub-)keys mixed with a fixed permutation of the whole block space is a valid block cipher design. But with a single "perfect" S-box and two sub-keys, you do not get your money worth of security (you get at most $2^{n/2}$ of a $n$-bit block). And since both the S-box and the key schedule cannot be "perfect", you have to add more rounds, and be very careful about the mathematical structures that you must necessarily employ. The current best-in-class design with that kind of structure is the AES, and it took many smart cryptographers and a lot of time to actually build some trust in its security.


Can I use guids / uuids as counters for key derivation? I have a 512 bit master key, and 128 bit unique identifiers.  I'm going to derive 256 bit keys to for use with deterministic and block ciphers.

For reference, The KDF I'm going to use is Hash( C | Z).

The implementation will be SHA256( uuid | master key).

I don't particularly care if SHA256 generates collisions as I never intend to store the derived key.

It think this will be fine, but would love a second opinion.

Yes, in practice this will be fine.

Expert cryptographers will give you grief and tell you that you should be using a PRF, and technically speaking, they will be right.  So, if you want to spare yourself from having that conversation, replace SHA256 with a PRF, such as AES-CMAC or SHA256-HMAC or PBKDF2 (using the master key as the key and the uuid as the seed).  This is the technically proper way to do it, and I'm thoroughly sympathetic with those who argue you should do it this way.

That said, even if you went ahead and used your original proposal (SHA256), you'd almost certainly be fine.  So, if I saw you using SHA256 instead of a PRF, I wouldn't get too worried about it.

P.S. I see a lot of confusion in the comments.  The following are not identical: PRF, MAC, HMAC.


For data shorter than 32 bytes, is it sure that no collision exists? I’m not talking about if a collision can be found but even simply exists.

The point is since it’s shorter than the length of the hash (since I’m talking about keccak256), normally there’s a hash value for each possible data. I mean in that case there’s more possible hash than possible values for input data.

So is the case ? Or by example, can 2 different 16 bytes long number share the same hash ?

I think what you're asking is:

  We know there certainly exist two 33-byte strings $m \ne m'$ such that $H(m) = H(m')$, when $H$ is (say) SHAKE128-256, because there are only $2^{256}$ distinct possible outputs of $H$ and $2^{262}$ distinct possible 33-byte messages.

  Do there exist two <32-byte strings, say 16-byte strings, $m \ne m'$ such that $H(m) = H(m')$?

Suppose the output of the hash function $H$ is $h$ bits long, and suppose the input is $t$ bits long.  If we model $H$ as a uniform random function, then each output for distinct messages $m_1, m_2, \dotsc, m_n$ is an independent random variable $H(m_1), H(m_2), \dotsc, H(m_n)$ with uniform distribution on the $h$-bit strings.  In this case, we are wondering whether there is any collision under $H$ in $n = 2^t$ distinct messages.

By the birthday paradox, the probability of a collision grows quadratically with the number of messages: it is at most $n^2\!/2^h = 2^{2t}\!/2^h$; of course, this bound is not very helpful if $t \geq h/2$, but the probability of a collision rapidly converges to $1$ as $t$ exceeds $h/2$.  So, there's roughly 50-50 odds that there's two 16-byte inputs that collide under (say) SHAKE128-256—but unless you find some amazing cryptanalysis of SHA-3, we'll never know what those two inputs are, if they exist at all.  The same goes for any other unbroken hash function of the same codomain, like SHA-256.


security in format preserving encryption In format preserving encryption an attacker knows the format and data type of the plain text. The format of the plain text and cipher text are same. usually cipher text are unreadable form. then how FPE is secure?what are all the possible attacks on FPE cipher?

Usually FPE is $Rank-LPE-DeRank$ Where LPE is length preserving encryption. The advantages of FPE schemes Preserving Formats and Lengths could be used against it too.

There are two attack vectors specific to FPE (but they are by design !)

Length Preserving
This might aide to brute force attacks if the domain is too small. For example encrypting an IP Address using FPE , the Cipher text is just $32$ bits, Where as encrypting with traditional AES would result in $128$ bits.

Inferences
FPE ciphers may reveal more inferences about the underlying data. For example encrypting an IP Address still looks like an IP Address, this leaks inference that the underlying  data types are.  An attacker getting access to encrypted logs might find it difficult to guess what the underlying data is if it looks random strings but if the encrypted logs have format preserving data this might leak the nature of the data is. One could argue this to be advantage too data that does not look random might not raise any suspicion etc.

It also depends on the over all system design what additional layers of security exist.

Also this particular paper[1] explains in much detail in theoretical jargon.

[1] http://arxiv.org/ftp/arxiv/papers/1506/1506.04113.pdf


What is the quantum-resistant signature scheme with the smallest signature + pubkey? After playing cat and mouse with an number of quantum-resistant signature schemes and coming up with nothing with small enough signatures, I'm turning to Crypto.SE. I need a quantum-resistant signature scheme with the smallest $signature || publickey$ that you can find. Private key size shouldn't really matter, can't I just use a CSRNG to generate a private key from a smaller seed?

Implementations are appreciated but not totally necessary. I'm hoping to get under 1000 bytes at least. Verification time is allowed to be in milliseconds, seconds sounds a bit exessive. Signing time could be up to 10 seconds, it's not the biggest issue. Also, it's fine if it's a one-time signature.

Some interesting reading:

https://en.wikipedia.org/wiki/Lamport_signature
https://gist.github.com/karlgluck/8412807/
http://tuprints.ulb.tu-darmstadt.de/1319/2/dissertation.dahmen.pdf

Choose some 128-bit hash function, such as RIPEMD-128, and a way of randomizing it, such as this.

The private key is either 60 uniformly random 128-bit strings s00,s01,...,s58,s59

and a uniformly random short salt or a seed to regenerate those. $\:$ For each i in

{00,01,...,58,59}, vi is the result of hashing si 19 times. $\:$ The public key is the

result of randomized-hashing v00 || v01 || ... || v58 || v59 with that salt.

To sign a message, the signer chooses a longer salt uniformly at random, computes the base-20 representation of the randomized hash of the message with the longer salt, and outputs

[[the two salts] and [for each j in {00,01,...,28,29}, the result of hashing s[2*j]

[19 minus the j-th digit of the base-20 representation] times and the result of

hashing s[(2*j)+1] [the j-th digit of the base-20 representation] times].

To verify a signature, the verifier computes the base-20 representation of the randomized-hash

of the message with the longer salt, [for each j in {00,01,...,28,29}, lets v[2*j] and

v[(2*j)+1] be the result of hashing the corresponding 128-bit parts of the signature [the j-th

digit of the base-20 representation] and [19 minus the j-th digit of the base-20 representation]

times respectively], and checks that the result of randomized-hashing

v00 || v01 || ... || v58 || v59 with the shorter salt is the public key.

If the length of the salts are fixed or can be efficiently computed from the sum of their lengths, then

the length of $\; signature \hspace{.04 in} || \hspace{.04 in} public\text{_}key \;$ will be $\;\;$ 7808 bits + the sum of the lengths of the salts.


Does CBC encryption of a hash provide authenticity? Given a message $M$ and a cryptographic hash function $H$, let $f(M) = E_K(M || H(M))$ where $E_K$ is AES-128-CBC encryption with PKCS#5 padding. Take $H = \textrm{SHA-256}$ if it matters. In other words, we encrypt the message and a hash of the message, with CBC.

Does $f$ guarantee the authenticity of the message? (Assume the adversary doesn't know the secret key $K$, of course.)

CBC doesn't provide any authenticity, but changing any bit of the ciphertext completely changes the decryption of the block, which should prevent the adversary from computing the hash of the modified plaintext. Is this right? Does this scheme provide authenticity if the IV isn't reused? If the IV is reused, I get the feeling that there are cases where the adversary can mix parts of the two messages.

 Don't worry, I am not planning on doing that. If I need authenticated encryption, I'll use a proper mode such as EAX or GCM.

No, the scheme described in the question does not provide integrity.

A forgery is possible when the message's size is allowed to vary (which is presumably the case since some padding is used), and the adversary can choose some segment of the message with knowledge of the message before that segment. That is, a message $M=M_b||M_c||M_d$ with the beginning $M_b$ of the message known, and chosen $M_c$.

The adversary chooses any $M_x$ she wants, computes $$M_c=M_x||H(M_b||M_x)||\operatorname{Padding}(M_b||M_x||H(M_b||M_x))$$
then let the legitimate sender do his job, which will produce the ciphertext $E_K(M||H(M))$ with $M$ starting in $M_b||M_c$. Notice that by construction, $M_b||M_c$ is block-aligned, and padded so that removal of the padding will leave $M_b||M_x||H(M_b||M_x)$. Now the adversary truncates the ciphertext after that block, and has a forgery that is accepted as the ciphertext for $M_b||M_x$.

Underlying problem: the same key is used for confidentiality and integrity.

Example where this would matter: The message $M=M_b||M_c||M_d$ is a program. $M_b$ is a header imposed by the operating system. The process of producing a program normally produces $M_b||M_d$ where execution starts after $M_b$ thus at the beginning of $M_d$, but the adversary has modified this process to produce $M_b||M_c||M_d$, so that execution starts at $M_c$, thus at $M_x$ which is under full control by the adversary. When executed, $M_x$ examines if $M_d$ is present, if yes executes $M_d$, else performs some nefarious action. The legitimate user produces a program $M$, checks that it performs normally (perhaps using some executable analysis tool that concludes $M_c$ will always jump at $M_d$ and disregard analysis of the rest of $M_c$), then authenticates and enciphers it into a cryptogram. Problem is: it is enough to truncate that cryptogram to produce an acceptable cryptogram which carries $M_b||M_x$, which is happily executed by the operating system but performs some nefarious action.

Note: The stated conditions are sufficient for the attack, but not necessary. For example, when $H=\operatorname{SHA-256}$, an attack can be carried if the adversary can choose some segment $M_c$ of the message with knowledge of the hash and length of the portion of the message before $M_c$.

Nitpick: It is meant PKCS#7 padding, for PKCS#5 padding applies only to 8-byte blocks.


How come “short” (eg 80 bit) MACs are regarded to be safe? I‘ve got two questions:

Why are much shorter output lengths of, e.g 80 bits, sufficient for MACs ?
Assume  a message $x$ that is sent in clear together with its MAC over the channel: $(x,MAC_k(x))$. What does Oscar have to do to attack this system?

I think I can answer the first question: it’s because of the Birthday Paradox
But for the second, I don´t know how to start. It’s not given how the MAC is calculated. I could do a secret pre- or suffix attack ?

But for the second, I don´t know how to start.

I won't give you the answer (this is homework; you won't learn as much if I just give you the answer); I will give you hints.

  It’s not given how the MAC is calculated.

No, but for this question, we assume that the attacker knows what the MAC is; he just doesn't know the key.  We also assume that he knows the correct MAC for a number of different messages (actually, we assume that the attacker can ask for a MAC for messages of his choosing; that ability won't help you in this attack).

What does that mean?  Well, it means that, for the purpose of this question, we treat the MAC as a black box; the attacker can (to his heart's content, up to the limits of the computational resources he has on hand) generate keys and messages and compute what the MAC would be for that key.

So, with those capabilities, our attacker's job is to get a (message, MAC) pair accepted, for a message he hasn't seen (he's not allowed to submit one of the (message, MAC) pairs he's already been given).  How can he do that?

Hint: there are two basic ways the attacker can proceed; one involves his use of the black box, and one does not.


PRNG taking advantage of very large seed Can anyone suggest a good (CS)PRNG algorithm that takes advantage of having a very large (ideally arbitrarily large) seed? I'd like to use several kilobytes, perhaps several hundred kilobytes, of random data to generate up to a few dozen megabytes of PRNG output. The PRNG algorithms I'm aware of only take relatively small seeds: I'd like to make the most of the random input data I have.

The PRNG proposed by Barak and Halevi should be able to meet your needs and provide sufficient security.

Their PRNG has an API of next and refresh. refresh takes an arbitrarily long string and uses it to update the internal state of the PRNG. next returns some number of random bytes (if more is needed, one can simply call next in succession).

They prove some very nice properties of their PRNG (which together define robustness of a PRNG), and give a concrete implementation.

The entire paper is definitely worth a read.


Simulator in Private Outsourced Computation over Outsourced Datasets Please, consider two honest parties $A$ and $B$ outsourced their private data to a malicious server $S$. So the parties store their data in the server. Then at a later point in time they want to ask the server to run some computation on both parties data and return a private result back to a party.

In order to prove the security of the scheme,in the ideal world, we construct a simulator $SIM_s$ simulating malicious server, $A_s$.

Question: Does $SIM_s$, pick two random datasets, make them private and send to  $A_s$?

What is not clear in this case is that whether the parties (or simulator) have input or the server has input. Because the parties have already outsourced their dataset.

The objective of the simulator is to make the simulated world (often called the ideal world) indistinguishable from the real world (running the actual protocol). See my write-up on the UC framework here for more detail.

In the proof setup, the entity attempting to distinguish between the two worlds is often assumed to provide the inputs to the parties. That keeps things as generic as possible.

So, what should be done is have $\mathcal{Z}$ pick the inputs for the parties.


Performing a dictionary attack on RSA/ECB with no padding I have the exponent $e=2^{16}+1$ and modulus $n$ (154 digit number) of an RSA public key along with the ciphertext (64 bytes) encrypted using the same key with RSA/ECB and no padding.

I am required to decrypt the ciphertext and have two options:-

Find the prime factors of $n$, $p$ and $q$, to determine the private key which can then be used for decryption, or
Use a dictionary attack (~135k words)

The first option does not seem feasible to me considering how big the modulus is and so I think the second option is more likely.

My question then is, where would I begin with a dictionary attack on the above cipher text? My initial idea is to iterate through every word in the dictionary, encrypt it using the public key above and check to see if the cipher text contains the result, but words in the dictionary have lengths up to 30 so this would definitely take a while.

If the public modulus was generated properly, option 2 (brute force dictionary search of candidate plaintext) will be faster. Option 1 (factoring a ≈512-bit RSA integer) is feasible, but can be quite compute-intensive even with the best known algorithm (GNFS). On the other hand, if random padding was used (as it should, and would be in any good practice), option 2 would not be feasible.

First things are to determine how exactly a dictionary word would be encrypted, including formatting of the ciphertext.

I think Python 3 might be acceptably fast just checking if pow(m,e,n)==c where m varies over the plaintexts appropriately converted to integer as in the encrption, and c is the ciphertext appropriately converted back to integer. For (perhaps only slightly) better speed, write a compiled program using GMP.


SAT-Based Public Key Cryptosystem I am researching post quantum cryptography and I've stumbled upon this article which presents a PKC with an np-complete (SAT) trapdoor.

I was wondering if someone could help me understand the way the encryption works. From what I understand the cipher text is a formula which consist of a bit (the message) which is then xored with variables taken from the public key. Doesn't it mean that the bit is actually in "plain sight" inside the cipher text ?

Surely I am missing something.

There are known impossibility results regarding basis public-key cryptography on NP-complete problems. In this paper by Goldreich and Goldwasser they show that under common types of reductions, it is not possible to base public-key cryptography on NP-hardness.


El Gamal existential forgery using Pointcheval–Stern signature algorithm I found that there exists an algorithm that claims to make the El Gamal signature generation more secure. The algorithm can be found here as a pdf.

I'm mainly interested in the two-parameter forgery that goes as the following:

Let $1 < e,v < p-1$ be random elements and $gcd (v,p-1)=1$. If $r = g^e \cdot y^v  \bmod{p}$ and $s = -r \cdot v^{-1} \bmod{p-1}$, the tuple $(r,s)$ is a valid signature for the message $m = e \cdot s  \bmod{p-1}$.

My question is how does this work? Is there a well explained proof?

The scheme you consider is the original ElGamal signature.  This scheme is known to be existentially forgeable.

By definition, a valid original ElGamal signature on a message $m \in \{1, \dots, p-1\}$ is a pair $(r,s)$ satisfying $g^m \equiv y^r \cdot r^s \pmod p$.

With $r = g^e \cdot y^v \bmod p$ and $s = -r\cdot v^{-1} \bmod (p-1)$ for random integers $e$ and $v$ the pair $(r,s)$ is a valid signature on message $m = e \cdot s \bmod (p-1)$. To see it, you must check that $g^m \equiv y^r \cdot r^s \pmod p$:

For $m = e \cdot s \bmod (p-1)$, we have $g^m \equiv g^{e\cdot s} \pmod p$;
With $r = g^e \cdot y^v \bmod p$ and $s = -r\cdot v^{-1} \bmod (p-1)$, we have $y^r \cdot r^s \equiv y^r \cdot (g^e \cdot y^v)^s \equiv y^{r+v\cdot s}\cdot g^{e\cdot s} \equiv y^{r+v\cdot (-r\cdot v^{-1})}\cdot g^{e\cdot s} \equiv y^0 \cdot g^{e\cdot s} \equiv g^{e\cdot s} \pmod p$.

Since the two sides are equal modulo $p$, the signature is valid. Q.E.D.


Scenario for applying power analysis I have started doing some reading about power analysis (SPA, DPA), and it is not clear to me in what Scenario one would have to fear such an attack.  It appears to me that a typical situation is

Scenario A: A key is stored in plain text on a smart card, the analysis is conducted while encryption/decryption request are sent to the card and in effect the key is obtained.

However I am more interested in

Scenario B: A key is stored encrypted on a device (smart card?). During normal operation one would send the passphrase (required for decrypting the key) together with an encryption/decryption request to be performed by the decrypted key. Now the assumption is that an attacker does not posses the passphrase.

Would it still be possible to obtain the passphrase by power analysis?
(From my imagination the only thing one could do is feeding wrong passphrases.) From my understanding scenario B is not susceptible to power analysis, or am I wrong?

This seems to be correct.

I do see one possible attack vector where repetition of the request could be used for DPA attacks on the decryption key. It is basically the plaintext when looking at the decryption using the passphrase. It is also the encryption / decryption key for the subsequent operation using the key. But that's a scenario that is less likely than an attacker holding the smart card and trying to use DPA to retrieve an encryption key.

If you send the password in plaintext then you should of course consider the security of the password before it actually reaches the smart card. DPA attacks are not interesting if the adversary can simply eavesdrop on an unprotected password.


Encrypted read-only message queue I'm creating a prototype for a messaging queue with some custom logic (can't re-use any existing solution).

One requirement is to have all messages encrypted. There are three classes of nodes subscribing to the queue with the following permissions:

Read/Write access
Read-only access
Buffer/forwarder with no access to the message content

The first and obvious thought was to use an RSA private key for group 1. This would allow to encrypt with the private key and decrypt with the public key.

Group 2 would receive the corresponding public key and would be able to only decrypt the content.

Group 3 would have no key and just handles the messages without access to the content.

After doing some further reading, there seem to be a number of problems with this approach (apart from the simple fact that the keys are used in "reverse" in relation to the intended mechanism).

Now the question: Is there some common approach to get this pattern to work? I have searched, but so far have not found anything.

I will have access to someone with more experience in this matter at a later point, but for purposes of the prototype, I just want to get something done that won't make me look like an idiot later. ;-)

If you aren't worried about collusion or dynamic group membership, then a very simple solution is to simply have one key for encrypting the messages and another for signing them.  The encryption key gives someone read access and the signing key gives them write access.  Only nodes with the encryption key will be able to successfully decrypt the messages and read them, and only nodes with the signing key will be able to produce "valid" messages that have correct signatures.  The encryption key would be a symmetric key and the signing key would be a private key.  Everyone would have access to the public key to verify that messages were constructed by an authorized node.

If you need more complicated logic or a more flexible system, you can use cryptographic role-based access control, which usually makes use of attribute-based encryption.  But that solution will be very, very complicated.


Random unique key per message, safe to use key as IV? The overall setup is that I am using RSA public key encryption, and because the messages are big instead of encrypting the entire message via RSA I am encrypting a random AES-128 key with the PK and then encrypting the message with that in AES-CBC.

The AES key is randomly generated for each message. Questions:

Is it safe to use the key as the IV of the CBC? The rationale here is the key is unique and random for each message and I'm not seeing a problem. The key is used in 3 places thus: the encryption itself, then as an IV, then again concatenated with the encrypted message's hash and everything hashed again as a MAC.
Do I still need to do any random padding on the IM itself? The key and IV are already unique and random.

Is it safe to use the key as the IV of the CBC?

CodesInChaos has answered this sufficiently in the Q&A he linked (AES key equal to IV (CBC mode)) and the TL;DR is: It's risky, but not directly exploitable.

  Do I still need to do any random padding on the IM itself?

Hybrid encryption modes generally don't need random message padding as the randomness is already encapsulated in the key.

Now for some other issues with your scheme:

You're using concatenation and hashing as the MAC. More precisely your MAC construction is $\tau=H(H(M)\parallel K)$ is potentially broken.
You're using CBC. Using CBC in newly deployed system is highly discouraged, especially due to padding oracle attacks and the likes which are only an issue in block-based encryption modes.
You're not using AEAD. Rolling your own mode of encryption and authentication is dangerous without proper knowledge and formal security reductions. Using a proper mode like GCM, OCB or EAX is really recommended and will ease implementation and use proven-secure constructions.
Your RSA encryption is probably risky to say the least. If I'm reading your question right you may be using straight, textbook RSA encryption of the 128-bit secret. However this is highly susceptible to brute-force attacks which can recover this secret in roughly $2^{64}$ steps.


Public key derivation for Ed448 Another potentially silly question here, but I seem to have developed tunnel vision and I am missing something very basic.
In RFC 8032 one can find a number of test vectors for Ed488 - for example:
SECRET KEY:
   c4eab05d357007c632f3dbb48489924d
   552b08fe0c353a0d4a1f00acda2c463a
   fbea67c5e8d2877c5e3bc397a659949e
   f8021e954e0a12274e

   PUBLIC KEY:
   43ba28f430cdff456ae531545f7ecd0a
   c834a55d9358c0372bfa0c6c6798c086
   6aea01eb00742802b8438ea4cb82169c
   235160627b4c3a9480

   MESSAGE (length 1 byte):
   03

   SIGNATURE:
   26b8f91727bd62897af15e41eb43c377
   efb9c610d48f2335cb0bd0087810f435
   2541b143c4b981b7e18f62de8ccdf633
   fc1bf037ab7cd779805e0dbcc0aae1cb
   cee1afb2e027df36bc04dcecbf154336
   c19f0af7e0a6472905e799f1953d2a0f
   f3348ab21aa4adafd1d234441cf807c0
   3a00

The public key, in the encoded format, is 57 bytes in size. Now my understanding is that the public key is obtained by computing the scalar product of the private key (encoded as described in RFC 8032) times the base point. The operations are to be carried out mod the prime p = 2^448 - 2^224 - 1, which is 56 bytes long.
How can the public key be 57 bytes long, if all the operations are mod a 56 bytes long quantity? It is true that the public key is not directly the scalar product above, for this product has to be encoded as described in RFC 8032. However, this encoding is very straightforward, and can't add an extra byte.
I must be missing something very obvious here - but I can't see what it is.

If you read all of the RF 8032 you will see that there is a compression (endcodings) of the points.
def point_compress(P):
    zinv = modp_inv(P[2])
    x = P[0] * zinv % p
    y = P[1] * zinv % p
    return int.to_bytes(y | ((x & 1) << 255), 32, "little")

Compression just stores the sign and restores it back with this information
def point_decompress(s):
    if len(s) != 32:
        raise Exception("Invalid input length for decompression")
    y = int.from_bytes(s, "little")
    sign = y >> 255
    y &= (1 << 255) - 1

    x = recover_x(y, sign)
    if x is None:
        return None
    else:
        return (x, y, 1, x*y % p)

The above has been defined for Ed25519, there is no code for Ed448 in the RFCs as I can see. However NIST.FIPS.186-5-draft defined it for both;

For a curve point $(x,y)$ with coordinates in the range $0 \leq x, y < p,$ first encode the $y$-coordinate as
a little-endian string of 32 octets for Ed25519 or 57 octets for Ed448. For Ed25519, the most significant bit of the final octet is always zero, while for Ed448, the final octet is always zero. To
form the encoding of the point, copy the least significant bit of the x-coordinate to the most significant bit of the final octet

As we can see, the LSB of the $x$-coordinate is placed in the MSB of the final octet (byte) of the $y$ coordinate. Therefore, the total size of the public-key is 57 bytes.
Although the compression has a time-consuming and little advantage on the storage/transmission it also helps in the point validation. The second and third options are verified during decompression.

The $x$ and $y$ coordinates of $P$, $x(P),y(P)$ are valid elements of the field.
$P$ satisfies the curve equation - against the twist attack.


Why does HMAC need a fixed length padding? As everybody knows in order to calculate HMAC we have to concatenate padding to the message. I am just curious why the padding needs to be fixed-length. Why do we need the blocksize parameter here?

Why not use an arbitrary length key with arbitrary length 0x5c5c5c…5c, 0x363636…36?

Why do we need to truncate the key when it is larger than the blocksize?

In HMAC, the key $K$ [after it has been replaced by $H(K)$ if $K$ was wider than the hash's internal block size] is padded with zeros to the hash's internal block size. The question asks why this padding.

In a nutshell: the security argument of HMAC would not hold without that.

HMAC's original and improved security arguments make heavy use of the Merkle–Damgård internal structure of the hash, that is:
$$\begin{align}
H_0&=\text{IV}&\text{ initialization with a public constant}\\
H_{i+1}&=F(H_i,B_i)&\text{ process }n\text{ padded blocks with the round function }F\\
\text{output}&=H_n&\text{ final result}
\end{align}$$
Heavily simplified, a central requirement of the proof is that during the first of the two hashes in HMAC, if the adversary knows nothing ultimately exploitable about $H_i$, then even though she might know and be able to manipulate $B_i$, she will know nothing ultimately exploitable about $H_{i+1}$. The padding performed on $K$ is such that $K$ maps (within XOR with constant ipad) exactly to $B_0$, and that is enough to insure that the adversary knows nothing ultimately exploitable about $H_1$; that bootstraps the proof by induction that the adversary knows nothing ultimately exploitable about any $H_i$ for $i>0$, hence knows nothing ultimately exploitable about the output of the first hash in HMAC. By contrast, without padding, the adversary would be able to manipulate in part $B_0$, which is mixed by $F$ with the known $H_0$, and we'd have no bootstrap of the security argument.

The second hash in HMAC transforms said nothing ultimately exploitable about the output of the first hash into an overall HMAC output which is indistinguishable from random; again the proof uses that the adversary does not know the other input $H_1$ of the function $F$ that receives the first hash's output, since that is entirely within $B_1$, thanks to the padding of $K$.

When the key $K$ is larger than a block, HMAC replaces it with its hash. Keeping the key as is, unpadded, would not be satisfactory for the same reason as above: we'd have no security argument (e.g. for 64-byte block size, 20-byte hash size, 84-byte key of which the first 64 bytes are zero).

I think padding with zeros to the next block would provide adequate security. But compared to that option, replacing the key with its hash:

leaves the security argument unchanged (it aims at the security level of the hash width, which is about that of the hashed key substituted to the original);
decreases the computational complexity of processing long keys by a factor of 2 (asymptotically);
only ever increases the number of internal hash rounds (and then only by 1 round out of at least 6) for a narrow range of key size (for SHA-1 and SHA-256: 120 to 128 bytes).


How many possible input files are there who's length can be stored in 63-bits? I'm trying to calculate how many possible combinations of files there can be using a signed 64-bit file length, but can't seem to find a formula (or I'm using the wrong keywords). For example, the number of unique files that have a length of 256 bytes is $2^{256*8}$ = $2^{2048}$. I assume the total number of combinations across all file lengths will be some kind of geometric sequence?

The reason I want to calculate it is because I'm curious how it relates to the number of possible SHA-256 hashes ($2^{256}$). Also, if I calculate the SHA-256 hash of the SHA-256 hash of a file's contents, how much have I reduced the entropy (if that's the correct term)?

For a given file length L bytes the combinations for that length is 256^L. The total combination is the sum of combinations for all file lengths L from zero to (2^63)-1. Just substitute parameters in the formula for summing the n first terms of a geometric series. The rest is left as an exercise to the reader :-)

If all you need is a rough order-of-magnitude estimate it is really sufficient to just look at the highest order term, which provides a quick lower-bound estimate and which will already tells you the ratio is a very large number (very large for cryptographic purposes), which means the factor you have "reduced entropy" is a number very close to zero (once again, for cryptographic purposes).


Factoring large numbers I am trying to factor few integers that are each between 115 and 135 digits long. I was wondering if anyone knew of any efficient methods or any programs that I could use to find the two primes $p$ and $q$ for $n=pq$.

I was thinking of using quadratic sieve but I don't know if there is any other way. Plus I don't know how I would write the algorithm on any program. Any input is much appreciated.

As for the algorithm, you have two choices: The quadratic sieve and the general number field sieve.

If you want to implement the factorization yourself you want to use the quadratic sieve, as a good implementation of the GNFS is really hard.

However, if you're willing to use pre-made tools using GGNFS and msieve (together) is your best option. Msieve provides good polynomial selection (first step) and GGNFS provides the efficient second step, while msieve takes over the last step, you may want to refer to this guide for the exact how-to.


What if the hash code of the genesis block (first block in the block chain) is changed? If so, what would happen? And if not, what are some limitations to it? The reason I am asking is because I just started getting into the cryptocurrency and am very interested in the cybersecurity aspect of it. Also, it's important to mention I don't have much experience in either but am willing to learn. Could someone advise some books/articles/guides? Greatly appreciated!

The genesis block is embedded in the chainblock (the hash of all the transactions since the bitcoin network was powered on).
Now, from your question I deduce that you know little about cryptography and in particular hash functions and the blockchain protocol so I will try to explain myself in the simplest (and obviously incomplete) way possible:

Blockchain can be corrupted only if the majority of the network work to corrupt it, this is the (in)famous 51% attack.
If I modify the hash on my client, this change does not involve anything on the network as 99.999% of clients have a different version of the hash (the correct one) and the majority is the authentic. This is one of the main strenghts of the blockchain: the fact that it is decentralized and that transactions must necessarily be accepted and registered by multiple clients (at least 51%) to be verified. Very democratic isn't it?

In any case, I believe it is a good thing that you want to inform yourself about how the protocol works before throwing into trading. Many (too many) people invest in bitcoins or other crypto without even knowing what they are ... after all, when you invest in a cryptocurrency, you should do it because you believe in the potential of the protocol that supports it and not just for fashion or to make (or lose) money.

If you want to know more about bitcoin, the starting point could be to learn some basic cryptography, especially Hash: Section 8 for Hashing functions.
         Once you have become familiar with these concepts, I suggest you read the original publication in which Satoshi Nakamoto (we dont know who he/she/them is/are) illustrates the bitcoin protocol:
a milestone of our time.


Strength of CBC with Ciphertext Stealing Is CBC with Ciphertext Stealing (CTS) considerably weaker than CBC with padding such as PKCS7?

I would imagine the most common situation where CTS is necessary would be due to some size constraint of an existing system, and redesign of the system is inconvenient. So, while it clearly reveals the length of the encrypted data, (in general) is this a significant enough weakness such that CTS should always be avoided?

I've read through the addendum to NIST SP800 38A on CTS variants, and while one could perhaps take this NIST recommendation as tacit approval of CTS's relative safety, there's no real mention of any weakness considerations and I've not been able to find any resources speaking directly to this topic.

In their 2012 paper "The Security of Ciphertext Stealing", Phillip Rogaway, Mark Wooding and Haibin Zhang prove that all the NIST-approved ciphertext stealing modes provide the same level of security as ordinary CBC mode, i.e. ciphertext indistinguishability under a chosen-plaintext attack.  To quote their abstract:

  "Abstract. We prove the security of CBC encryption with ciphertext stealing. Our results cover all versions of ciphertext stealing recently recommended by NIST. The complexity assumption is that the underlying blockcipher is a good PRP, and the security notion achieved is the strongest one commonly considered for chosen-plaintext attacks, indistinguishability from random bits (ind\$-security). We go on to generalize these results to show that, when intermediate outputs are slightly delayed, one achieves ind\$-security in the sense of an online encryption scheme, a notion we formalize that focuses on what is delivered across an online API, generalizing prior notions of blockwise-adaptive attacks. Finally, we pair our positive results with the observation that the version of ciphertext stealing described in Meyer and Matyas's well-known book (1982) is not secure."

In particular, in section 3 of the paper, the authors write:

  "Turning now to the CBC-CS modes, we claim that these inherit CBC's security
  with no quantitative degradation. The needed observation is that $\text{CBC-CS1}^{IV}_K(P)$
  is just $\text{CBC}^{IV}_K(P\ 0^∗)$ (minimal padding to the next multiple of $b$ bits) with some bits excised and some bits reordered. Which bits are excised and how bits are rearranged depends only on $|P|$. Thus if $\text{CBC}^{IV}_K(·)$ looks random, so too will look $\text{CBC-CS1}^{IV}_K(·)$. The same comments hold for CBC-CS2 and CBC-CS3; these are
  just diﬀerent rearrangements of the bits of $\text{CBC}^{IV}_K(P\ 0^∗)$. The observation and proof are formalized by the proposition below."

Edit: It should be noted that all these indistiguishability results assume that the length of the plaintext (and corresponding ciphertext) is fixed and known to the attacker.  If used to encrypt variable-length messages, all the commonly used block cipher modes of operation leak information about the length of the plaintext.

As you correctly note, CBC mode without ciphertext stealing does leak slightly less information about the plaintext length than other modes (like CFB, OFB, CTR or CBC-CS), since in traditional CBC mode the message is padded to the next multiple of the cipher block size (usually 8 or 16 bytes).  However, this incidental side effect isn't really something you should generally rely on to conceal your plaintext lengths, at least unless you can be sure that just knowing whether or not, say, a message is less than 16 bytes long won't ever be the critical piece of information the attacker is looking for.  Instead, if you do care about concealing the length of the plaintext, you should pad your messages yourself to some fixed length before encrypting them.


Paillier cryptosystem preserve ordering of sums for two integer sequences According to Paillier cryptosystem the product of two ciphertexts will decrypt to the sum of their corresponding plaintexts.

I have two separate integer sequences X and Y that have same number of values. I want to calculate the 1-1 combination that minimizes the sum (e.g, x1+y1 IF and ONLY IF x1+y1 <= x2+y2 AND x1+y1 <= x3+y3)

Original Data:

X: {x1,x2,x3}
Y: {y1,y2,y3}

I then Paillier encrypt the X sequence with public key r1 and the Y sequence with public key r2.

Encrypted Data:

X: {E(x1),E(x2),E(x3)} (with public key r1)
Y: {E(y1),E(y2),E(y3)} (with public key r2)

If E(x) the cyphertext for message x, then I can calculate E(x1)E(y1), E(x2)E(y2),E(x3)E(y3), decrypt them and then get the correct minimum result x1+x2.

If indeed x1+y1 <= x2+y2 AND x1+y1 <= x3+y3 does the Pailler encryption guarantees that also E(x1)E(y1) <= E(x2)E(y2) AND E(x1)E(y1) <= E(x3)E(y3). My intuition is that NO, because that would also mean that if x<y then E(x)<E(y) for the same r.

Is my understanding correct, that Paillier cryptosystem despite its homomorphic properties cannot preserve ordering of sums for the two sets X and Y when X set is encrypted by r1 and Y set is encrypted by r2? Is there any other cryptosystem that can support this?

Paillier is not order preserving, so in your algorithm $x_1+y_1$ IF and ONLY IF $x_1+y_1 <= x_2+y_2 \dots$ simply does not work. You can't do the $\leq$ comparison.

Whether you have the same $r$ or not does not really matter, if we look at the encryption:

$E(m)= g^m r^n$ mod $n^2$

You could try to achieve that by fixing $r^n$ such that the product with $x$ doesn't surpass $n^2$ (and thus isn't reduced any further by the modulus), but that means you have to find $r$ so that $r^n$ is quite low, and then your entire security will go down in flames most likely.


In the page $104$ you can see:
$$F_{2^8}=\frac{Z_2[x]}{x^8+x^4+x^3+x+1}.$$
this means that irreducible polynomial that generate the $F_{2^8}$ is $x^8+x^4+x^3+x+1$. so, in multiplications, you should note that $x^8=-x^4-x^3-x-1=x^4+x^3+x+1$. Therefore $x^{8+i}=x^8\cdot x^i=x^{4+i}+x^{3+i}+x^{1+i}+x^i$.


Attack RSA knowing the public key and brute forcing all possible message Alice want to send a message $m$ to Bob, and encrypt it with Bob public key $K_B$.

$A \rightarrow B : \{m\}K_B$

Lets assume I have intercepted $\{m\}K_B$, I know $K_B$ and I know that $m \in D$ (Alice message belong to a relative small dictionary called $D$ )

By brute force attack, can I got through all  $x \in D$ so that I find $\{x\}K_B = \{m\}K_B$ ?

If textbook RSA is used then many attacks are possible, including dictionary attacks. This is because the value that is used in modular exponentiation (called RSAEP in the standard) is just the input decoded to a number. However, plaintext RSA is susceptible to many attacks and is not considered secure; a rather obvious one is when a message with value 0 or 1 is encrypted, as the output would be 0 or 1 as well; no attacks necessary.

Normally however a secure padding method is used. The original scheme from RSA labs was PKCS#1 v1.5 padding. This padding "wraps" the message and includes many random bits that are encrypted together with the message. These bits are not know to an attacker. They can be used to check that the decryption was successful or not. The later padding method OAEP, which is provable secure, should however be used as PKCS#1 v1.5 is vulnerable to attacks on the unpadding of the message. OAEP, just like v1.5 padding, uses random bits.

PKCS#1 reads for OAEP "Generate a random octet string seed of length hLen" where hLen is the hash function used within MGF-1, often SHA-1. That means that hLen is at least 160 bits. That means that 160 bits of randomness are encrypted together with the message. It's at least 63.95 bits for PKCS#1 v1.5 padding but usually it is more (the amount of padding depends on the difference between key and message size).

So no, you cannot use dictionary attacks because the output of the RSA encryption will always be different from the given message - if a secure padding is used. However, if for some reason the random number generator fails and leaks the not-so-random bits then you could match the padding, and perform a dictionary attack.


What place do prime numbers have in cryptography? My understanding of hashing and encryption is rather limited. I certainly do not understand the mathematical formulas at play in these algorithms. With that said, what part do prime numbers play in cryptography?

When I was in college, one of my professors told me that the fact that there is no formula to predict a prime number (other than just trying them) is what makes many encryption schemes (like PGP) so secure, since it's not possible to guess the number used for the public/private key in any reasonable amount of time. Is that correct?

No, the fact that there's no known practical formula that produces only prime numbers doesn't really come into play; if someone found one tomorrow, that wouldn't have any cryptographical implications.

You may want to go through the How does asymmetric encryption work? thread; the short answer is that for public key operations, the public and the private keys must be related, but not in an obvious way.  What means that whatever scheme is used has some mathematical structure.  Number theory is a place where we find 'related-but-not-in-an-obvious-way' mathematical structures, and primes are rather, err, primary in number theory.

Exactly how the primes are used depends on which asymmetric algorithm is used; in RSA, we exploit the fact that, given $M^e \mod N$ (and $e$ and $N$), there's no known way to recover $M$ without knowing the prime factors of $N$ (but with that information, it's easy).  In DH/DSS, we exploit the fact that, given $G^x \mod p$ (and $G$ and $p$), there's no known way to recover $x$ (and we have $p$ be a prime because the problem with composite moduli becomes a lot easier if someone finds the factorization).  In Elliptic Curve Cryptography, we exploit the difficulty of recovery $k$ given $kG$ (where $G$ is a known point); a prime is involved because Elliptic Curves are defined only a field, and the only finite fields (that is, fields with a bounded set of elements) have size $p^N$, for prime $p$ (and positive integer $N$).

Now, you occasionally see primes used in symmetric crypto; it's not nearly as common (and those primes aren't secret).


How the message is decrypted in an RSA chosen ciphertext attack when it's a modulo? During the last stage of decryption of a chosen ciphertext attack we are left off with this equation
$$c = m \cdot t \pmod n$$
Removing all exponents like $d$ and $e$ where $c$ is the decrypted message which (doesn't mean anything), $t$ is the message we multiplied original ciphertext with, $m$ is the message we want.
If we substitute with value like these after decryption $c=2$, $t=2$, $n=5$ for example, we get:
$$2 = (m \cdot 2) \pmod 5$$
But here $m$ can be many different values. It can be 6 or it can
be 11: $(6*2) \bmod 5 = 2$. I mean it's a clock so many options for $m$ would give same decrypted ciphertext output.

In a chosen ciphertext attack, it is hypothesized that the adversary can obtain the decryption of cryptograms chosen by the adversary other than the targeted one(s), and in addition obtain the encryption of any message chosen by the adversary (which is free for asymmetric encryption).
The most general CCA experiment goes:

Key generation: the challenger secretly draws a key, and reveals the public key if any (that is for asymmetric encryption)
Message choice and encryption:

the adversary chooses messages $m_0$ and $m_1$ and submits both to the challenger
the challenger randomly draws $b\in\{0,1\}$
the challenger verify that both $m_0$ and $m_1$ are valid (could be encrypted), and if that holds encrypts $m_b$ yielding $c_b$, sets $c=c_b$, and reveals $c$ (unrelated to the question's $c\,$).

Interaction: the challenger accepts and answers both encryption and decryption queries, with the exception of decryption queries which ciphertext matches $c$.
Examination: the adversary makes a guess of $b$. The cryptosystem is broken under chosen ciphertext attack when the guess is correct for probability non-vanishingly better than $1/2$.

For asymmetric encryption, the challenger needs not answer encryption queries, for these can trivially be handled by the adversary using the public key.
No deterministic encryption can be CCA secure per this definition (argument: the adversary can get $c_0$ and $c_1$ and determine which matches $c$). For a weaker notion of CCA security applicable to deterministic encryption, another change is imperative. That can be:

The challenger does not answer decryption queries where the ciphertext submitted matches matches one of $c_0$ or $c_1$ (the challenger needs to compute both).
Alternatively, only the challenger is involved in the message choice, which becomes selecting $m$ such that encrypting it into $c$ succeeds. And in examination the adversary makes a guess of $m$, not $b$. And must guess correctly with non-vanishing probability.

The question is for textbook RSA, which is asymmetric and deterministic. With the second of the above options, and a single decryption query, the experiment goes:

Key generation: the challenger

draws a key pair
reveals the public key $(n,e)$
keeps secret the private exponent $d$
Note: $(n,e,d)$ is such that messages $m$ that can be encrypted are those integers with $0\le m<n$; their corresponding encryption is per $c\gets m^e\bmod n$, and decryption of $c$ with $0\le c<n$ is per $m\gets c^d\bmod n$ or equivalent.

Message choice and encryption: the challenger

randomly draws an integer $m\in[0,n)$
computes $c\gets m^e\bmod n$
reveals $c$ (unrelated to the question's $c\,$).

Interaction: the challenger accepts a chosen ciphertext query where it

receives $\tilde c$ (the chosen ciphertext) submitted by the adversary
checks $0\le \tilde c<n$ and $\tilde c\ne c$
checks and deciphers $\tilde c$, that is checks $0\le \tilde c<n$ then in the affirmative computes and reveals $\tilde m={\tilde c}^d\bmod n$ (this $\tilde m$ is the question's $c\,$).

Examination: the adversary makes a guess of $m$. The cryptosystem is broken under chosen ciphertext attack when the guess is correct for non-vanishing probability.

A standard way to carry this attack in textbook RSA is that the adversary

chooses some $t$ in $[2,n)$ with $\gcd(t,n)=1$, e.g. $t=2$ or $t=n-1$
computes $s=t^e\bmod n$
computes and submits $\tilde c=c\cdot s\bmod n$
obtains $\tilde m$ from the challenger
Note: from $\tilde c=c\cdot s\bmod n$ it follows ${\tilde c}^d\equiv(c\cdot s)^d\pmod n$ (obtained by raising to the exponent $d$), thus ${\tilde c}^d\equiv c^d\cdot s^d\pmod n$, thus $\tilde m\equiv m\cdot(t^e)^d\pmod n$ (since decryption works for $m$ and $\tilde m$), thus $\tilde m\equiv m\cdot t\pmod n$ (since decryption works for $t$).
solves for $m$ with $0\le m<n$ the equation $\tilde m\equiv m\cdot t\pmod n$ (which in the question is the equation $c = m \cdot t \pmod n\,$), and submits the result as the recovered $m$.

In that later step, the adversary computes a multiplicative inverse of $t$ modulo $n$, that is some integer $t'$ such that $t\cdot t'\equiv1\pmod n$. This is possible since $\gcd(t,n)=1$. One method uses the extended Euclidean algorithm. When $t=2$ (resp. $t=n-1\,$), we can use  $t'=(n+1)/2$ (resp. $t'=n-1\,$).
Then $\tilde m\equiv m\cdot t\pmod n$ becomes $\tilde m\cdot t'\equiv(m\cdot t)\cdot t'\pmod n$, thus $\tilde m\cdot t'\equiv m\cdot(t\cdot t')\pmod n$, thus $\tilde m\cdot t'\equiv m\cdot1\pmod n$, thus $\tilde m\cdot t'\equiv m\pmod n$.
Therefore, the adversary always finds $m$ by computing the uniquely defined $m=\tilde m\cdot t'\bmod n$ (see notation at end).

Critically w.r.t. to the question, there is no hesitation between several $m$ because

it is known that the challenger chose a valid message $m$, thus that $0\le m<n$
a solution $m$ to $\tilde m\equiv m\cdot t\pmod n$ exists and all are congruent modulo $n$, because a solution $t'$ to $t\cdot t'\equiv1\pmod n$ exists and all are congruent modulo $n$, because the adversary has chosen $t$ with $\gcd(t,n)=1$, thus $t\bmod n$ belongs to the multiplicative group of integers modulo $n$
when $y$ is congruent to $x$ modulo $n$, that is when $y\equiv x\pmod n$, the additional condition $0\le y<n$ makes $y$ uniquely defined by $(n,x)$.

Notation: for integer $n>0$ and integer $x$

$y\equiv x\pmod n$ means that $n$ divides $x-y$. This is best read as: $y$ is congruent to $x$ (short pause) modulo $n$. It can be written y = x (mod n).
$y=x\bmod n$ means that $n$ divides $x-y$, and $0\le y<n$. This can be read as: $y$ is $x$ modulo $n$. Such integer $y$ is uniquely defined for a given $(n,x)$. That $y$ is the remainder of the Euclidean division of $x$ by $n$ when $x\ge0$.


AES function with 128 bit key and 128 bit input size - does it have perfect secrecy? If I look at the version of AES that gets key of size 128 bit and encrypts messages of size 128 bits.

If I get some random key for the function, can I say it has a perfect secrecy and why?

After a lot of thinking it got me to the next question: if I apply AES 2 times, both times on the same input but with 2 different keys, can I get the same output or must the result be different?

I don't think a block cipher can offer perfect secrecy. Perfect secrecy means that knowledge of the ciphertext doesn't give you any information about the plaintext.

However a block cipher is a keyed permutation: the key is used to choose one permutation of the plaintext to ciphertext. The number of possible permutations is almost infinite. This means that the permutations selected by the key is a (randomly chosen) subset of all possible permutations.

Now the problem is that there may be mappings of one plaintext to a ciphertext that are more common in this set than others. This means that the tiniest amount of information may be leaked by a ciphertext: a specific key or group of keys is more likely to convert a specific plaintext to a specific ciphertext. This means that a certain plaintext is more likely than another plaintext for a given ciphertext.

And this, in turn, means that a block cipher is not perfectly secret - even if the key is the same size as the plaintext / ciphertext.

As for the second question: yes, you can get the same output. Although the keys select a specific permutation, it isn't said that the same mapping of one specific plaintext to one specific ciphertext isn't part of the permutation; a permutation is different if even just one mapping in the complete set of mappings is different. The chances are of course abysmally small to find it.

In the end we just don't need perfect secrecy. If we do want perfect secrecy it makes absolutely no sense to use a block cipher while a simple XOR suffices. The trick - as always - is to generate and share the perfectly random key stream. Once you have that you don't need AES anymore.


Secure password-authenticated key exchange that allows for passwords to be stored as hashes, but does not make the hashes password-equivalent Are there any secure password-authenticated key exchange that allows for passwords to be stored as hashes, but does not make the hashes password-equivalent?  This would be useful for many authentication applications.

Are there any secure password-authenticated key exchange that allows
  for passwords to be stored as hashes, but does not make the hashes
  password-equivalent?

Yes, they are called augmented or asymmetric password-authenticated key exchanges (aPAKE). They generally build on the scenario that the user knows a password and the server may only store a "verifier" that should at most admit off-line brute-force search of the password and the key exchange should only succeed if the right password is match with the right verifier.

There are extensions to this approach which also consider cases where the user has a second device (e.g. a smart card or a phone) and a connection between his primary and secondary device, for an overview of the protocols, see here.

The most notable standard aPAKE is currently OPAQUE, which has already been announced to soon get an IRTF / CFRG draft and hopefully someday become an RFC, see this email thread.

The basic idea of OPAQUE goes as follows:

Upon registration the server generates a random key $k$ and two DH key-pairs and stores one of the private key as well as the random key and the two public keys in clear and computes $H(pw,H'(pw)^k)$ with the random key to get an encryption key which is used to perform an authenticated encryption over the complete second DH key and its own DH public key.
Upon a login request the client chooses its own DH public key as well as a random key which is used to exponentiate the inner hash of the of the password, ie $H(pw)$.
The server then retrieves the data stored on registration, generates a fresh DH keypair, exponentiates the received exponentiated hash with the stored $k$ and computes a key-exchange (HMQV is recommended) over its long-term secret DH key, its short-term DH secret key, the received short-term DH public key and the stored long-term DH public key.
The client undoes the exponentiation from 2. and evaluates $H(pw,X)$ on the result. This can e.g. be a memory-hard hash function taking the second input as the salt. It uses the resulting key to decrypt the stored ciphertext  and itself computes the key-exchange.


Encrypt UDP packet with time-generated encryption key I'd like you to help me solve a dilemma of mine. I am currently building a home automation from scratch for my next house.

The basic gist of it is that I will send UDP packets over a local network.

I created the clients in Electron/Web App (so Js backend) and also used a RPi with a C program(I can change the language to something else if necessary) as the server with the database. The client will send a ~10byte package to the server. Speed is key here, and from my testing, over Wi-Fi turing on a LED is almost as fast (to the human eye) as a normal light switch. So I'd like to keep my speed.

Since the packets will hold string that basically say "turn on this light in this room" or "lock the door and activate the alarm" or "change the temperature in that room" I obviously need to encrypt the package, thus I arrived here.

Here is what I tried or thought of so far:

Use (D)TLS to send the Packages. While this would normally be a good idea, the libraries for it in JavaScript, Python or C are junk. There is no Python 3 library and the JavaScript's documentation is basically non-existant. One more thing to note is that this whole ordeal will be on a local network, so I don't know quite sure how to distribute the certificates in a secure way so they can't be replicated.
Use TLS and switch to TCP. This would probably be a good idea but the overhead of TCP and TLS seem so big in comparison to my mere 10byte packet. Again, the certificate issue rises up, since I don't know how to make a DIY CA.
Encrypt the packets with AES256. I wanted to do this until I realized that I don't have an extraordinarily good way to store the encyption key. I don't know how secure it is to store the key in plaintext in something like a NodeJS app. It a tad better in the binary of my C program but that is still not bulletproof. Maybe encrypting it in a file, but how do I keep that file safe.
The most secure thing to me is to still use AES256 but generate the key based on some factors like: a passphrase, the time, the server's and client's IP address "mumbo-jumboed" together. Like this, the attacker would have to guess my algorithm instead of a key which will always change(maybe once an hour).

One thing to note, the packets will be a one way road. The clients will send the command and the server will act upon it.

What are your thoughts? Am I wasting my time? Should I just buy an already made board with for alarms with sensors and such? Has anyone done something similar (I know home automation with Pis is a big thing, but I only see little things and I want something bigger, more comfortable).

EDIT: I removed the unnecessary things from the post, as suggested by DannyNiu.

Setup a DTLS proxy that invokes your server program to respond to requests should work. You don't need to put security and functionality in a single monolithic bundle.

This is called the Unix philosophy - write multiple programs that works together instead of trying to solve everything at once.

I don't know about NodeRTC you've mentioned in the comment, but there's another archtypical program called "ssh" we use everyday. At its minimal, it's a program that establishes secure channels between client and server, the channels can carry anything from stdio, tty, x11, to just any data. (which by the way is much easier to setup than a DTLS proxy if you may consider).

SSH saves its configs and keys in local files protected by permissions - had it been encrypted, it can't automatically start itself and would require user to input passphrase.

Since this site is about cryptography, the software part of the question should be kept out or it will be off-topic.


Is it possible to get different plaintexts from a single ciphertext using different keys? Suppose to have a chipertext that you can't decrypt, but you know that the plaintext can be A, B or C. Then arrives to you the key which is used to encrypt the chipertext.
You can decrypt the chipertext and you get a plaintext equal to A. Is it possible that the original plaintext was B or C and you have received a key such that the decryption process gives as output a different plaintext (A)?

Of course, each A, B and C have a meaning to you, so if you decrypt something else (like D, E, F...) you understand that it is meaningless. Also, i want to add that the source from which you receive the key cannot be trusted, but this doesn't mean that the key is always incorrect.

For clarification:

I receive a ciphertext I can't decrypt
I receive a key to decrypt the ciphertext
I decrypt the ciphertext with the key from step 2 and get the plaintext

How can I be sure that the plaintext obtained is infact the one previously encrypted if I can't trust the source from which I get the key and the ciphertext?

How can I be sure that the plaintext obtained is in fact the one previously encrypted if I can't trust the source from which I get the key and the ciphertext?

In general you cannot. The standard security notions of do not imply any binding. I.e., the definitions do not rule out that, given a key $k$ and a ciphertext $c \gets \operatorname{Enc}(k,m)$ an attacker might be able to find a key $k'$, such that $m' = \operatorname{Dec}(k',c)$ for some $m' \neq m$.
In fact, for many encryption schemes, such as block ciphers in some non-authenticated mode of operation, or a stream-cipher this is always possible, since decryption will always succeed with any key. What differs between different schemes is how much control an attacker may have over $m'$. But for many schemes some control, such as ensuring that a few bits have specific values is certainly possible.

Opening an encryption scheme to a different value than was originally encrypted is called equivocation. The one-time pad as described by AleksanderRas is an extreme of an equivocal encryption scheme, being *fully equivocal.
I.e., for any ciphertext $c$ and any plaintext $m'$ it is possible to find a key $k'$, such that $\operatorname{Dec}(k',c)=m'$. Being equivocal is in fact a useful property of an encryption scheme in applications such as secure multi-party computation. However, being fully equivocal actually implies the scheme must
necessarily have a key size which is as large as the message size. There are relaxed notions of somewhere equivocal and non-committing encryption.

That name of that last notion brings us to the fact that you do in fact want your encryption scheme to not be equivocal. The opposite of an equivocal encryption scheme would be a committing encryption scheme, where the ciphertext serves as a commitment to the plaintext.

At this point your question and in particular the "key-exchange" tag lead me to believe that you are probably not actually looking for an encryption scheme, but a commitment scheme. A commitment scheme allows one party to commit to a message $m$ in a commitment $c \gets \operatorname{Com}(m;r)$. Such a commitment can later be opened usually by revealing the randomness $r$ used in the commitment.

A commitment scheme has two important properties:

It is hiding, meaning that $c$ reveals nothing about $m$.
It is binding, meaning that it is infeasible to equivocate, i.e., to open the commitment $c$ to a message $m'\neq m$.


How much can we compress RSA public keys? I am wondering to what degree we can define an RSA variant, with a security argument that it is as safe as regular RSA with a given modulus size $m$ (e.g. $m=2048$), in which the public key has a compact representation of $k \ll m$ bits.

We can fix the public exponent to our favorite customary value, e.g. $e=2^{16}+1$ or $e=3$, thus need to store only the public modulus $n$. We need not store the leftmost bit of $n$, which is always set by definition; nor the rightmost bit, which is always set since $n$ is odd. With a little effort, we could save (very) few more bits noticing $n$ has no small divisors, but that will still be $k \sim m$ bits.

We can do better by forcing the $\left\lfloor m/2-\log_2(m)-2\right\rfloor$ high bits of $n$ to some arbitrary constant such as $\left\lfloor\pi \cdot 2^{\left\lfloor m/2-log_2(m)-4\right\rfloor}\right\rfloor$.
Observe that we can chose the smallest prime factor $p$ of $n$ just as we would do in regular RSA, then find the maximum integer interval $[q_0,q_1]$ such that any $q$ in that interval cause $n=p\cdot q$ to have the right high bits, then pick a random prime $q$ in that interval (most often there will be at least one, if not we try another $p$).
Some of the security argument is that

generating an RSA key $(p,q')$ using a regular method, with random huge primes in some appropriate range and no other criteria beside the number of bits in $n'=p\cdot q'$, and $p<q$;
then deciding the high bits of $n$ from those in $n'$;
then finding $[q_0,q_1]$, generating $q$ as a random prime in that interval, and setting $n=p\cdot q$;

demonstrably gives the same distribution of $(p,q)$ as said regular generation method, hence is as secure; then we remark that the high bits of $n$ are random (with some distribution not too far from uniform), and public, thus fixing it can't much help an attack (I think this can be made rigorous).

This is now $k \sim m/2+\log_2(m)$ bits to express the public key. We can save a few more bits, each one at worse doubles the amount of work to generate the private key (we can repeat the generation process outlined above until we find a key with these bits equal to some public arbitrary constant; or equal to bits from a hash of the other bits if we want a tighter assurance that the scheme is not weakened).

Can we do better, and what's the practical limit?

Update: In RSA Moduli with a Predetermined Portion: Techniques and Applications, Marc Joye discuses this, and reaches $k \sim m/3$ (without claim of optimality). I'm worried that I do not see an argument that the manner in which $(p,q)$ are selected in Algorithm 3 does not weaken $n$ against a dedicated factoring algorithm.

Daniel J. Bernstein mentioned your way of compressing RSA public keys in his paper "A secure public-key signature system with extremely fast verification".
The naive way you outline roughly doubles the work for each extra bit. If there were a better method which did not run very slowly then it could be repurposed as a factoring algorithm.
So if it were possible to decompress arbitrary 104 to 128-bit strings into secure 2048-bit RSA public keys faster than factoring as David Schwartz suggests then that would be quite remarkable. Every time you ran the algorithm you'd effectively be finding the approximately equal sized factors of some 2048bit number of which you'd specified a lot of the bits.
Although there's no theoretical reason I can think of why this should be impossible, nor would it render RSA necessarily insecure, it does strike me as rather unlikely.

As you hint, a further (impractical) way to reduce the storage of the unspecified low bits of the modulus would be to store their residues modulo various small primes and reconstruct using the CRT. In theory this should save between 3 to 4 bits for a 2048-bit modulus. You save the space because you can rely on the residues not being zero.


What does it mean the security parameter for a FHE scheme? FHE schemes claim to use some security parameter $\lambda$ for deriving the other parameters of the scheme, the size of the key and the possible circuits that can be evaluated. Like in Fully Homomorphic Encryption over the Integers. What does this parameter signify ?

Is something that applies only to FHE schemes and puts them on hierarchy of security ? How does this parameter compare to classical schemes, like RSA or AES ?
How can be compared the security of a FHE scheme with RSA or AES ?

What does this parameter signify ?

It's a tweakable parameter that varies (typically) the sizes of various objects in the cipher, and while any non-silly value will work (e.g. encrypt and decrypt properly), it does have an influence on the security of the system (typically, how hard of a 'hard problem' the system relies on).

  Is something that applies only to FHE schemes and puts them on hierarchy of security ?

Actually, it's fairly common for public key systems to have such a parameter; it's not limited to FHE systems.

  How does this parameter compare to classical schemes, like RSA or AES ?

Actually, RSA does have a 'security parameter'; it's the modulus size.  When you generate an RSA keypair, you select the size of the modulus; that's your security parameter.  Now, we typically don't call that a security parameter, however I believe that's for mostly historic reasons; RSA predates much of modern nomenclature, and so uses its own terminology.

As for AES, no, it doesn't - AES comes in three flavors (128 bit keys, 192 bit keys, 256 bit keys), and those are the only variations you are allowed.

Symmetric ciphers, in generally, usually don't have security parameters; I suspect that's because they're not usually based on preexisting 'hard problems' (and so don't need to choose the size of hard problem to rely on).


How does one calculate the scalar multiplication on elliptic curves? I found this example online:

  In the elliptic curve group defined by
  $$y^2 = x^3 + 9x + 17 \quad \text{over } \mathbb{F}_{23},$$
  what is the discrete logarithm $k$ of $Q = (4,5)$ to the base $P = (16,5)$?

  One (naïve) way to find k is to compute multiples of $P$ until $Q$ is found.
  The first few multiples of $P$ are:

  $P = (16,5), 2P = (20,20), 3P = (14,14), 4P = (19,20), 5P = (13,10)$,
  $6P = (7,3), 7P = (8,7), 8P = (12,17), 9P = (4,5)$

  Since $9P = (4,5) = Q$, the discrete logarithm of $Q$ to the base $P$ is $k = 9$.

How do we get to these scalar multiples?

  $P = (16,5), 2P = (20,20), 3P = (14,14), 4P = (19,20), 5P = (13,10)$,
  $6P = (7,3), 7P = (8,7), 8P = (12,17), 9P = (4,5)$

How can I check that $9·(16,5) = (4,5)$?

$\def\dbl{\mathrm{dbl}}$Okay, let's give the missing step between mikeazo's and poncho's answers.

I assume you've read mikeazo's answer to know how to add and double points.

Now, how do we get a scalar multiple of a point?

A simple algorithm is called "double-and-add", as it just does this.

In a simple example, we have $5 = 4 + 1 = 2·2 + 1$, and thus $5·P = (2·2+1)·P = 2·2·P + P$. So we calculate $P → \dbl(P) = 2·P → \dbl(\dbl(P)) = 4·P → 4·P + P=5·P$.

For your example of $200$, we have $200 = 128 + 64 + 8 = 2^7 +2^6+2^3$, and thus $200·P = 2^7·P + 2^6·P + 2^3·P$, which can be calculated as $\dbl(\dbl(\dbl(\dbl(\dbl(\dbl(\dbl(P))))))) + \dbl(\dbl(\dbl(\dbl(\dbl(\dbl(P)))))) + \dbl(\dbl(\dbl(P)))$. (Of course, you would calculate the common sub-terms only once.)

Alternatively, we can use the distributive law to write it this way: $200·P = 2·2·(2·2·2·(2·P + P) + P)$.

(Note that we used the binary form of the scalar factor here to decide when to add and when not to add.)

Here are two general forms of this algorithm to calculate $d·P$, when $d$ has the binary form $d_kd_{k-1}\dots d_1d_0$ (assuming d_k = 1):

Starting from the small-endian bits:

Q := 0
R := P
for i = 0 .. k:
   if(d_i = 1)
      Q = add(Q, R)
   R = double(R)
return Q

Starting from the big-endian bits:

Q := 0
for i = k ... 0:
   Q := double(Q)
   if(d_i = 1)
      Q := add(Q, P)
return Q

Note that this is actually the same algorithm you are using for modular (or other) exponentiation, just with the operations square and multiply instead (and then usually named square-and-multiply).

Also, this trivial implementation is quite vulnerable to a power analysis attack, if implemented on a smart card, as doubling and adding doesn't use quite the same amount of power, and the adding is only done when a bit in the (usually secret) exponent is set. There are measures against this, and also a bit more efficient point multiplication algorithms – any book about elliptic curves should mention some of them.


Share encrypted files without giving master key Imagine I have four files I want to encrypt. I have master key, and from that master key I derive four keys, one for each file:

key1 = HMAC-SHA-2(masterKey, filename1)
key2 = HMAC-SHA-2(masterKey, filename2)
key3 = HMAC-SHA-2(masterKey, filename3)
key4 = HMAC-SHA-2(masterKey, filename4)

After that, I encrypt each file with AES, each with its own derived key (file1 encrypted with key 1, file2 encrypted with key2, etc).

Imagine Alice (owner of the master key) publishes every encrypted file publicly and only shares key3 with Bob.

Is it then safe to assume that Bob will only be able to decrypt file
three because he only has key3, and no one else will be able to
encrypt the other files (except Alice)?
Is Bob able to decrypt the other files, when he knows that his key
was made by using HMAC-SHA-2(masterKey, filename3), even though he
doesn't have the keys for the other files?
If all four keys are handed out to one person (and that person also
knows the four filenames) , is that person then able to derive the
master key?

Yes, it's safe, as you can't calculate the secret key from the HMAC result. HMAC would be useless without this feature
No, Bob will not be able to use his key to calculate the other keys, as long as you use a  reasonable hash function (SHA-2 should fit)
It's the same as 1., Bob doesn't get more information by more derived keys

But when Bob get the key for filename2 and Carlos for filename3, then it's important that Bob nor Carlos are able to affect the filenames.
Otherwise they could create a key for a encrypted file related to another person


Lifting a congruence $f(X) \equiv gh (\textrm{mod} \ p)$ to a higher power moduli I have the polynomial ring $R = \mathbb{Z}[X]/(X^N - 1)$ with $N = 11$ and $h \in R$ with
\begin{equation*}
h = 7 -11X - 7X^2 -12X^3 + 8X^4 - 11X^5 + -8X^6 + 11X^7 - 4X^8 + 2X^9 + 3X^{10}
\end{equation*}
Now I want to find the polynomial $u$ such that
\begin{equation*}
u\cdot h + v\cdot (X^N - 1) \equiv X - 1 \ (\textrm{mod} \ 32)
\end{equation*}
where we assume $\gcd(h, X^N - 1) = X - 1$ reducing coefficients $\textrm{mod} \  32$. If we also let $*$ denote the multiplication in $R$, I can easily find $u$ such that $u*h \equiv X - 1 \ (\textrm{mod} \ 2)$ using the extended Euclidean algorithm, and it's $u = 1+X+X^{4}+X^{5}+X^{9}$, but I'm having issues using this to construct the solution such that $u' * h \equiv X - 1 \ (\textrm{mod} \ 32)$. Can someone outline an algorithm or link me some reading material on how to do this?

One way to raise solutions to higher powers of the modulus is Hensel's Lemma.

First, you need to express your element as a root of a function: $g(u)= hu - (X-1)$
Find the solution modulo 2, which you already did.
Use the Lemma to raise this solution to higher powers of 2. Maybe it is useful to do this in several steps. Find the solutions mod 4,8,16 and then 32.


salting with password hash to improve security? Would something like the following improve security (against rainbow attacks, not brute force)? Assume that $P$ is a user-chosen password, and the objective is to obtain a hash $H$ for password checking.

Let $S$ be a random salt.
Let $A_1 = MD5(P || S)$
Let $A_2 = MD5(A_1 || P) || A_1$
Let $H = MD5(A_2)$.

The idea is to increase the ciphertext length and the number of MD5 iterations by "salting" the hash with another hash of the password. Does that really help?

Security against attacks using rainbow tables requires using a salt. In your first step $A_1 = MD5(P || S)$, you're already mixing in a salt. Provided that the salt is indeed globally unique (and randomly generating the salt is a correct way of achieving that), you already have protection against rainbow tables.

In a nutshell, rainbow tables trade off a huge amount of pre-computation for the ability to crack many hashes quickly. As soon as you use a salt, a useful rainbow table would have to accommodate for all possible salt values, which very quickly becomes impractical.
For more information, read
What are rainbow tables and how are they used?

There is nothing to be gained by mixing the salt in again through another application of MD5. However, if you repeated the process many times, you would achieve another property that is necessary for a password hashing function, namely that it must be slow, because that hurts the attacker far more than the defender. On this topic, do read
How to securely hash passwords?

So if instead of using $A_2$ you used $A_{10000}$ (or however many iterations would be reasonable based on current CPU speeds), you would have what looks like a reasonable password hashing scheme, built along the same lines as PBKDF2, which is one of the recognized good password hashing functions. However, in cryptography, details matter. Maybe what you're doing is as good as PBKDF2, or maybe it has a fatal flaw that isn't immediately obvious to me. It would take a long time of analysis by multiple expert cryptographers to determine whether your password hashing function is acceptable.

Therefore, don't roll your own: use a generally-approved password hashing function. There are three big names: scrypt, bcrypt and PBKDF2. Scrypt is the new and improved thing, bcrypt is tried and tested, and PBKDF2 is showing signs of age, so bcrypt and scrypt are slightly preferable, but even PBKDF2 isn't fundamentally wrong. All three have PHP implementations available.


Is it possible to validate a Public Key in RSA? If I have a 1024-bit number, and someone is telling me that it is in fact a valid RSA public key, is there any way I can quickly validate that it is indeed so (without cracking RSA)?

(I suppose I am asking if it's possible to quickly tell if a number only has 2 prime factors)

There are two approaches to such a validation:

Test: you can look at the number and decide without involving the person who gave it to you.
Proof: The person who generated the number can also give you additional information that will convince you it is a correct RSA number.

There are no tests for RSA numbers.

There are proofs for RSA numbers, including "zero-knowledge" proofs. Zero-knowledge means that the person who generated the number can convince you it has two prime factors without giving you any information about what the two factors are.

A zero-knowledge proof can be interactive: you and the generating party exchange messages (akin to challenges/responses) that lead you to become convinced. It can also be non-interactive: its a transcript that convinces anyone who looks at it. Thus if the generating party gives you the number and the proof, you can forward that to anyone else and they too will be convinced. With interactive proofs, unless you are watching each message go back and forth and know that the two parties that are interacting are not colluding, you can't be convinced it is correct.


Inversion in $GF(2^{10})$ Using Composite Fields I'm designing a circuit that uses many $GF(2^{10})$ inverters.  Normally for this sort of thing I use lookup tables.  (Itoh-Tsujii is not efficient for these smaller fields.)  This application is for an ASIC so the 1024-deep ROM will be optimized by the synthesizer.  However, I recalled that when I built an AES encryptor, I used a Satoh S-box which efficiently computed the inverse in $GF(2^8)$ by splitting an element into two composite-field elements in $GF(2^4)$, performing an extended Euclidean algorithm which required finding an inverse in the much-smaller $GF(2^4)$, and then converting composite-field elements back to $GF(2^8)$.

The question is:  could I do something similar to invert elements in $GF(2^{10})$ by using composite fields in $GF(2^5)$?

Do you know how to invert complex numbers? If yes, then you also know the answer to your question:

$$z^{-1} = \frac{\bar{z}}{z\cdot\bar{z}},$$

where $\bar{z}$ is the complex conjugate of $z$ (if $z=x+y\cdot i$ with $x, y\in\mathbb{R}$, then $\bar{z}=x-y\cdot i$) and $z\cdot\bar{z}=x^2+y^2\in\mathbb{R}$.

Complex conjugation is a field automorphism of order $2$, i.e., composed with itself it is the identity ($\bar{\bar{z}}=z$). For the field $\mathbb{F}_{2^{10}}$ squaring is a field automorphism (called Frobenius automorphism) of order $10$, as $z^{2^{10}} = z$ for $z\in\mathbb{F}_{2^{10}}$. So if you take the field automorphism $\sigma$ of $\mathbb{F}_{2^{10}}$ defined by $\sigma(z) = z^{32}$ (the 5th power of the Frobenius automorphism) you get an automorphism of order $2$ like for the complex numbers. The role of the real numbers (which are fixed under complex conjugation) is played by the field $\mathbb{F}_{32}$ (whose elements are fixed under $\sigma$).

If you know an irreducible polynomial $f$ of degree $5$ over $\mathbb{F}_2$, you can use it to define the field $\mathbb{F}_{32}$ as $\mathbb{F}_2[X]/(f(X))$. To get $\mathbb{F}_{2^{10}}$ as extension field of degree $2$ over $\mathbb{F}_{32}$ you can take the irreducible polynomial $g(T) = T^2+T+1$ over $\mathbb{F}_2$, which stays irreducible over $\mathbb{F}_{32}$ as $2$ does not divide $5$ ($\mathbb{F}_{32}$ doesn't have subfield of order $4$, as its order $32$ prevents it to be a vector space over $\mathbb{F}_4$): $\mathbb{F}_{2^{10}} = \mathbb{F}_{32}[T]/(g[T])$.

Any element $z\in\mathbb{F}_{2^{10}}$ you can write as $z = x+y\cdot T$, where for $T^2 = 1+T$ holds for $T\in\mathbb{F}_{2^{10}}$ (as $T$ is root of $g$). Now

$$z^{-1} = \frac{\sigma(z)}{z\cdot\sigma(z)} = \frac{\sigma(x+y\cdot T)}{(x+y\cdot T)\cdot\sigma(x+y\cdot T)} = \frac{x+y\cdot \sigma(T)}{(x+y\cdot T)\cdot(x+y\cdot\sigma(T)},$$
using that $x,y\in\mathbb{F}$ are fixed by $\sigma$. As $T^4 = (T^2)^2 = (T+1)^2 = T^2 + 1 = T + 1 + 1 = T$ ($T$ is in the subfield of order $4$ of $\mathbb{F}_{2^{10}}$) we get $\sigma(T) = ((T^4)^4)^2 = T^2 = T+1$ and therefore

$$z^{-1} = \frac{x+y\cdot(T+1)}{(x+y\cdot T)\cdot(x+y\cdot(T+1))} = \frac{x+y\cdot(T+1)}{x^2 + x\cdot y\cdot (T+1) + y\cdot T\cdot x + y\cdot T\cdot y\cdot(T+1)} =
\frac{x+y\cdot(T+1)}{x^2 + x\cdot y + y^2},$$
using $T^2 + T = 1$.

The denominator is an element of $\mathbb{F}_{32}$, it's non-zero (do you know why?), so you can invert elements of $\mathbb{F}_{2^{10}}$ if you know how to invert elements of $\mathbb{F}_{32}$.