Proper uses for CTR and CBC AES block cipher modes Assuming the following:

Key is randomly generated is being used (32 bytes+)
IV is also randomly generated
Crypto random key generator is used
Data being encrypted contains common bytes like { } and " and keys (like JSON)

Which of these modes (CTR, CBC) are more appropriate for storing sensitive information?

Is it possible for someone to discover the CTR counter value knowing some of the bytes in the original message?

Is CBC safer than using CTR for storing data, or would it be more susceptible to a padding oracle?

Is it just a bad idea in general to encrypt a self-describing data structure?

As said by Thomas in the comment, modern encryption algorithms should work for all kinds of data, regardless of whether the plaintext is partially known or not.

In both modes of operation (CTR and CBC), for stored data you should remember to get a new initialization vector and reencrypt your whole "message" (or database entry) when changing any part of the data, not try to reencrypt only the changed parts. (Though CBC is likely a bit more robust here – the attacker in the case of IV reuse only gets to see from which block on the data changed, while with CTR mode she can see the XOR difference between the old and new values, assuming she can observe both ciphertext.)

  Is it possible for someone to discover the CTR counter value
  knowing some of the bytes in the original message?

The counter value can be derived from the initialization vector, and thus is considered public knowledge (even if nothing is known about the plaintext). There is no weakness resulting from that, as long as you take care not to repeat your counter values.

With CTR mode, you don't get authentication, which means that an attacker who is able to change your message and observe your programs reactions to that might gain some knowledge about the contents. To avoid this, combine it with a MAC algorithm (preferably on the ciphertext), like a HMAC, which refuses decryption if failed. (Have an independen key for your MAC.)

The same is valid for CBC, just the methods of attacking are different. Here it is even more important to apply the MAC on the ciphertext, not on the plaintext, for the mentioned padding oracles.

As Ricky Dehmer mentioned in a comment, an attack scenario would be someone who got write access to your database, but doesn't have the key, and aims either to maliciously modify the data, or to use chosen-ciphertext attacks to break your encryption privacy.

Don't forget to include the initialization vector in the MAC-ed message.

For an encrypted database column, you could store the tuple (IV, Ciphertext, MAC tag) together, either in one column (most easily in this order) or in three columns, and for decryption pass them together to your decryption function, which should first check the MAC, and then decrypt the ciphertext.

A authenticated encryption mode like OCB or GCM already includes the authentication, so you have less hassle to worry about.


autokey script gone wrong! I tried to make a script to encode a txt with the autokey cipher. From my poor understanding of the cipher I created another cipher which has nothing to do with autokey:

first I encoded a txt with a key which give me a result as long as the original txt -Vigenère cipher used
then I encoded the original txt with first result -Vigenère cipher

How can I get the original txt from the original key?!

$$\begin{array}{}
\text{txt} &+ &\text{key} &\to &\text{etxt}\\
\text{txt} &+ &\text{etxt} &\to &\text{final result}
\end{array}
$$

Editor's note: the + stands for vigenere cipher algorithm

Recipe sans math

Given a non-empty $\text{final result}$ obtained as in the question, and $\text{key}$, we can find $\text{txt}$ as follows (see full answer for assumptions made and justification):

Extend $\text{key}$ to the same length as $\text{final result}$, by repeating $\text{key}$ as necessary, then truncating.
Form pairs of letters at same index in $\text{final result}$ and $\text{key}$, and decode per the following table, where $\text{key}$ determines the line, and $\text{final result}$ determines the column. The intersection should contain two possible letters for $\text{txt}$.
We now have two choices for each letter of $\text{txt}$ (or are certain that $\text{final result}$ was not obtained as in the question, if any -- was encountered). In the former case, redundancy in $\text{txt}$ is the only way to disambiguate.

   A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z final result
A  AN -- BO -- CP -- DQ -- ER -- FS -- GT -- HU -- IV -- JW -- KX -- LY -- MZ --
B  -- AN -- BO -- CP -- DQ -- ER -- FS -- GT -- HU -- IV -- JW -- KX -- LY -- MZ
C  MZ -- AN -- BO -- CP -- DQ -- ER -- FS -- GT -- HU -- IV -- JW -- KX -- LY --
D  -- MZ -- AN -- BO -- CP -- DQ -- ER -- FS -- GT -- HU -- IV -- JW -- KX -- LY
E  LY -- MZ -- AN -- BO -- CP -- DQ -- ER -- FS -- GT -- HU -- IV -- JW -- KX --
F  -- LY -- MZ -- AN -- BO -- CP -- DQ -- ER -- FS -- GT -- HU -- IV -- JW -- KX
G  KX -- LY -- MZ -- AN -- BO -- CP -- DQ -- ER -- FS -- GT -- HU -- IV -- JW --
H  -- KX -- LY -- MZ -- AN -- BO -- CP -- DQ -- ER -- FS -- GT -- HU -- IV -- JW
I  JW -- KX -- LY -- MZ -- AN -- BO -- CP -- DQ -- ER -- FS -- GT -- HU -- IV --
J  -- JW -- KX -- LY -- MZ -- AN -- BO -- CP -- DQ -- ER -- FS -- GT -- HU -- IV
K  IV -- JW -- KX -- LY -- MZ -- AN -- BO -- CP -- DQ -- ER -- FS -- GT -- HU --
L  -- IV -- JW -- KX -- LY -- MZ -- AN -- BO -- CP -- DQ -- ER -- FS -- GT -- HU
M  HU -- IV -- JW -- KX -- LY -- MZ -- AN -- BO -- CP -- DQ -- ER -- FS -- GT --
N  -- HU -- IV -- JW -- KX -- LY -- MZ -- AN -- BO -- CP -- DQ -- ER -- FS -- GT
O  GT -- HU -- IV -- JW -- KX -- LY -- MZ -- AN -- BO -- CP -- DQ -- ER -- FS --
P  -- GT -- HU -- IV -- JW -- KX -- LY -- MZ -- AN -- BO -- CP -- DQ -- ER -- FS
Q  FS -- GT -- HU -- IV -- JW -- KX -- LY -- MZ -- AN -- BO -- CP -- DQ -- ER --
R  -- FS -- GT -- HU -- IV -- JW -- KX -- LY -- MZ -- AN -- BO -- CP -- DQ -- ER
S  ER -- FS -- GT -- HU -- IV -- JW -- KX -- LY -- MZ -- AN -- BO -- CP -- DQ --
T  -- ER -- FS -- GT -- HU -- IV -- JW -- KX -- LY -- MZ -- AN -- BO -- CP -- DQ
U  DQ -- ER -- FS -- GT -- HU -- IV -- JW -- KX -- LY -- MZ -- AN -- BO -- CP --
V  -- DQ -- ER -- FS -- GT -- HU -- IV -- JW -- KX -- LY -- MZ -- AN -- BO -- CP
W  CP -- DQ -- ER -- FS -- GT -- HU -- IV -- JW -- KX -- LY -- MZ -- AN -- BO --
X  -- CP -- DQ -- ER -- FS -- GT -- HU -- IV -- JW -- KX -- LY -- MZ -- AN -- BO
Y  BO -- CP -- DQ -- ER -- FS -- GT -- HU -- IV -- JW -- KX -- LY -- MZ -- AN --
Z  -- BO -- CP -- DQ -- ER -- FS -- GT -- HU -- IV -- JW -- KX -- LY -- MZ -- AN
key

For example, given $\text{final result}=\mathtt{HOS}$ and $\text{key}=\mathtt{DOG}$

for the 1st letter we use the line for $\mathtt D$ and the column for $\mathtt H$; we read CP there, thus know that the 1st letter of $\text{txt}$ is $\mathtt C$ or $\mathtt P$
for the 2nd letter we use the line for $\mathtt O$ and the column for $\mathtt O$; we read AN there, thus know that the 2nd letter of $\text{txt}$ is $\mathtt A$ or $\mathtt N$
for the 3rd letter we use the line for $\mathtt G$ and the column for $\mathtt S$; we read GT there, thus know that the 3rd letter of $\text{txt}$ is $\mathtt G$ or $\mathtt T$

Thus $\text{txt}$ can be $\mathtt{CAT}$. In English, that's the most common of 8 possibilities including also $\mathtt{PAT}$ (a chess term), $\mathtt{PNG}$ (initials of an image format), and 5 others.

Detailed answer

I'll assume the usual definition of the Vigenère cipher, even though that's reportedly not the cipher promoted by Vigenère, which is closer to autokey. Consequently:

$\text{txt}$, $\text{key}$, $\text{etxt}$ and $\text{final result}$ are strings of letters $\mathtt A$ to $\mathtt Z$, which will be assimilated to integers $0$ to $25$ without explicit mention.
$\text{txt}$ and $\text{etxt}$ are unknown strings, while $\text{key}$ and $\text{final result}$ are known. They all are of equal length (with $\text{key}$ extended by repetition as necessary).
The question's $\,+\,$ is not regular addition, and I'll note the variant $\;\widetilde+\;$ to avoid confusion. It holds that

$\;\widetilde+\;$ applied to individual letters stands for addition modulo $26$, so that $\mathtt R\;\widetilde+\;\mathtt M=\mathtt D$, because $\mathtt R$ maps to $12$, $\mathtt M$ maps to $17$, $12+17\bmod26$ is $3$, and $3$ maps back to $\mathtt D$. See this table.
$\;\widetilde+\;$ applied to two strings of letters of equal length performs $\;\widetilde+\;$ on letters of same rank in each strings, producing a string of the same length.

For example, if $\text{txt}$ is $\mathtt{CAT}$ and $\text{key}$ is $\mathtt{DOG}$, then the question's equation becomes
$$\begin{array}{llllllllll}
\text{txt}\;\widetilde+\;\text{key} &=&\text{etxt}        &=&\mathtt{CAT}\;\widetilde+\;\mathtt{DOG}&=&\mathtt{FOZ}\\
\text{txt}\;\widetilde+\;\text{etxt}&=&\text{final result}&=&\mathtt{CAT}\;\widetilde+\;\mathtt{FOZ}&=&\mathtt{HOS}
\end{array}
$$

To solve for $\text{txt}$, we eliminate $\text{etxt}$ in the second equation by substitution with the value assigned to $\text{etxt}$ per the first equation. The equations are equivalent to $\text{txt}\;\widetilde+\;(\text{txt}\;\widetilde+\;\text{key})\,=\,\text{final result}$.

This implies that for each $t$, $k$ and $f$ designating letters of same rank in $\text{txt}$, $\text{key}$ and $\text{final result}$, we have $t\;\widetilde+\;(t\;\widetilde+\;k)=f$. Per usual rules of (modular) arithmetic in the ring $(\Bbb Z_{26},+,\times)$, including associativity and distributivity, this is $(2t+k\bmod26)=f$, and is equivalent to $2t\equiv f-k\pmod{26}$.

The modulus $26$ is the product of distinct primes $2$ and $13$. Therefore, by the Chinese Remainder Theorem, the above equation is equivalent to $2t\equiv f-k\pmod2$ and $2t\equiv f-k\pmod{13}$. And, since $2^{-1}\bmod13=7$, for given $f$ and $k$, and under the necessary condition that they are of the same parity, we can obtain the two solutions for $t$ as$$t_0=7(f-k)\bmod 13\quad\mathsf{then}\quad t_1=t_0+13$$

The recipe's table is a pre-computation of this formula. For example, given $f=7=\mathtt H$ and $k=3=\mathtt D$, we get that $t$ is one of $t_0=7(7-3)\bmod13=28\bmod13=2=\mathtt C$ or $t_1=2+13=15=\mathtt P$, and the table has CP for line D column H.

Notations for modular arithmetic

By definition, for positive integer $m$ and any integers $a$ and $b$

the notation $b\equiv a\pmod m$ means that $a-b$ is a multiple of $m$
the notation $b=a\bmod m$ additionally means that $0\le b<m$
Note: in the later notation, there is neither an $\equiv$ sign, nor an opening parenthesis immediately on the left of $\bmod$
equivalently to the previous statement, $a\bmod m$ is the integer defined as

for non-negative $a$, the remainder of the Euclidean division of $a$ by $m$
for negative $a$, the integer $m-1-((1-a)\bmod m)$

the notation $b\equiv a^{-1}\pmod m$ means that $a\,b\equiv1\pmod m$
the notation $b=a^{-1}\bmod m$ additionally means that $0\le b<m$.
Note: $b$ is called the multiplicative inverse of $a$. It exists when the Greatest Common Divisor of $m$ and $|a|$ is $1$. For small integers, $b$ can be found from $a$ and $m$ by trial and error. More generally, the GCD and $b$ can be computed using the extended Euclidean algorithm, or its half-extended variant.


Linkable Ring Signatures on Pairing-Friendly curves I'm working on a pairing-friendly (Barreto-Naehrig) elliptic curve. If I understand correctly, one consequence of this is that the Decisional Diffie-Hellman assumption no longer holds, but the Computational Diffie-Hellman assumption still should.

I'd like to be able to construct linkable ring signatures, but all the linkable ring signature schemes I know of depend on DDH for their anonymity proofs, and none of the pairing-based ring signature schemes I know of are linkable.

Are there any linkable ring signature schemes that are usable on pairing-friendly curves?

As I know, the pairing on bn-curve is type 3, $G_1\times G_2\rightarrow G_T$.
In CryptoNote, the key image is $I=H(P)^x$ and it can't be attacked if $H(*)$ and $P$ belong to same group.

See my question related.


Feistel cipher vs Substitution-permutation network - number of rounds So I have been doing for the last couple of days comparison between Feistel cipher and Substitution-permutation network. Now I can say I know a lot about them and their similarities and differences but there is still one more thing I would like to know and I can't find it anywhere.

The thing is I don’t know how many rounds these structures have. I mean simply which structure has more rounds and why?

After searching a lot for this I have a feeling (didn't find any hard proof) that we can customize number of rounds when designing a symmetric algorithm based on one of those structures, if this is true then I want to know on which structure based algorithms has typically more rounds (or how many rounds they need to have to be considered safe)?

While I can confirm that your “feeling“ is indeed correct, the rest of your question is not that easy to answer. I’ll try to give you some insight nevertheless.

Generally…

The number of rounds depends on the design and security parameters of the individual ciphers. This makes it rather impossible to generalize things in form of “structure $A$ should use $x$ rounds, and structure $B$ should use $y$ rounds”. While cipher algorithms may share alike structures, their internals differ… and so do their individual round numbers.

Yet, what we can say is that less rounds tend to make a cipher less secure, while more rounds tend to make a cipher more secure. This might sound perfect, but you have to keep in mind that you can’t simply take a random cipher and hope to make it “unbreakable” by throwing enough rounds at it.

Where increasing rounds doesn’t save the day…

You might have heard about cryptanalysis where people show that some algorithms are breakable when you attack “reduced rounds” of that cipher. That practically means that they took a cipher algorithm, decreased the number of rounds below the recommended minimum, and tried to successfully apply attacks on the reduced-round version of the cipher to learn about potential weaknesses. A potential weaknesses in the reduced-round version might be expandable  to the full-round version of the cipher (which uses the originally defined and/or agreed upon number of rounds).

In a worst-case scenario, someone finds a successful attack on a reduced-round cipher and successfully expands that attack to any number of rounds. From that moment on, all hope is lost for the involved cipher as that would be a “total break”… and increasing the number of rounds won’t help.

But as long as we’re not talking about such worst-case scenarios, increasing the number of rounds can help increase (or regain) the safety margin in other cases.

The “ideal” number of rounds…

In the end, cryptography is all about safety margins. During the design phase, the cipher algorithm designer will try to pinpoint the to-be-expected security his/her cipher offers as exact as he/she possibly can and/or can prove. (Assuming you’ve seen a few reference papers already, you’ll know that cipher designers publish such proofs in the reference papers which describes their individual cipher designs.) Simpler said: while creating the cipher algorithm, the designer tries to identify the minimum number of rounds his cipher needs to be able to meet the security parameters of the cipher, as well as the recommended number of rounds.

Most of the time, there is no maximum number of rounds defined. The reason for this is pretty simple: the cipher designer already provided the *recommended * number of rounds  and – if possible – related security proofs. The recommended number of rounds represents the (let’s just call it) “ideal” number of rounds in relation to the cipher’s security.

Increasing the number of rounds beyond that level may increase security, but from a certain level on you will merely be able to detect a minimal security gain, while – at the same time – you’ll notice you’re wasting too many system resources and valuable time… which doesn’t really make sense as the gain is discardable compared to the investment of time and resources. (Think about it: no one will want to wait half an hour for something to encrypt, just because you chose to increase the original number of rounds from 10 to 1.000.0000.000. Besides, the cipher will not be a million times more secure if you do that.)

tl;dr

There is no perfect answer to the question “which cipher structure” will need “what number of rounds” to be secure, because that depends on the individual cipher algorithms. While cipher structures might be alike, the security margins tend to be different. Simpler said: two ciphers with the same structure might need a totally different number of rounds to make both provide a comparable security.

But, what we can say is:

You can make almost any cipher more secure by adding enough rounds… assuming it’s not totally broken. Also, you can make almost every cipher insecure by reducing enough rounds. (1)

(1) Never reduce rounds unless you can actually prove that your reduced-round version will still provide the expected safety margin. Without such proof, you’re walking on very thin ice.


secret sharing scheme difference confused about differences between 5 out of 5 threshold secret sharing scheme and 4 out of 5 threshold secret sharing scheme. how would the share and reconstruction schemes be different assuming both of them use xor?

For $(t,n)$ where $t=n,$ and where the secret is the vector $Z,$ the XOR based scheme is:

Scheme $\cal S:$

distribute $n$ shares, one to each user, as the binary vectors
$$S_1=X_1,S=2X_2,\ldots,S_{n-1}=X_{n-1},S_n=Z\oplus X_1\oplus \cdots\oplus X_{n-1}$$.
reconstruct $Z$ by computing $S_1\oplus\cdots S_n$.

For $t=n-1,$ one way is to create $n$ different $(n-1,n-1)$ schemes for each of the $n$ subsets of size $t=n-1$. So for the users $1,2,\ldots,n-1$ we can use the scheme

Scheme ${\cal S}(1,\ldots,n-1):$

distribute $n-1$ shares, one to each user, as the binary vectors
$$S_1=X_1,S_2=X_2,\ldots,S_{n-2}=X_{n-2},S_{n-1}=Z\oplus X_1\oplus \cdots\oplus X_{n-2}$$.
these users reconstruct $Z$ by computing $S_1\oplus\cdots S_{n-1}$. .

Note that the sums of the different shares  differ by the xor of two random vectors, in the symmetric difference of the two sets of users, and if these are uniformly generated the required intra-subset security property will hold.

Obviously this multiplies storage and communication by a factor of $n.$


Is it secure to compute the exponentiation and the LWE operation? Suppose Alice and Bob have specified an elliptic curve, for example, secp256k1. Alice has a secret number $s$ (can be seen as secret key), Bob choose a point $g$ on the curve and send it to Alice. After receiving the point, Alice computes $g^s$ and sends it the Bob.
$\text{Whether the interaction will reveal Alice's secret key?}$

Similarly, in a RLWE system, Alice has a secret polynomial $s\in R_q$ ($R_q=\mathbb{Z}_q[x]/(x^n+1)$),Bob chooses a polynomial  $a\in R_q$ and sends it to Alice, Alice  compute $as+e$, where $e\leftarrow \chi$ is a secure distribution in RLWE, then in this situation, whether Bob will learn the secret $s$? Intuitively, if Bob chooses some polynomial $a$ satisfied $ab=0$ for some $b$, then it seems that Bob could learn the $s$, but does Alice have some methods to judge if the polynomial $a$ come from Bob has the property?

For the second question, it depends on whether we can trust Bob to generate $a$ uniformly at random and without any “hidden structure.” If we can trust him, then this is secure assuming RLWE is hard; what Bob gets is merely one properly distributed RLWE sample.
However, if Bob may choose $a$ in a malicious or “sneaky” way, then there can be attacks. For example, Bob can choose $a$ as an NTRU public key, as $a=f \cdot g^{-1} \pmod{q}$ for “short” polynomials $f,g$ of a certain form that constitute the secret key. Then, giving Bob $s \cdot a + e$ for short $s,e$ is essentially just NTRU encryption, and Bob can use $f,g$ to recover $s,e$. Moreover, such an $a$ doesn’t even seem to “look suspicious,” since it’s commonly conjectured that NTRU keys constructed in this way are indistinguishable from uniformly random. So Alice can’t even hope to catch Bob being sneaky in this way.
If Bob doesn’t care about “acting suspiciously,” then there is an even simpler attack: Bob can choose $a=p$ for some small scalar integer $p$ that will be slightly bigger than the coefficients of $e$. Then, giving Bob $b =s \cdot a + e = ps + e$ makes it easy for Bob to recover $e$ (just reduce $b$ modulo $p$) and then $s$.


How were the best AES whiteboxes in the CHES 2017 CTF challenge built and broken? Along CHES 2017 was a Capture the Flag Challenge, aka The WhibOx Contest.

Participants submit C source code with interface

  void AES_128_encrypt(unsigned char ciphertext[16], unsigned char plaintext[16]);

that performs AES-128 encryption with some key. Other participants attempt to find that key from the submission. A mechanical referee checks if a guess of the key is correct. A rating system awards points (strawberries and bananas) as a function of how much time one's submission remains unbroken, and for breaking a submission. Survival range has been from 1 minute to a record 28 days 13h 42'.

What where the techniques used by the leading participants, both for making whiteboxes, and attacking them? The only clear thing is that there was an inflation in size; the winner is 28MByte.

Junwei Wang gave a talk on how the winning entry (#777 by cryptolux) was designed and how team cryptoexperts broke it. Slides, video.

The overvew of the design (slide 9) is:

Multi-layer protection

Inner: encoded Boolean circuit with error detection
Middle: bitslicing
Outer:   virtualization, randomly naming, duplications, dummy
operations

Code size: ~28 MB
Code lines: ∼2.3k
12 global variables including:

computation state (2.1 MB)
program bytecode (15.3 MB)

And the overview of their approach to reversing it:

Reverse engineering ⇒ a Boolean circuit
Single static assignment (SSA) transformation
Circuit minimization
Data dependency analysis
Key recovery with algebraic analysis


What do people use non-extractable WebCrypto keys for? I understand that non-extractable keys are secure because they cannot be exported. But I think many people would WANT to export their keys at some point if they don't want to risk losing everything.
For example, if you stored all your app data encrypted using a WebCrypto non-extractable key and can't export the key, this means you lose access to all your encrypted data when your indexedDB gets wiped out for some reason, or even worse, if your entire computer gets wiped out or the disk gets corrupted (This is not an impossible scenario. For example when you send off your problematic macbook to Apple for repair, they say I should back up everything in case something goes wrong)
This is just encrypt/decrypt scenario, but I'm sure there are same types of issues with sign/verifying messages. If I want to use crypto as my identity by signing messages, why would I want to use a key that even I cannot access and export myself, so I can only use that key on that specific browser on that specific device?
So I guess this is a four part question:

What are the actual use cases for non-exportable keys? Why would people want to go that far while risking key losses?
Don't most people want to be able to reuse and back up their keys, especially since they're used for identity and encryption purposes?
If #2 is true, and there is no way to securely store extractable keys inside a browser, how do people build a secure app using WebCrypto?
Finally, isn't storing keys on the browser fundamentally insecure whether extractable or not? Even if the key cannot be exported, a website sign a message on behalf of the user (or decrypt a message intended for the user and send it to their server) without the user knowing, and that's a huge security issue.

What are the actual use cases for non-exportable keys? Why would people want to go that far while risking key losses?

One of the main ideas of key stores is that access to the keys is minimized; as long as you don't export a key, you can be sure that no other service is using the key.

Don't most people want to be able to reuse and back up their keys, especially since they're used for identity and encryption purposes?

That depends.
Private keys used for decryption you may want to be backed up. Note that the term "exportable" is probably taken from PKCS#11 used for HSM's and Smart Cards. And note that HSM's do often allow for secure backup, e.g. to another HSM.
As for signature generation: consider losing a smart card with a single key. In that case you may simply request a new card. The signatures can still be verified as long as the public key is available (and not revoked because the private key has been compromised).

If #2 is true, and there is no way to securely store extractable keys inside a browser, how do people build a secure app using WebCrypto?

I'm not sure about that. I must say that I find WebCrypto a pretty ill thought out API. To be honest, I think they just copied the exportability part from PKCS#11 / cryptoki.

Finally, isn't storing keys on the browser fundamentally insecure whether extractable or not? Even if the key cannot be exported, a website sign a message on behalf of the user (or decrypt a message intended for the user and send it to their server) without the user knowing, and that's a huge security issue.

The main issue with WebCrypto is establishing trust with the browser; that's nigh impossible even for the server providing the code and pages. Still, you could use it to encrypt with a public key. That could provide some protection against passive attacks against a past TLS session, for instance.


Where can I find Secp256k1 ECDSA test vectors? I`m currently implementing an ECDSA library based on curves like secp256k1. I would like to test it using some test vectors, like http://csrc.nist.gov/groups/STM/cavp/documents/dss/ecdsatestvectors.zip . Is there any place where I can get some vectors for testing encryption with that curve?

Example vector has this structure:

var testVectors = []struct {
msg    string
Qx, Qy string
r, s   string
ok     bool
}

and looks like this (for P224 curve):

{
    "96b2b6536f6df29be8567a72528aceeaccbaa66c66c534f3868ca9778b02faadb182e4ed34662e73b9d52ecbe9dc8e875fc05033c493108b380689ebf47e5b062e6a0cdb3dd34ce5fe347d92768d72f7b9b377c20aea927043b509c078ed2467d7113405d2ddd458811e6faf41c403a2a239240180f1430a6f4330df5d77de37",
    "851e3100368a22478a0029353045ae40d1d8202ef4d6533cfdddafd8",
    "205302ac69457dd345e86465afa72ee8c74ca97e2b0b999aec1f10c2",
    "4450c2d38b697e990721aa2dbb56578d32b4f5aeb3b9072baa955ee0",
    "e26d4b589166f7b4ba4b1c8fce823fa47aad22f8c9c396b8c6526e12",
    false,
},
{
    "86778dbb4a068a01047a8d245d632f636c11d2ad350740b36fad90428b454ad0f120cb558d12ea5c8a23db595d87543d06d1ef489263d01ee529871eb68737efdb8ff85bc7787b61514bed85b7e01d6be209e0a4eb0db5c8df58a5c5bf706d76cb2bdf7800208639e05b89517155d11688236e6a47ed37d8e5a2b1e0adea338e",
    "ad5bda09d319a717c1721acd6688d17020b31b47eef1edea57ceeffc",
    "c8ce98e181770a7c9418c73c63d01494b8b80a41098c5ea50692c984",
    "de5558c257ab4134e52c19d8db3b224a1899cbd08cc508ce8721d5e9",
    "745db7af5a477e5046705c0a5eff1f52cb94a79d481f0c5a5e108ecd",
    true,
},

I don't unfortunately know a good set of preexisting test vectors for this curve. Instead I decided to advice you how you can generate them yourself. Hope this helps.

Some (fairly recent) OpenSSL versions are familiar with secp256k1 curve. You may use e.g. OpenSSL's command line tool openssl's commands ecparam, ec, dgst to generate key pairs, parameter files, and ECDSA signatures using the curve.

If you do some scripting, you can even create files that appear similar than the the ECDSA test vectors from NIST/CAVP.

On the other hand, if you do not wish to force specific value for $k$ for testing  or use deterministic variant of ECDSA signing (see RFC 6979), then you may be better of trying this:

Validate your verification function with some pregenerated test vectors (containing both correct and incorrect signatures). Note: Remember to generate the vectors using some independent implementation (possibly e.g. OpenSSL).
Validate your signature function for compatibility with your verification function.


Given just the hash of a file, can I verify that the file contains a specific data block? Imagine I only have the hash of a file which we can call hash(file). Then a user sends me a data block (or section) of the same file, which we can call section1(file). Is there a way to verify that such section belongs to the file, given only the hash of it?

I was thinking of constructing a Merkle tree. So the hash(file) would actually by the Merkle root. However, to verify that a section belongs to the file I would need the entire Merkle tree (not just a single hash).

Any thoughts about proving that a file contains a specific data block? It doesn't matter which hashing methodology I use as long as I can verify it with little information.

Assuming that you know that $h_0$ is the root hash of a Merkle tree for the file, you can be sure that $h_1$ is a hash of a section of the file if you know that it's one of the hashes of the sections one level below the root and you know its sibling hashes, i.e. you have values $(h_1^1, \dots, h_1^{m_1})$ such that $\mathscr{H}(h_1^1, \dots, h_1^{m_1}) = h_0$ where $\mathscr{H}$ is the hash function used to build the Merkle tree. Because of collision resistance, if you have a preimage for $h_0$, it must be the right one, so the $h_1^k$ values are the hashes of the section at a level below.

More generally, you can verify that $h$ is a hash of a section of the file knowing the hashes of the siblings of that section, and the hashes of the siblings of its parents, and so on recursively up to the root. This requires the knowledge of $b \cdot n$ hashes where $n$ is the depth of the section and $b$ is the tree's branching factor. Note that you only need to be given the hash values, you don't need to trust them; they'll all be verified in the process.


NaCl allows decryption with the same public key as for encryption I followed the description here:

Public-key authenticated encryption: crypto_box

and created an example that encrypts a message with Bob's public key and signs it with Alice's secret key :

cipher = crypto_box(secret_string, nonce, bob_pk, alice_sk);

The cipher text can be decrypted and verified with Bob's secret key and Alice's public key:

message = crypto_box_open(cipher, nonce, alice_pk, bob_sk);

However, the message can also be decrypted with Bob' public key and Alice's secret key:

message = crypto_box_open(cipher, nonce, bob_pk, alice_sk);

This is somehow unexpected. I couldn't find much documentation for the crypto box. What is the math behind it?

My full code to reproduce:

#include <crypto_box.h>
#include <string>
#include <iostream>
#include <fstream>
#include <randombytes.h>
#include <string>
#include <iostream>

int main() {

    std::string alice_pk;
    std::string alice_sk;
    std::string bob_pk;
    std::string bob_sk;
    std::string nonce;
    std::string cipher;
    std::string message;

    std::string secret_string = "my secret string";

    unsigned char buffer[crypto_box_NONCEBYTES];

    randombytes((unsigned char*)buffer, crypto_box_NONCEBYTES);
    nonce.assign((const char*)buffer, (size_t)crypto_box_NONCEBYTES);

    alice_pk = crypto_box_keypair(&alice_sk);
    bob_pk   = crypto_box_keypair(&bob_sk);

    cipher = crypto_box(secret_string, nonce, bob_pk, alice_sk);

    message = crypto_box_open(cipher, nonce, bob_pk, alice_sk);

    std::cout << message << std::endl;

    message = crypto_box_open(cipher, nonce, alice_pk, bob_sk);

    std::cout << message << std::endl;

}

Alice and Bob's keys are used to compute a shared key.

Both parties compute the same key, which is used both encryption and decryption.

This is a traditional, hybrid encryption system.

Using only asymmetric cryptography for encryption would be painfully slow.

As a mitigation, the sender can create an ephemeral key pair, deleted right after the message has been encrypted. See ECIES or libsodium's crypto_box_seal() construction.


How can I obtain the raw decimal value of an RSA key's modulus? So maybe I'm thinking about this too hard, or maybe I'm missing a piece of information.

We'll use Google for this example. Say I wanted to obtain the modulus of Google's current public key.
Well I can do this relatively simply using OpenSSL:

  openssl s_client -connect www.google.com:443 | openssl x509 -text -pubkey

Great, so now I export that into a pem file. So now I have their certificate and their public key. Let's discard their certificate for this instance.
Also using OpenSSL, I can list the raw hexadecimal value of the modulus:

  openssl rsa -in pubKey.pem -pubin -text -noout

Now that lists this information:

Public-Key: (2048 bit)
Modulus:
    00:c3:d5:12:42:8a:36:02:f5:77:01:8b:f6:83:2f:
    ab:c5:c7:00:e4:c0:3e:94:33:3a:2e:7a:2d:37:30:
    c0:6c:75:67:d4:13:d0:30:b1:11:34:16:21:6f:95:
    99:b0:f6:31:3c:55:51:b9:3f:8c:c3:63:50:b9:d0:
    03:7f:bb:76:53:66:80:4e:3e:51:d6:77:e6:5c:f5:
    38:b1:19:88:7b:86:f8:2d:39:d0:12:4c:d0:6a:5e:
    37:f1:bb:22:47:ec:d8:08:ca:06:81:44:4b:11:ef:
    51:aa:e6:96:b8:ad:ed:6b:15:be:01:4b:bc:60:c9:
    df:42:0a:df:d3:8b:e5:b0:03:ac:18:ef:c3:f8:3a:
    96:5e:a6:77:61:fe:36:1e:f5:f2:aa:83:1f:69:d4:
    79:5d:69:a9:d9:a1:18:a2:98:cd:e6:3d:5b:1e:0f:
    a9:66:c8:42:f2:ba:b0:74:e8:5f:b3:b5:30:6d:79:
    a9:e8:9f:9c:23:5f:51:aa:36:2e:35:a7:9a:08:76:
    f9:46:f0:34:de:70:1a:3d:4e:f7:34:68:e4:43:75:
    bf:20:58:54:66:1c:9f:6d:9b:9d:28:21:15:ae:89:
    a7:e9:6f:75:7e:22:49:93:85:c6:a4:c5:2b:1a:23:
    92:f9:eb:8f:67:a8:26:56:e1:9f:66:e5:74:2a:01:
    0c:17
Exponent: 65537 (0x10001)

Great! I have the hexadecimally encoded modulus.
I've read many articles and have seen many websites that offer this, but, for future purposes, I'll just say that I don't necessarily prefer uploading keyfiles (public or private) to external services and "hoping" that they don't record it.

For experimental purposes, how might I obtain the plain decimal version of this modulus using a local client in Linux? I've seen a lot of posts showing that people have done it, but I'm having trouble figuring it out for whatever reason.

Also, I've heard a little bit about the prefixing "00" of this hexadecimal string (00:c3:d5:12:42...), about how it's just a bug. Can you give me more information on this, such as why it occurs and if it's relevant?

You've downloaded Google's (or whomever's) certificate. You have it stored in a file called GoogleCert:

$ cat GoogleCert
-----BEGIN CERTIFICATE-----
MIIIdDCCB1ygAwIBAgIIWOU4T7CaLpQwDQYJKoZIhvcNAQELBQAwVDELMAkGA1UE
BhMCVVMxHjAcBgNVBAoTFUdvb2dsZSBUcnVzdCBTZXJ2aWNlczElMCMGA1UEAxMc
...
JmztPlaPUkFUEnAL2aWCAQCHscxb9bMFDmUW/kv/UnBNBBX7PRvl5rPjPeFk9yS5
HU2vHiQa8VY=
-----END CERTIFICATE-----

Use the command openssl x509 -in FILENAME -noout -modulus argument to extract just the Modulus:

$ openssl x509 -in GoogleCert -noout -modulus
Modulus=AAC42564448507CB736A37F...9152FD0458ECF42145

Copy and paste the HEX output into BC using the ibase=16 argument to indicate the input is in Hex:

$ echo 'ibase=16;AAC42564448507CB736A37F...9152FD0458ECF42145' | bc
21557235071938158553153701887793754486919886530446620906710060142975\
...
80517225349695620402252397302295002436481842156355298655378997632358\
23941


How does this generate a permutation? In the process of trying to answer this question, I ended up getting stuck. I found a paper which seems to solve their issue: its authors define a process which yields a pseudorandom permutation generator $h$ when applied to a pseudorandom function $f$ and the resulting $g$ composed twice onto itself:

Let $f=\{f\}^n$ be a pseudorandom function generator where the key length function is $l(n)$. Define a function generator $g=\{g\}^n$ in terms of $f$ as follows. Let $k$ be a string of length $l(n)$, let $k'$ be a string of length $l(n+1)$, let $L$, $R$, and $L'$ be strings of length $n$, and let $R$ be a string of length $n+1$. Then $$g_{k}^{2n}(L\bullet R)=R\bullet[L\oplus f_k^n(R)]$$ $$g_{k'}^{2n+1}=R'\bullet[L'\oplus\text{first }n\text{ bits of }f_{k'}^{n+1}(R')]$$
…
Let $h=g\circ g\circ g$. … Theorem 1 shows that $h$ is pseudorandom if $f$ is pseudorandom… [however, note that] $h=g\circ g$ is not at all pseudorandom[.]

– Michael Luby and Charles Rackoff, How to construct pseudorandom permutations from pseudorandom functions.
However, as I'm implementing it, it seems not to be actually yielding a rearrangement of the input bits. I'll show an example where I provide an input with a hamming weight of 4, but it returns a string with a hamming weight of 15 -- so, clearly not a permutation of the input.

Parameters:

$f$ = SHAKE256
$m = 00001000\ 00000100\ 00000010\ 00000001$
$n = 32$
$l(n) = 0 \Rightarrow k = \text{‘’}$

So, going through it step-by-step:

$g_{k}^{n}(g_{k}^{n}(g_{k}^{n}(m)))$

$g_{k}^{n}(g_{k}^{n}(g_{k}^{n}(00001000\ 00000100\bullet 00000010\ 00000001)))$

$g_{k}^{n}(g_{k}^{n}(00000010\ 00000001\bullet[00001000\ 00000100\oplus f_k^{n/2}(00000010\ 00000001)]))$

Python: Crypto.Hash.SHAKE256.new(k).update(b'\x02\x01').read( (n//2) // 8 )

$g_{k}^{n}(g_{k}^{n}(00000010\ 00000001\bullet[00001000\ 00000100\oplus 10111101\ 00000101]))$

$g_{k}^{n}(g_{k}^{n}(00000010\ 00000001\bullet 10110101\ 00000001))$

$g_{k}^{n}(10110101\ 00000001\bullet[00000010\ 00000001\oplus f_k^{n/2}(10110101\ 00000001)])$

Python: Crypto.Hash.SHAKE256.new(k).update(b'\xb5\x01').read( (n//2) // 8 )

$g_{k}^{n}(10110101\ 00000001\bullet[00000010\ 00000001\oplus 10100111\ 01010000])$

$g_{k}^{n}(10110101\ 00000001\bullet 10100101\ 01010001)$

$10100101\ 01010001\bullet[10110101\ 00000001\oplus f_k^{n/2}(10100101\ 01010001)]$

Python: Crypto.Hash.SHAKE256.new(k).update(b'\xa5\x51').read( (n//2) // 8 )

$10100101\ 01010001\bullet [10110101\ 00000001\oplus 10000010\ 01010011]$

$10100101\ 01010001\ 00110111\ 01010010$

Since this has not yielded a permutation of $m$, how do the authors actually intend this composition to be done? Am I misinterpreting $\bullet$? Am I botching the composition? Should I be splitting $m$ differently? I did not see any special requirements on $f$ other than it be able to output $n$ bits (and even that looked non-strict, being croppable when an odd number of bits is required), so what am I missing here?

It is a permutation not in the sense that it permutes the bit positions of the given input, but in the sense that it is a one-to-one correspondence from a set (of bitstrings) to the same set, as defined in that paper:

2. Terminology …
Let $F^n$ be the set of all ${2^n}^{2^n}$ functions mapping
$\{0,1\}^n$ into $\{0,1\}^n$… Let $P^n\subset F^n$ be the set of such
functions that are permutations, i.e., they are 1-1 onto functions.


Backdoor in NIST elliptic curves Let $E$ be an elliptic curve defined over a finite field $F_q$ with prime order $n$ and $P,Q \in E$ and $k$ be private key such that $kP=Q$. Since $n$ is prime, $E$ is isomorphic to $Z_n$. Suppose $\psi$ be a map that
$$\psi:E \to Z_n$$

Also, let $a,b\in Z_n$ such that $\psi(P)=a,\psi(Q)=b$. Then we have:

  $$k=ba^{-1}$$

All recommended NIST elliptic curves(P-192,...,P-521,K-163,...) have prime orders.

Also When $\#E(F_p)=p$ we have polynomial time for computing such map. This is well known attack that is called anomalous curve attack.

What is the reason for confidence to them? Are computations speed enough?

Yes, the attack you sketched out would work - in theory.

In practice, it's an efficient (computable in polynomial time) mapping $\psi:E\rightarrow\mathbb Z_n$ we're lacking. As for the unefficient mappings, $\psi:x\cdot P\mapsto x$ would be perfectly fine theoretically, but we don't know how to calculate it (it's the elliptic curve discrete logarithm problem, aka ECDLP).

Furthermore you might say: "well, we can construct an isomorphism in theory, so why don't we just map it somehow and apply the GNFS on $\mathbb Z_n$?" The problem is again, that we don't know an efficient mapping and even if we would, we would need one (for this attack) that preserves birational equivalence to transfer addition laws from one group to the other and if such a mapping would exist, people probably would have found it in ECC's 25 year(+) history.

Bottom line: The DLP isn't hard because of the elements you want to find, it is hard because of the element's representation.


What's efficient MPC protocol for determining if sum's bigger than y? My secure multi-party computation (MPC) in need is simply to determine if a sum of two private variable is bigger than a given value $y$, as

$f(x_0, x_1) = [(x_0 + x_1) > y]$

in which the value of sum itself (i.e., $x_0+x_1$) is deemed private and $y$ is publicly known. The output of this function is yes or no.

I am aware of many MPC protocols out there, mostly based on boolean circuit (as in Yao's protocol) or arithmetic circuit. But I have no experiences of benchmarking these protocols, and I want to ask which (existing) protocols are more suitable for my computation?

Update: based on the answer from @mikeazo, arithmetic circuit is good at addition and boolean at comparison. Since my function $f(\cdot)$ involves with both, so the question is really which out of these two circuits can do both (comparison and addition) better?

Update2: I am also thinking if possible to decompose $f(\cdot)$ into separate parts, one for comparison and one for addition. And use different/corresponding circuits for each part. Is it such adaptive framework out there that can do this?... maybe this way, it can be even more efficient.

The answer is definitely yes. You should be able to do what you are looking for. The computation is very simplistic, so using existing MPC protocols will be efficient. Many of the existing protocols are able to evaluate a few blocks of AES using MPC per second, so this computation will be no problem.

Typically MPC works by translating your function into a circuit (either boolean or arithmetic). In the 2 party case, you are probably best off using Yao's approach. There are newer constructions that you could use and that would probably still be efficient, but they do use some heavy public key crypto and I'm not aware of any publicly available implementations. For Yao's approach, I'd recommend the MightBeEvil framework. I believe Yao's approach is most commonly (if not always) used with boolean circuits. Another option is Fairplay.

In the multi-party case (more than 2 parties), garbled circuits won't do (at least not with publicly available implementations). Your options here are really Viff and Fairplay-MP. Viff uses arithmetic circuit representations while Fairplay-MP uses boolean circuits. Viff has a specialized protocol from Toft for comparison to help mitigate some of the problems with comparison in arithmetic circuits (more on this in a moment).

Adversary Model
You don't mention adversary model in your post, but I thought I'd say a little on this. You have 3 choices in the literature: semi-honest (or honest-but-curious), covert, and malicious (or Byzantine). Fairplay, Fairplay-MP, and MightBeEvil all only support semi-honest adversaries while Viff has support for both. Theoretically any of Fairplay, Fairplay-MP and MightBeEvil could be made to support malicious adversaries, but they don't out of the box and would require significant work (not to mention publishing to make sure you didn't make any mistakes).

If you are not familiar with the difference, semi-honest assumes that corrupt parties will follow the protocol as specified and only use information gleaned during the execution to violate privacy. Malicious makes none of these assumptions (parties can deviate all they want from the protocol and will always be caught, caught with overwhelming probability). I am not aware of any implementations available publicly that support covert adversaries. FYI, a covert adversary is one who will deviate but doesn't want to be caught, so you only have to define the protocol such that the probability of catching a deviating adversary is high (as opposed to overwhelming).

Boolean vs Arithmetic
Both approaches have their strengths and weaknesses. In arithmetic circuits, addition is cheap but comparison is much more expensive. The opposite is true in boolean circuits. I believe that, for example, in the MightBeEvil framework, they have built in circuits for say a 32 bit adder but not a 2000 bit adder. Thus, input size will make a difference here. On the arithmetic side, you only have to define the underlying field large enough to support the input size. This will have an effect on performance, but not as large as in the boolean circuit approach.

Comparison in boolean circuits is relatively easy. Simply start with most significant bits and compare the bits using a single bit comparison operation. Scan from MSb to LSb, stopping when a difference is found. Whoever has the 1 bit in this case is the larger of the two. On the arithmetic side, things are more complicated which is why Viff uses a specialized protocol from Toft. For small input sizes, it probably won't make a huge difference.


RSA Accumulators with auxiliary information or known trapdoor information In "Universal Accumulators with Efficient Nonmembership Proofs" by
Jiangtao Li1, Ninghui Li2, and Rui Xue3 section "How to compute witness with the auxiliary information" the authors write:

"The membership witness and nonmembership witness can be computed efficiently given the auxiliary information $aux_f$. Suppose there is a trusted group manager who knows $aux_f$, maintains the set $X$, and has already computed the accumulator $c = f(g, X)$, the group manager can compute (non)membership witness for any $x \in X_k$ with one short modular exponentiation.

For $x \in X$, the group manager first checks whether $x \in X$, then computes
$a = x^{−1} \bmod \phi(n)$, and finally computes $c_x = c^{a} \bmod n$. The membership witness for $x$ is $c_x$. It is easy to verify the correctness of the witness as $(c_x)^x = (c^a)^x = c^{x^{−1}·x \bmod \phi(n)} = c \bmod n$."

When I try to apply this I always get membership in the accumulator as true, even when the tested number is not in the accumulator.

Example:

$$
c = g^{x_1 x_2 \cdots x_k} \bmod n
$$

According to the authors I should calculate the witness of $p$ (a prime number) as:

$$
c_p=c^{p^{−1}mod \phi(n)} \bmod n
$$

Then check if $(c_p)^{p} = c$.  This is always true if $p^{-1}$ exists. As per the proof presented by the authors, even when $p \notin X$.

On the other hand if I store the full exponent of accumulator $c$ as $e = \prod_{i=1}^k x_i $ I can test if an element is a member of the accumulator or not by calculating:

$$
w_p = g^{e / p \mod \phi(n)} \bmod n
$$
$$
c' = (w_p)^p \mod n
$$

$$
  isMember(p) = \left \{
  \begin{aligned}
    &\text{true}, && \text{if}\ c'=c \\
    &\text{false}, && \text{otherwise}
  \end{aligned} \right.
$$

This works but I have to store the full exponent $e$ instead of just storing accumulator $c$ and using trapdoor $\phi(n)$ to calculate witnesses on the fly.

What am I doing wrong? How can I use the knowledge of the accumulator's trapdoor to calculate valid membership, or non-membership, on the fly just by knowing the accumulator's value $c$?

For the inclusion proof you might need the trapdoor or the accumulated set. The exclusion proof can be generated without knowing the trapdoor. See this related question and answer.

How can one generate inclusion proofs if knew the trapdoor, i.e. the factorization of $N=p\cdot q$?

Let's $A$ denote the accumulator's value, $x$ be an item to-be-accumulated and $N$ the modulus whose factorization is known.

Generating a valid membership proof for an item $x$ essentially means taking $x$-th root of $A$ $\mod N$. Since you know the factors of $N$ you can just compute $x$-th root $\mod p$ and then $\mod q$ and afterwards compute the $x$-th root $\mod N$ by applying the Chinese-remainder theorem for moduli $p,q$.

Note, that computing efficiently arbitrary roots mod a prime is simple. See, for instance, here.


One-time pad with public key changes Let $k$ by a randomly generated $n$ bit string, and $m$ a $n$ bit message.  Then putting $c = m \oplus k$ is the one-time pad and is perfectly secure.  Now assume the transmitter and receiver wanted to share more messages: then they could publicly choose a random $n$ bit string $b$, and then by putting $k' = b \oplus k$ they have obtained a new random key, which they can again use to encrypt a new message $m'$ with perfect secrecy.

I am wondering why such a cipher is not used?  The only reason I can think of is that if the attacker obtains a single plaintext message, they can decrypt all past and future messages which is clearly not good, and thus the reason it is not used.  Are there any other reasons I am missing?

Further, couldn't this be used to create a random bit generator?  That is, the seed is a random $n$ bit string, and the publicly known generator will XOR $k$ random but publicly known $n$ bit strings with the seed $k$, to generate a random sequence of length $kn$.  Naturally, the reason I am assuming this is not a good random number generator is that, again, if the attacker learns the internal state they can obtain all past and future bits.  Are there any other reasons this is not good?

As @kelalaka pointed out OTP is not “differentially secure”. In addition it has the property, like all additive ciphers which work by modular addition of a keystream, that the keystream and the plaintext have symmetric roles.

What I mean is your suggestion to add the string $b$ to the key $k$ is essentially equivalent to the weakness resulting from reusing plaintext as in VENONA.

The constant $b$ is visible to differential attacks, such as crib dragging. In this case, it is the keystream that is differentially deficient.


AES with linear S-Box If the AES S-Box is replaced with a linear or affine transformation, for instance the identity mapping $\sigma(x)=x$, does the cipher become entirely affine and hence trivially weak?

does the cipher become entirely affine and hence trivially weak?

Yes; the AES sbox is the only source of nonlinearity (the ShiftRows and MixColumns are linear, and AddRoundKeys for a fixed key is affine), and so if you replace it with a linear/affine one, the entire cipher becomes affine.


Is it possible to guarantee a SHA-256 hash will begin with a certain 3 bytes? I've found this online currency someone has built as a project and it's "miner" / Proof of Work algorithm is as follows:

Generate 32 bytes of random data and hash it, store the original value and the hash
Test if the hash begins with a "server key" which is the 3 bytes the hash has to begin with to be valid
Submit the value to the server and it will award you with some of the currency and change the server key if the value that you sent's hash begins with these first 3 bytes.

Since a SHA-256 hash is 32 bytes, and I would only need to guarantee the first 3 bytes to mine the currency, would it be possible to get values that produce a hash with these first 3 bytes, but faster than just random hashing?

Cryptographic Hash functions are deterministic random functions. Deterministic means the same input the same output and random in a sense mean that the output is unpredictable. We expect that the hash functions have avalanche effect that whenever one bit complemented from the input, each of the output bits flips with a 50% probability.

If it is possible to find a specific first 3-byte faster than the hashing random inputs this actually means that someone found a weakness in the hash function. There is no known such weakness in the SHA-256.

Note: By the design of the SHA-256 (or the family), even there is a non-random method for the first 3-byte, with high probability, the other bytes will have, too.


Are there deterministic private-key encryption schemes that are CPA-secure? I'm assuming there can't be such schemes because CPA-security is equivalent to CPA-security for multiple encryptions, and
an adversary can distinguish between $(\mathsf{Enc}_k(m_0),\mathsf{Enc}_k(m_0))$ and $(\mathsf{Enc}_k(m_0),\mathsf{Enc}_k(m_1))$ if Enc is deterministic, hence there is no deterministic symmetric encryption scheme that is CPA-secure.
However, I can't see how an adversary might distinguish only one encryption from another.

The CPA indistinguishability experiment $\mathsf{PrivK}_{\mathcal A,\Pi}^{\mathsf{cpa}}(n)$:
Let $\Pi = (\mathsf{Gen}, \mathsf{Enc}, \mathsf{Dec})$ be any encryption scheme, $\mathcal A$ any adversary, and $n$ the security parameter.

A key $k$ is generated by running $\mathsf{Gen}(1^n)$.
The adversary $\mathcal A$ is given input $1^n$ and oracle access to $\mathsf{Enc}_k(\cdot)$, and outputs a pair of messages $m_0$, $m_1$ of the same length.
A uniform bit $b \in \{0, 1\}$ is chosen, and then a ciphertext $c \leftarrow \mathsf{Enc}_k(m_b)$ is computed and given to $\mathsf A$.
The adversary $\mathcal A$ continues to have oracle access to $\mathsf{Enc}_k(\cdot)$, and outputs a bit $b'$.
The experiment is defined to be $1$ if $b' = b$, and $0$ otherwise.

Definition of CPA-security:
A private-key encryption scheme $\Pi = (\mathsf{Gen}, \mathsf{Enc}, \mathsf{Dec})$ has indistinguishable encryptions under a chosen-plaintext attack, or is CPA-secure, if for all probabilistic polynomial-time adversaries $\mathcal A$ there is a negligible function $\mathsf{negl}$ such that
$$\text{Pr}[\mathsf{PrivK}_{\mathcal A,\Pi}^{\mathsf{cpa}}(n) = 1] \leq \frac{1}{2} + \mathsf{negl}(n),$$
where the probability is taken over the randomness used by $\mathcal A$, as well as the randomness used in the experiment.

Summarizing fkraiem's comment, a CPA-secure encryption scheme can not be deterministic.

The reason is simple: the attacker is challenged to distinguish between the encryption of $m_0$ and $m_1$, but he also has access to an encryption oracle (and he can query the oracle at whatever input he wants!). If the encryption scheme yields the same ciphertexts each time it's queried on the same plaintexts, the attacker can simply ask the oracle for an encryption of $m_0$ and an encryption of $m_1$, and compare which one is equal to the given challenge ciphertext.


Solving a discrete logarithm using GDlog I am trying to calculate an $x$, such that $t = g^x \pmod p$ in order to crack a weak ElGamal encryption for university.

I found GDlog, but I cant figure out how I can use the input to calculate my $x$.

Here is what we got (from gdlogs example code):

p:1000000000000000000000000000057 //prime number, modulus
q:290240017                       //(p-1)/2
g:5                               //generator
t:519335238006017621936447751736  //member of the group

GDlogs result: Logarithm of the 519335238006017621936447751736 to the 5 is 142363323.
My question is: What is the number that GDlog outputs (142363323)?

This is what is written in the README:

  Find $0 \le x < q - 1$ such that $g^{x (p-1)/q} \pmod p = b^{(p-1)/q} \pmod p$ (assuming that such $x$ exists).

But I still can't figure out how to do it.


Is the MD5 algorithm only useful for bytes, rather than bits? The MD5 algorithm is designed to accept a message of any length and produce a 512-bit message digest. Because of the way it pads the original message, by adding a 1-bit then a number of 0-bits, the length of the message can be any number of bits. It is not limited to an integer number of bytes. But it can also be written to work only in bytes, so the padding stage would involve adding a 0x80 byte then a number of 0x00 bytes. The end result is the same, as long as the input data is an integer number of bytes.
However, my understanding is that data is almost always stored in bytes. This is especially the case for character strings, where each character is represented by at least 1 byte. For this use case, I believe a byte-oriented approach would work fine. But if I wanted to write an MD5 implementation that also accepts files, does the bit/byte distinction become important? Would I need to write the algorithm to deal specifically with bits, or would a byte-oriented implementation work just as well for strings (e.g. from STDIN) and files?
In other words, is data always stored as whole bytes? And if so, what applications are there in which one would need to write an MD5 algorithm that uses individual bits, rather than whole bytes?

If I wanted to write an MD5 implementation that also accepts files, does the bit/byte distinction become important?

No, a byte implementation is fine. In modern OSes, hashing from a file, pipe, string (whatever the encoding) is hashing bytes.
The only times I made and used an implementation of a hash with bit support was to make or check test vectors. But I can imagine a few use cases that would require bit support

hashing the expression as a minimum number of bits of an integer (per some specified endianness), for an hypothetical algorithm specifying that.
one wants a few variants of MD5, and obtains these by appending a suffix shorter than a byte to a bytestring fed to MD5. For 15-byte messages that makes a computational saving compared to appending a whole byte (one internal padded message block of 32 bytes rather than two), plus avoids trivial collisions with regular MD5.


Can Pre-Paid Cards be cracked? Is it possible to deduce the original function that used to generate those prepaid cards number that are used for charging your mobile phone credits?

For example: If I've collected about 1000 of those cards, how can I analyze those numbers so that I can re-generate the generated numbers again using my own software?

If the people who generated the pre-paid card numbers did their job properly, then no, it is not possible to reconstruct these numbers.

The simplest pre-paid card number generation system is to use purely random numbers, and store generated numbers in a database. To verify a generated number, simply look it up in the database. The function which can then rebuild the numbers is the RNG -- if that is /dev/urandom from a Linux/*BSD/MacOS/Solaris system, or CryptGenRandom() from a Windows system, then there is no known weakness which would allow an attacker to merely recognize the RNG as being that specific system (as opposed to, say, someone flipping a coin repeatedly), let alone predict the next number with a non-trivial probability of success.

The method with random numbers and a database has two main drawbacks:

You can get collisions. E.g., if you use 16-digit numbers, you can expect to reach your first collision after 108 (100 millions) generated numbers. You can deal with that by checking your generated numbers against the database, but this can make the industrial process more complex (i.e. you have to talk to the database before deciding whether the card is worth printing).
Each number verification entails a database lookup. With millions of customers, this may imply an heavy load, especially if there are people who routinely try random numbers, just in case they get lucky (apparently, people do that). Database access is unavoidable at some point, if the card is genuine (if only to update the customer account), but one would prefer to have a lighter way to filter out most invalid card numbers.

So a slightly more complex method involves symmetric encryption. Namely, you use a block cipher operating over the space of $n$-digit integers. So you have a secret key $K$; let $E_K$ be the encryption function, and $D_K$ the decryption. You keep a counter $c$ of generated card numbers. To get a new card number:

Increment $c$.
Encode $c$ into a sequence of $m$ digits and pad it with $n-m$ zeros.
Encrypt the whole thing with $E_K$.

Then, when it comes to verify a number, try first decrypting it with $D_K$: if the result does not end with $n-m$ zeros, then you know that it is not a genuine number, and can be rejected without involving the database. This method also guarantees the total absence of collisions.

The tricky part in this method is having the appropriate $E_K$ / $D_K$ function. It must be a pseudo-random permutation; anything like a stream cipher is inadequate (including AES in CTR mode). If the number length ($n$) is 19 or less (but close to 19), then this is easily done with a 64-bit block cipher $B$ such as IDEA or the venerable 3DES (apparently, the IDEA patents expired, which is why it becomes recommendable again). Then, to encrypt a sequence $d$ of $n$ digits:

Encode $d$ into 64 bits (interpret $d$ as an integer, write down the value in binary); call $x$ the resulting sequence.
Set $x \leftarrow B_K(x)$ (encryption with the 64-bit block cipher).
Interpret $x$ as an integer value $e$.
If $e ≥ 10^n$, loop to step 2. Otherwise, define $E_K(d) = e$.

In plain words, we use the block cipher repeatedly until it gets us back to the appropriate space of integers between $0$ and $10^n-1$. If the block cipher is a secure pseudo-random permutation, the this process is also a secure pseudo-random permutation. The average number of iterations will be $2^{64}/10^n$; for instance, with $n = 16$, this will require on average about 1845 invocations of the underlying block cipher: a very small amount, since a cheap PC can do millions of those per second, with a single core.

With this method, predicting valid numbers with success probability higher than $10^{m-n}$ would require breaking the 64-bit block cipher (that is, there mere existence of such a predictor would be viewed as an unredeemable weakness of the block cipher). So, with IDEA or 3DES, no worry. With practical figures: with $n = 16$ (16-digit card numbers) and $m = 11$ (you have room for one hundred billions of valid numbers), then only one random number in 100000 will require actual database lookup.

If $n$ is much smaller (e.g. $n = 12$), the computational cost can become excessive, but the core principle can still be applied, provided that you design a custom block cipher which runs over sequences of digits -- this is a difficult task (don't do this at home ! I.e., do not deploy such a system in production without getting some professional advice from a trained cryptographer), but there are existing tools (see this question for details).


How can I calculate the time complexity of modular arithmetic? I'm doing modular arithmetic in a Java program, and I want to calculate the time complexity of the individual operations.

$$ c= a · b \bmod n $$
$$ m = a^{-1} · b \bmod n $$

How do I get an approximation of the time complexity here, for example for 256-bit numbers?

I'm turning earlier discussion into a partial answer. I apologize if the whole thing can be considered off-topic (we are discussing computer science, with specialization to Java, and only potential application to cryptography).

In order to discuss time complexity, we must specify the algorithm used, and that's not done in the question. However, in Java, an easy and customary way to perform integer arithmetic on numbers of 256 bits is to use the java.math.BigInteger package. Its source code is supplied with the public JCDK, in src.zip, allowing analysis. The algorithms used by this package to compute $a⋅b$, then $a⋅b\bmod n$, are essentially the so-called classical algorithms taught in primary school with base 10, only adapted to base $2^{32}$; see e.g. multiplyToLen in BigInteger.java where the actual computation of $a⋅b$ occurs.

Assuming that implementation is used, and $a$, $b$ and $n$ are of the same order of magnitude, the asymptotic cost of computing $a⋅b\bmod n$ is going to be $O(\log(n)^2)$. More precisely, I expect the number of long multiplications to be $o(2⋅(\log_2(n)/32)^2)$, and that goal is reachable by a good Java implementation of the classical algorithms, which java.math.BigInteger seems to be.

Unless something clever is done, computing $m=a^{-1}·b\bmod n$ will be by first computing $i=a^{-1}\bmod n$ (perhaps using modInverse in BigInteger.java), then $m=i·b\bmod n$. Assuming that, the asymptotic cost is going to be at least that of the second part, which was discussed above. I suspect $i=a^{-1}\bmod n$ might cost appreciably more than $m=i·b\bmod n$, even asymptotically, but my time is missing right now for a detailed analysis; I stopped after determining that the core of the computation is by mutableModInverse in MutableBigInteger.java, and this is not quite a straightforward Extended Euclidian algorithm.

Caveat: Given that a 256-bit integer uses only eight 32-bit words/digits/limbs, asymptotic cost, be in in $O()$ or $o()$ notation, likely is a poor predictor of the actual runtime; that might be dominated by non-computational overhead, especially in Java.

Edit: As references, I suggest the HAC (esp. chapter 14), and Modern Computer Arithmetic.


How to break RSA signature on XOR of hashed blocks I'm trying to figure out if there's a way of breaking or weakening the following method of signing long messages

Given $M=m_{1}m_{2}...m_{n},\,\,|m_i|=64b,
\,\,h=h(m_{1})\oplus h(m_{2})\oplus\cdots\oplus h(m_{n})$

sign $h$ using the RSA method.

also, is it weaker than the original way (of signing every message separately)?

To sign a message $M = m_1 \ldots m_n$, you calculate $h(M) = h(m_1) \oplus \ldots \oplus h(m_n)$ then $S(M) = \textsf{RSASSA}(h(M))$ where $\textsf{RSASSA}$ is some RSA-based signature mechanism. $h$ is presumably a cryptographic hash function. You're looking for a weakness of this signing method.

Start small. Given $M = m_1 m_2$, can you think of another message $M'$ such that $S(M) = S(M')$? (Note that a weakness could be more complicated than this. For example, it could be impossible to find two messages with the same signature, but possible to derive the signature of $M'$ from the signature of $M$. However, in this case, it is possible to forge another message with the same signature.)

   $S(m_1 m_2) = \textsf{RSASSA}(h(m_1) \oplus h(m_2)) = \textsf{RSASSA}(h(m_2) \oplus h(m_1)) = S(m_2 m_1)$

Follow-up exercise (easy): given an arbitrary message $M = m_1 \ldots m_n$, find a longer message with the same signature. Hint:

   Above I used the fact that $\oplus$ is commutative. What other algebraic properties does $\oplus$ have?

The normal way to sign a message $m_1 \ldots m_n$ is of course $\textsf{RSASSA}(h(m_1 \ldots m_n))$. If you also want to be able to verify the signature of one part independently, one solution is to build a hash tree and sign the root hash. A two-level hash tree would be $h(h(m_1) \ldots h(m_n))$. If you transmit the signature $\textsf{RSASSA}(h(h(m_1) \ldots h(m_n)))$ as well as the list of individual hashes $(h(m_1), \ldots, h(m_n))$ then it's possible to verify the signature of any of the individual $m_i$. Signatures are larger than hashes and more expensive to compute, so this can save resources compared so signing each $m_i$ independently.


Subkey generation in OMAC1/CMAC with XTEA? All implementations of CMAC that I have found so far use a block cipher with the same key and block size. However, XTEA enciphers a 64 bit block by using a 128 bit key.
If E_XTEA(key,block) is the encipher function and k is my main key, CMAC produces a temporary key k0 from an all-zero block:

k0 = E_XTEA(k,0)

CMAC derives two other keys from k0 with the same length as k0, k1 and k2.
This derivation uses a constant C which is "completely determined by the number of bits in a block"

There are two problems:

k is 128 bit long, but k0,k1 and k2 are only 64 bit long because they depend on the output of the 64 bit encipher function.
Is C really determined by the block size instead of the key size?

My assumption is that E_XTEA(k,0) is used to generate a pseudo-random block, and I can use k0 = concat(E_XTEA(k,0),E_XTEA(k,1)) to generate a pseudo-random block of the right size. But I don't know if this is correct  or which C to choose.

Look at how the keys $K_1$ and $K_2$ are used in CMAC (pdf, Section 6.2):

  If $M_n^*$ is a complete block, let $M_n = K_1 \oplus M_n^*$; else, let $M_n = K_2 \oplus (M_n^*||10^j)$, where $j = nb-Mlen-1$.

They are combined with message blocks using XOR. So they must be equal in length to the block size, not the key size (if different), of the cipher.

Similarly, then, $C$ is determined by the block size.


Is it OK to use a secret IV as key when creating keyed MD5 checksum for fixed-size data? Is it OK to use a secret IV as key when creating keyed MD5 checksum for fixed-size data?

Because data size is known, attacker cannot append anything. And I think it's hard to raise chosen-plaintext attack if the secret is well kept, but I’ld like to be sure.

So the idea is to use the IV of MD5 as a key to create a MAC. Like CodesInChaos mentions in a comment, it would be pretty much equivalent to using $H(k||m)$, if your IV is randomly chosen.

By only using it on fixed length messages you avoid the length extension attack, but that is not the only attack on hash constructions that try to create a MAC. In this question on $H(k||m||k)$ the answer provides links to an attack that uses internal collisions (pdf, Proposition 4):

  This means that an attacker can replace or delete $w \le s$ trailing blocks, and that the attack is applicable even if the input is of fixed length [...]

It can also be applied here. So, no, it would not be secure. At least strictly speaking: the attack requires seeing $2^{n/2}$ authenticated messages, though a smaller amount could allow an attack with some probability.

You should use HMAC or another standard MAC instead. I would also consider a more secure hash than MD5, if you use a hash based MAC, even though the attacks known for MD5 are not sufficient to break HMAC.


Why is an IV used in Merkle–Damgård transform? In Merkle–Damgård  transform, a fixed vector IV is chosen at the beginning, and it is hashed together with the first block x1. I wonder why we don't use x1 straightforward, i.e. hash x1 and the next block x2 at the very beginning.

In most Merkle–Damgård hash functions, it uses a block cipher in the compression function, with the inputs being the padded message blocks and the IV.

The IV is the fixed width input plaintext to the cipher, and the message becomes the key. The hashing of the input block x1 works by expanding it (using a key expansion) so that there are as many subkeys as there are rounds (for SHA at least, this may/will vary with other hash functions). Then the IV is encrypted over $N$ rounds using the compression function. Wikipedia has a nice image that gives a general high level overview of this.

In SHA2 hashes, the compression function is an unbalanced Feistel network that encrypts 2 of the 8 words of the IV using a single subkey and a round constant during each round. Once all the rounds have completed, the output of the block cipher becomes the plaintext input for the next block x2, and so forth until all blocks have been used. The output of the cipher then becomes the hash value, truncated if necessary.

SHA256 uses 32-bit words and 64 rounds, with 512-bits of message being expanded to 2048-bits of subkeys. SHA512 uses 64-bit words and 80 rounds, with 1024-bits of message being expanded to 5120-bits of subkeys.

Without a specified IV, the block cipher may output results that follow a pattern, since it is not an ideal cipher. Most hash functions use IVs based on irrational numbers, which generally have a fairly balanced hamming weight, while also not being part of a defined pattern. SHA1 uses the initial values from MD4, which are not irrational or random, and are built from a very specific pattern, but have an average hamming weight of $1/2$ per bit.


Any real world implementation using message recovery? During my master thesis I came across RSA-PSS-R which is in my opinion a quite elegant way of saving bandwidth and space using digital signature.
But I didn't find any information about any real world implementation out there. I have the feeling that it's exactly like the Schnorr Signature scheme. Everybody says that it is very efficient, but no one actually uses it.

Maybe I didn't dig deep enough but is there anyone out there actually using message recovery AT ALL in any real world implementation?

Thank you for your feedback

A signature scheme with message recovery is standardized as ISO/IEC 9796-2 (link to preview). Scheme 1 in this standard is commonly used in the Smart Card industry, despite its known weaknesses in a chosen-message setup.

Example real-life uses include the EMV banking application (the free documents linked there include a description of an industry-standard subset of ISO/IEC 9796-2 Scheme 1; there is support for this subset in JavaCard 2.2.2 and up); and the certificates in the European Digital Tachograph system (head to Annex 1B, appendix 11).

Update: As kindly pointed by Maarten Bodewes, that is also used in ICAO e-passport specifications, appendix 4.


What's the reason for Monte Carlo tests for block ciphers? NIST specifies that implementations were required to create Monte Carlo test vectors for ECB and CBC mode for the AES competition.

What's the reason for these tests? The only thing I can think of is that it is some randomized testing of the block cipher in specific modes. However, in that case the difference between ECB and CBC would not matter.

It seems to me that this is a weird way to test for implementation errors. You'd expect things like bounds checking and such, but just performing the encryption over and over again may not actually hit the right results. And weird keys / input values are also covered by the other tests.

Finally, having the algorithm generate it's own input seems dangerous. If the block cipher doesn't behave as specified, then the input may be erroneous. So why use the block cipher as DRBG and not another well specified / tested algorithm?

As usual, government departments simply repeat their existing rules.  So they incorporated the Monte Carlo tests from earlier test documents, this time from 1980.   If you follow the dusty trail from Maarten's link, you eventually arrive at NBS Special Publication 500-20, Validating the Correctness of Hardware Implementations
of the NBS Data Encryption Standard.  These are the two relevant extracts.

  This publication describes the design and
  operation of the NBS testbed that is used for the
  validation of hardware implementations of the
  Federal Information Processing Data Encryption
  Standard (DES).

and

  Since the test set is known to all, an additional
  series of tests is performed using pseudo-random data to
  verify that the device has not been designed just to pass
  the test set. In addition a successful series of Monte Carlo
  tests give some assurance that an anomalous combination of
  inputs does not exist that would cause the device to hang or
  otherwise malfunction for reasons not directly due to the
  implementation of the algorithm. While the purpose of the
  DES test set is to insure that the commercial device performs the DES algorithm accurately, the Monte Carlo test is
  needed to provide assurance that the commercial device was
  not built expressly to satisfy the announced tests.

So it is there to test  future hardware implementations of AES.


Private key ECDSA/TLS Is the private key required once the certificate is hashed and signed? After a certificate is generated, public key is shared within the certificate itself. Is the private key used for any other purpose within the handshake or certificate validation?

Is the private key required once the certificate is hashed and signed?

That of the CA that issued the certificate? No. That of the end entity you are trying to communicate with? Yes. The whole point of a certificate is to create a binding between an entity (eg a website) and a public key, so that by proving ownership of the associated private key somebody (the entity) can confirm to be the entity named in the certificate.

  Is the private key used for any other purpose within the handshake or
  certificate validation?

Again, the CA's private key: No. The end entity's private key is used to sign a specific part of the handshake (usually the ephemeral ECDH public key) so that the party knows that said part really originated from the entity named in the certificate and that they are connecting to that entity which then also knows the negotiated symmetric keys.


Stern identification scheme to signature scheme I'm trying to understand the comment in the page 103 of the book Postquantum Cryptography. about convert the identification Stern procedure for signing. Can you write an example of signature of this conversion?

  The standard method to convert the identification procedure into a procedure for signing, is to replace verifier-queries by values suitably derived from the commitments and the message to be signed.

In order to convert a 3-move id-scheme to a digital signature you have to replace the request (or the challenge) by the value of a secure hash function applied to the message (this method is called Fiat-Shamir method).

In Sterns's id-scheme you have to choose a random element from the set $\{0,1,2\}$ for your message. That is $H(m)\in \{0,1,2\}.$ For  instance if you have $H(m)=0$ then the signature of $m$ is $(c_1,\Pi).$

EDIT : Before you convert it, you have to run the id-protocol many times, say 64 or 80 times, and then apply Fiat-Shamir method.


Transferable ownership certificate Is there a crytpographic way to assert ownership of an asset (let's say a piece of stone)?

As an example, a number (public key) could be engraved in the stone, and the owner could keep a private key (never shared).

Anyone who wants to claim for ownership would have to decrypt a message, and only the one who has the private key can do it.

But one more thing: the ownership should be transferable. Here is the problem with the previous system: if the owner A sells the object to owner B, owner A could secretely keep the private key when he gives it to owner B.

What are the general cryptographic solutions for this? (except blockchain which is a famous solution nowadays, that I already know)

For the sake of simplicity, I assume that every party can be identified by a keypair (e.g. Alice has a public $A_{p}$ and a secret $A_s$) and every asset by an identifier (a hash for example).

Let us say it is "known" that Alice owns a certain property identified by $P$, either because she created it and registered the identifier somewhere, or she claimed it, or got it from someone else (we don't care). A way that she could transfer the ownership to Bob (with keypair $B_p, B_s$) is to make a statement that is semantically equivalent to:

I, Alice, transfer the ownership of [P] to the person holding the key [B_s].
The current date is [Mon 30 Oct 17:27:18 CET 2017].

She then signs the statement with her private key $A_s$ and gives it to Bob. Then, if anybody contests whether Bob actually owns $P$, he can show the signed statement and thus prove that he owns $P$.

There is only one drawback to this system, which is that Alice could transfer the ownership more than once. This is because she can just write another statement with an invalid date, which looks (as long as we never have seen Bob's statement) to be valid all the same.

Therefore, we will always need to broadcast transfers of ownership. There are multiple ways this can be done. For example, Bob could put the hash of the statement in a widely distributed newspaper. Then he could later point back to prove that the statement indeed existed at the moment the newspaper was printed. To retract this Proof of Existence (PoE) you would need to get your hands on all the prints of the newspaper, which is probably not feasible.

We could (as you mention) also publish the statements in a blockchain (this is what Bitmark does), such that the distributed nature of the blockchain makes it impossible to retract a statement.

A third way is to use a trusted third party. The Time Stamping Protocol defines CA's for signing PoE's for users. On Twitter, you will sometimes see cryptographers publishing proofs of existence for articles/knowledge that they are not (yet) allowed to publish. In this case, Twitter is the trusted third party (because we all trust Twitter not to allow a person to tweet in the past).


Decently safe amount of AES key derivation? I am encrypting my computer using Veracrypt. The default 500,000 derivations is quite slow, what would a "safe" balance be between security and speed? My password is more than 20 characters.

VeraCrypt tries each hash and cipher combination with your supplied password if PKCS5-PRF is set to auto-detection on the enter password screen, i.e. it will try all. It will work until one of them work. It can do this in parallel. In the end, if none is working it will inform you that your password is incorrect.

Change it to the PKCS5-PRF that you selected during the setting the volume, it will not test the others. That will decrease the time.

In the attacker's eye, this will slow them, since they have to try all for each candidate passwords during brute-forcing possible passwords.

Also, the 500,000 derivations is important against the password crackers. The higher the better and it will affect the attacker's time linearly. In recent years their capabilities are highly increased.


Number of terms in Balanced boolean functions? I know that balanced boolean functions are required for creating S-boxes. I want to create four balanced Boolean functions for 4X4 Sbox and as far as I’ve understood, the maximum order of the balanced Boolean function should be <= (number of var)/2.

But… how many terms should there be in my boolean functions?

In general, if the algebraic normal form representation has few terms, an implementation can be faster.But such a simple representation can also lead to certain attacks.

You can represent such an Sbox as a mapping from $GF(2^4)$ to itself as well as a univariate polynomial mapping from $GF(2)^4$ to itself and what's sparse or simple in one representation can be complex in the other.

There are criteria such as resilience to consider as well, which may be the reason about your comment on nonlinear order.

Saarinen has a nice paper on classifying 4x4 Sboxes here.


How were the number of rounds for different key sizes of AES selected? The number of AES rounds increases with the key length. Why increase the number of rounds at all, and how were these round counts chosen?

There are two reasons:

More rounds means more security against cryptanalysis, simply, since there is more confusion and diffusion.
For a secure block cipher, there should be no attack faster than exhaustive key search (i.e. brute force). As exhaustive key search takes a lot longer for a larger key size, a theoretical attacker can afford more work to "break" the larger cipher. Thus we also increase the round number a bit to increase the security level of our cipher accordingly.
For a larger key size (as well as a larger block size), we need more rounds so that every key bit affects every ciphertext bit in a similar way, i.e. without measurable differences which would allow any cryptanalysis.

The 10 rounds for AES-128 seem to be about the lower level of what is (approximately) 128-bit-secure, and 10 rounds for a AES-256-like-cipher would have way below 256 bits of security.


Does FHE's longer key bring more security than traditional encryption algorithm? I check some key size which FHE libraries generated, for example, HElib's key size will be more than 300M, while tfhe's is also nearly 100M. Since these keys are so long, does it guarantee FHE encryption is more safer than traditional encryption, such as RSA?

No, the large sizes basically come from the fact that one needs to be able to handle a very large error term in order to perform a procedure known as "bootstrapping." The basic idea of bootstrapping is that we use a "base" homomorphic system which is somewhat error-prone; that is, the decryption of $c_1 \oplus c_2$ is intrinsically some $m_1 + m_2 + \epsilon$ for some error $\epsilon$. As we evaluate more and more $\oplus$ gates we accumulate more and more error, but we can solve this problem by including more and more bits per "signal" bit to handle the "noise" bits, and there are even clever ways to shift moduli as-you-go to keep the absolute magnitude of the error down for multiplications and so forth -- what's important is that you can either limit the depth of the circuits you use, or increase the size of the state space. Finally as part of decrypting, we end up truncating this error.

In bootstrapping, we take the fixed ciphertext that we have built up so far (which we of course know) and we form the circuit which would take a variable private key (which we of course don't know) and decrypt this ciphertext with that key. So, we "homomorphicize" this decryption circuit by treating the key as the input and the ciphertext as fixed, known boolean constants. We can then apply the homomorphic circuit to an encrypted private key $\kappa = E_k(k)$ that is stored as part of the public key, to get an "encrypted decrypted ciphertext" -- in other words, to get a new representation of our fixed ciphertext, $c \mapsto c'.$

This sounds completely useless and it is completely useless if you do not include the homomorphic version of the logic which truncates the error. But when the homomorphic error-truncation logic enters the picture, something magical happens: whatever $\epsilon_c$ has been built up so far in $c\leftrightarrow m + \epsilon_c$ gets replaced with a fixed error, $c'\leftrightarrow m + \epsilon_0.$ This error only depends on the depth of the decryption circuit (when viewed in this backwards key-first way).

I like the analogy for bootstrapping that one of the TFHE researchers gave: Spider-man can only swing for a certain time on one piece of webbing before it "runs out" (and he starts going backwards or something). But Spider-man is able to swing an arbitrary time/distance. How does he do this? While he is swinging he devotes some of his time to firing out another piece of webbing, and switches to that before the current piece "runs out". Similarly we have an error threshold of operations; we can only continue for a certain number of operations before we "run out", and so we devote a certain number of these operations to resetting our error bars on our ciphertext state and then we can continue doing this again.

Anyway, for a long story short, the combination of the tolerable error margins and the width of the key/plaintext/ciphertext together set the security level; and you may need to increase the width of the key text without making the key any more secure, in order to handle larger homomorphic circuits. The docs for the TFHE software for example specify that they target only a 110-bit security level; that places its security roughly at the 2048-bit RSA level according to a 2003 estimate from RSA security. The fact that it has megabyte-size keys is purely to handle the errors needed to bootstrap successfully.


How hard is to invert the function that computes the middle-bits of (x^2)? I'm designing a function f that should be moderately hard to invert and very fast to evaluate in a modern CPU. The function will be used in a proof-of-work function.

I've read that the middle-bits of multiplication are the harder bits to obtain, so I suspect that they are the hardest to invert.

Let $f(x) = ((x^2) >> 16)$ where $x$ is 32-bits and $f(x)$ is truncated to 32-bts, and the multiplication is carried on a 64-bit architecture.

(alternatively one could use $f(x) = ((2^{32}-x-1)*x) >> 16 )$

Suppose that, since $f$ may not be bijective, any pre-image (if exists) is accepted.
Suppose also that there is no enough memory or time to precompute $f^{-1}$ for all possible $f(x)$ values (although there might be some memory/time to precompute a much smaller table)

Again, this is not a strict crypto question. In this context "hard" does not mean cryptographically hard. I'm asking approximately how hard it is, measured in number of instructions of a standard computer (with a standard instruction set). A bound on the number of any operation would be great.

I'm posting here because the question does not fit well in theoretical computer science not in programming stack-exchanges.

Maybe there is a paper that describes this?

This is probably not secure enough for a proof of work.  I'll outline some attacks, of increasing sophistication/complexity and increasing effectiveness (decreasing runtime).

Brute force

The obvious attack is brute force: enumerate all $2^{32}$ possible inputs and check to find the first that produces the desired output.  This takes $2^{32}$ time.  I'm sure you already knew about this attack, and based on your question, it sounds like this is acceptable in your application.

Time-space tradeoff

You can use Hellman's time-space tradeoffs (or rainbow tables, the hyped-up version of that) to solve preimages.  You have to do a $2^{32}$-step precomputation to build up the table.  The table is of size about $2^{22}$.  After you've built up the table, you can find a preimage of $f(x)$ in about $2^{22}$ steps of computation.

Thus, after a one-time precomputation that probably takes a few minutes or at most hours, you can invert the function in a few seconds, using a few tens of megabytes of storage.

Guess the high bits and take a square root in the integers

There's a cleverer attack, which will find the preimage using at most $2^{16}$ simple steps of arithmetic (often quite a bit faster).  This will probably run in much less than a second, maybe at little as milliseconds to find a preimage.

We can write any 64-bit integer in the form $\alpha \cdot 2^{48} + \beta \cdot 2^{16} + \gamma$, where $\alpha$ is a 16-bit integer, $\beta$ a 32-bit integer, and $\gamma$ a 16-bit integer (i.e., $0 \le \alpha,\gamma < 2^{16}$ and $0 \le \beta < 2^{32}$).  Now we don't know the value of $x^2$, but $x^2$ is a 64-bit integer and we know its middle bits, so we can write it in the form

$$x^2 = \alpha \cdot 2^{48} + \beta \cdot 2^{16} + \gamma$$

where we know $\beta$ ($\beta$ is just the output of your hash function) but we don't know $\alpha,\gamma$.

Now iterate over all possible values of $\alpha$.  For each guess at $\alpha$, form the value

$$y = \alpha \cdot 2^{48} + \beta \cdot 2^{16} + 2^{16}-1,$$

take the square root of $y$ in the integers, and round down to an integer.  Let $x'$ denote the result, i.e., $x' = \lfloor \sqrt{y} \rfloor$.  Then check whether $x'$ is the desired preimage, i.e., whether $f(x') = \beta$.

I claim that this attack requires at most $2^{16}$ steps.  There are only $2^{16}$ possible values of $\alpha$, so we do at most $2^{16}$ iterations.  Moreover, in the iteration where we've guessed the value of $\alpha$ correctly, I claim we will successfully recover the preimage $x$.  Let me explain why.  First, the 64-bit integer $y$ will be very close to the 64-bit integer $x^2$: $y - x^2 < 2^{16}$.  Therefore, when you take the square-root, $\sqrt{y}$ will be very close to $\sqrt{x^2}=x$.  How close?  Well, notice that $(x+1)^2 \approx x^2 + 2x + 1$, so for 32-bit values of $x$, consecutive squares will be about $2^{32}$ apart from each other.  That's much larger than the gap between $y$ and $x^2$, so $y$ will be much closer to $x^2$ than to $(x-1)^2$ or $(x+1)^2$.  Thus, taking the square root of $y$ and rounding to the nearest integer will return $x$, not $x-1$ or $x+1$ or anything else (unless $x$ is extremely small, say $x < 2^{14}$, which has very low probability and thus can be ignored).

This means that this attack is guaranteed to succeed after at most $2^{16}$ iterations.

It turns out that not all values of $\alpha$ are equally likely; when $x$ is uniformly distributed, the upper 16 bits of $x^2$ are biased towards small values.  Therefore, if you iterate over all values of $\alpha$ in the sequence $0,1,2,3,\dots,2^{16}-1$, you are unusually likely to succeed early.  The average number of iterations until success is $2^{16}/3$, so the attack is about $3\times$ faster than you might expect based upon a worst-case analysis.


Is this a good entropy collector and whitening technique? I'm just reviewing a program someone wrote to provide high quality random data using an entropy collector and a hash based whitening technique. I'll try summarize the process:

Collect entropy from sources into separate arrays e.g.

milliseconds between key presses
milliseconds between mouse clicks
mouse movements x + y concatenated together

All the separate numbers are joined into a single array of values (a + b + c).
The array is mixed using a Knuth shuffle using random numbers from the programming language's psuedo random source. I believe a Knuth shuffle works its way through an array in reverse order swapping the current item in the array into a random position in the array.
The items in the mixed array are concatenated together and converted to a single string.
Each 512 bits of the string is iteratively run through SHA2 to give a uniformly distributed 256 bits of output per 512 bits of input. For example if a total of 8192 bits of entropy was collected, the total output would be 4096 bits.

The quality of randomness probably depends on how random the input is, e.g. how randomly the user moved their mouse. It would seem difficult for a person to repeat the same mouse movement path in the same way twice. Let's assume for now the user moved it very randomly and not in a repeatable fashion.

My questions:

Does this give high quality random data compared a PRNG?
What problems are there with this design?
Would "Von Neumann"-whitening work better than hash based?
How could it be improved?

The entropy of a PRNG depends on the quality and amount of "true" random noise used to initialise the PRNG and how much bits the PRNG produces before being re-initialised. A fresh PRNG might be as high quality as your entropy collection above, albeit often a different source such as CPU heat.

The method you cite will not add entropy but will spread the entropy fairly evenly within each 256 bit SHA result (Step 3 can be dropped).

If you want to know the level of actual entropy, just save a lot of results from Step 2 and check with a test suite such as NIST's statistical tests.

The key concern you should focus on is not spreading the entropy (even a non-cryptographic hash like MurmerHash will suffice*) but improving the quality and bitrate of the random noise source.

* If the random source is truly random as it should be, a cryptographic hash isn't needed. If it isn't random, a cryptographic hash reduces inferring the signal in the noise.

EDIT

Regarding Step 1 - If you want stick with keyboard/mouse for random noise input, I suggest you use an approach similar to HotBits timing.

Only the difference between two or three timings (I forget which is used to cancel clock drift) are used to create a single bit of entropy; a mouse could use pixel travel distance per fixed interval.

As the timings aren't as random as beta decay, you'll need a NIST test suite or similar to decide on how many bits you need to collect for each SHA-256 hash. Hint: It will be much more than 256 bits.


What are the disadvantages of XOR key derivation? Assume a 256-bit Key and a 256-bit Salt, with uniformly distributed entropy, both fully independent.

Assume Key is secret and Salt is public.

What theoretical advantages would deriving an AES-256-CTR encryption key using Key XOR Salt give to an attacker?

Assume that the product of Key XOR Salt will remain secret.

Assume that a KDF such as HKDF or a PRF such as HMAC cannot be used.

The two main concerns I'd have with the scheme you describe are 1) the risk of one of the subkeys being compromised, and 2) related-key attacks on the cipher.

The first concern is obvious: since the XOR operation is reversible, if an attacker finds out any one of the subkeys and knows the corresponding salt, then they can recover the master key.

Of course, if you can guarantee that all the subkeys are just as well protected as the master key, then this may be a non-issue.  But an extra layer of safety in case of subkey compromise can still be a nice thing to have, and using a non-reversible key derivation function instead of just XOR provides it at a very low cost.

The second concern is a bit harder to quantify.  There are known related-key attacks against AES, but so far none of them are efficient enough to be a real threat in practice.  Still, they do demonstrate that AES does not necessarily deliver its full advertised level of security in situations where an attacker may know the XOR of two or more keys.

As before, assuming that no new and significantly better related-key attacks against AES are found, you might be able to get away with this in practice.  (We do need to make some assumption like that anyway, given that nobody has proven AES to be secure, with or without related keys.)  But again, the safe and conservative choice would be to use a proper key derivation function that does not reveal any mathematical relationship between the subkeys.