texts: Elliptic curve cryptography related key attacks

texts:
This question is an extension of Families of public/private keys in elliptic curve cryptography

As described above, bitcoin "type 2" deterministic wallets use a root private/public key pair, where subsequent keys take advantage of the fact that in elliptic curve cryptography the public key for a private key + a fixed number, happens to be another public key plus the same number times a point.

Symbolically, with root private key $a$, public key $A$, 'fixed number' $b$, hash function $H(\cdot)$, we could construct a new private key as:

$a' = a + H(b)$,

which gives the corresponding public key as:

$A' = A + H(b) \cdot G$, where $G$ is the generator of the elliptic curve group in question.

There was some discussion about the properties $H(i)$ should have, with the responder being unsure if $H(i)=i$, or any $H$ at all, results in a secure system. This issue has been discussed in the bitcoin community as well, with the consensus being that if $H$ is a pseudorandom function, the idea is secure. Theory aside, this is exactly how a number of production "type 2" deterministic wallets work, and they haven't been hacked yet.

Building on that sandy foundation, I'd like to extend the idea even farther. Specifically, I'm creating a wager service, where I'd like users to be able to submit their wagers by sending bitcoins to specially encoded addresses. My thought was to use $H(\mbox{bet details} | \mbox{return address})$ with $|$ representing concatenation and $H$ a pseudorandom function. Thus the final public key for the address becomes $A + H(\mbox{contents})\cdot G$ and the private key $a + H(\mbox{contents})$

If the bet details are restricted to a small search space, and the return addresses restricted to addresses seen on the bitcoin network in the last $n$ blocks, simple brute force checking of every transaction to see if it is part of the system is quite feasible.

Note that I do not care if someone can determine if a given public key is related to another; the system will be completely public and all public keys will be determinable by anyone. In fact, for this application this property is an advantage for reasons of transparency.

The problem is, this gives the attacker a lot of control over the value $H(\mbox{contents})$: they can set an arbitrary number of bits by exhaustive search, incrementing the return address as required. If the service then spends the payments it is forced to use related private keys chosen by the attacker. To me, this smells bad, but if ECC is genuinely secure against related keys, it's not a problem.

Now I will say, a countermeasure would be to include (in the contents of $H()$) the block hashes of $n$ consecutive bitcoin blocks seen after the receiving address was last in the block chain. This assumes that no attacker has the hashing power to choose the hashes of $n$ consecutive blocks; a particularly strong statement as even to generate one block you are heavily constrained by the requirement to create a partial collision; $n=1$ may be sufficiently secure. However this extension would complicate the user interface and slow down the wagers which I'd like to avoid if possible. The attacker  would still have control over the bet details as well.

Quite simply: Is my proposed scheme secure, and why?


texts: Can you break a multi language code using Frequency analysis?

texts:
Let say that I wrote a 26 letter alphabet, each letter of my alphabet represent a letter from the latin alphabet.

I'm writing in 3 languages, only I know which languages.
Grammar is the one from my native language.

Each time I need to write a word I randomly chooses in which language I'm going to write it.

Can you actually break this code using Frequency analysis?

EDIT

example :

abcdefghijklmnopqrstuvwxyz
xzcdnefqghijbkslmaoprtuvwy

The sentence :

this is a cherry tree

becomes :

ceci is a sakura

[fr] [en] [en] [jp]

and once encoded :

cfch gi x oxirax


texts:
I have a unique identifiers that I would like to keep secure and provide information about it through tokens. These tokens should be verifiable after using the same algorithm on other end system with presented ID and comparing these values.

I am thinking to use PBKDF2 as a one-way function to get such tokens from IDs. But to be verifiable  I should use the same SALT everywhere.

Are there any security issues related to use the same SALT in PBKDF2 for all IDs?


texts: How do I retrieve a number which has been multiplied with a random number?

texts:
I have a 1024-bit number $n$ obtained by multiplying two 512-bit randomly generated prime numbers $p$ and $q$.
Then there's $\phi = (p-1)(q-1)$, which is another 1024-bit number.
I do not have $\phi$ but I do have the result obtained by multiplying $\phi$ with a random 1024-bit number.
I need to retrieve $p$ and $q$. I know how to get to $p$ and $q$ values starting from $\phi$ but I don't know how to extract $\phi$ from the product I have.
Is it even possible?


texts: How does Naver Line PC client obtain private key for end-to-end encryption (letter-sealing)?

texts:
When I download Naver Line PC client onto my PC, a six-digit number will be shown on the PC client for me to enter the number into my Line app on my mobile phone for decrypting the old and new messages. Once I do so, I can receive and send messages to any other endpoints.

How does Naver Line send my private key stored on my phone to the PC client?


texts: HMAC SHA256 vs RSA SHA256 - which one to use

texts:
Salesforce recently announced they are moving away from HMAC SHA256 to RSA SHA256.

Why did they make that move? Any technical factors?

Is HMAC really easy to break?

PS: I am not a security expert.


texts: Why would you expect to find a collision in a hash function after approximately $\sqrt{n}$ hashes?

texts: I can't get an intuitive understanding of why it's $2^{(\frac{n}{2})}$ and not $2^n$, where $n$ is the number of bits of which the key consists.


texts: Security effects of the seed's length in OAEP

texts:
In the OAEP scheme for asymetric encryption padding a random seed is used, whose length can be chosen. The paper which introduced OAEP in 1994 just states, that the seed's length $k_0$ should be chosen such that the adversary's running time is significantly smaller than $2^{k_0}$ steps.

I am wondering, what the securiy effects would be, of choosing a very small or very large $k_0$.

NOTE: I am asking about the generic OAEP, not RSA-OAEP, which fixes $k_0$ to the length of the hash function used.


texts: Sextic twist maps to q Eigenspace of Frobenius

texts:
Let $E(p)$ be a Barretto-Naehrig elliptic curve with r-torsion and embedding degree 12 and $E'$ a sextic twist with homomorphism $\psi$.
How to show, that

$E'$ has a unique r-torsion group
$\psi$ maps the r-torsion of $E'$ to the Trace-0 subgroup of $E(p^{12})$


texts: specific scenario question relating to using NACL crypto_box in a protocol

texts:
Scenario 1: SenderA sends message1 to ReceiverB

message1 is encrypted using NACL crypto_box using SenderA secret key and ReceiverB public key.

we understand that the NACL crypto_box authenticator proves to ReceiverB that message1 originated from SenderA.

we understand that ReceiverB cannot prove to a third party that message1 originated from SenderA because ReceiverB could have calculated the same authenticator. For our purposes this is a good thing.

Scenario 2:

AttackerA steals ReceiverB secret key and is also able to stage a man in the middle attack

We understand that AttackerA can now read all messages addressed to ReceiverB. We also understand that AttackerA can now impersonate ReceiverB and send out messages as ReceiverB. We accept that this may happen and we can manage the consequences.

What we cannot manage and must remain valid is that ReceiverB can always prove that any message received from SenderA (intercepted by AttackerA or not) has indeed originated from SenderA. Is there anyway that AttackerA can change an existing message from SenderA and still make it appear to ReceiverB as a valid message from SenderA?

Thank you


texts: Why ISO/IEC 9796 (signature with message recovery) instead of just encrypt the short message with private key?

texts:
I've had a look at “Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures” and read the very good answer https://crypto.stackexchange.com/a/17846/59673 and I understand that signature and encryption are usually different algorithms. For clarity, here I am just talking of RSA.

For long messages usually a hash is computed, padded, and then encrypted with the private key, and sent along with the message. The receiver can decrypt the signature with the public key and compare with the hash (re)computed on the message (and verify the padding integrity).

For short messages ( m < N ), what I (still) do not understand is the need of complex algorithms like ISO/IEC 9796.

Given that encryption is not the important factor but only verification is needed, the sender could encrypt the whole message with the private key (like it is normally done for the hash). The receiver decrypts the message with the public key, gets the message and implicitly verifies the sender.

Obviously textbook RSA would be subject to existential forgery (which wouldn't be a problem with formatted messages) and maybe to multiplicative forgeries. So one has to add padding, like in standard RSA.

If there are security issues on this mechanism, for what I understand they are exactly the same than for standard signature. So the only downside is that without the public key the receiver cannot get the message.

EDIT:
I'va also read the answers to Why hash the message before signing it with RSA? but as stated, I am asking in case of m < N.

So, are there more reasons not to encrypt the original message + some padding?


texts: Existing works on pre-computing ElGamal ephermal keys

texts:
I was playing around with a problem in e-voting schemes that use additive homomorphic encryption to tally votes, namely that at the end of the day somebody (or somebodies, if the secret material has been broken up somehow) has to be trusted to decrypt the final tally.
Looking at ElGamal's additive variant, reproduced here for reference:

$M$ is a modulo field in which all computation happens
$g$ is a generator for $M$
private key = $k_2$ = random number < $M$
public key = $k_1$ = $g^{k_2}$
$m$ is a member of the modulo field $M$
$x$ is the plaintext
$r$ is a random number < $M$, different for each call to E

this is the ephemeral key, used in the second $D(...)$

$E(k_1, x) = <g^r, m^x * k_1^r> = <c_1, c_2>$
$D(k_2, c_1, c_2) = c_2 * ({c_1^{k_2}})^{-1}$
$D(r, k_1, c_1, c_2) = c_2 * (k_1^r)^{-1}$

In e-voting schemes*, every vote is represented as a 1 or 0 plaintext and tallying is a simple matter of multiplying all the ciphertexts together and decrypting the result.
The following scheme eliminates the need to release the private key to decrypt the final tally:
Prior to the "election"

precompute a large list of random numbers $R = [R_1, ... , R_n]$ where $n$ is  the number of possible voters
let $A = [A_1, ..., A_n] = [R_1, A_1+R_2, A_2+R3, ... , A_{n-1}+R_n]$
publish the hashes of each member of A in order

When encrypting "ballots"

when choosing an $r$ for a $E(k_1, x)$, choose the first unused member of R

After the election

publish all the ciphertexts (the "ballots")
publish $A_y$ where $y$ is the number of ballots cast

$A_y$ would be the ephemeral key for the tally, but wouldn't allow for the decryption of any other ballots (like the private key would).  The correctness of $A_y$ is achieved by the polling authority committing to its value by publishing hashes before hand.

In a nutshell, it's just publishing a commitment (via hashing) for all possible ephemeral keys for the final tally; then releasing the singular relevant ephemeral key.  Everyone can tally, and decrypt that tally but decrypting individual "ballot" values shouldn't be possible.
I built a little proof of concept program that actual does this (using some open source implementations of additive ElGamal), and it works.
Of course, simply working isn't sufficient; I'm curious about the security of the scheme.
My question, are there any publications or other work related to this approach?
This seems like a pretty simple extension to the well documented additive ElGamal e-voting schemes, but my Google-Fu is failing to find anything and I'm personally unfamiliar with any such material.
(This approach [the pre-computed ephemeral key part, specifically] being broken and why, also acceptable naturally)
*Simplified greatly from actual schemes, but this is the heart of the crypto bits.


texts: Reasons for Chinese SM2 Digital Signature Algorithm

texts:
In the IETF RFC draft named "SM2 Digital Signature Algorithm" a signature algorithm is specified. The RFC does however not mention why this signature algorithm has been defined. Nor does it specify what the advantages of this scheme are over ECDSA. It seems that SM2 is the preferred EC signature format in China.

So the two related questions are:

Why was SM2 defined?
What are the (operational) differences compared to ECDSA?

Note that there seems to be a set of SM2 Elliptic Curve domain parameters defined as well.

According to [SM2 Algorithms Parameters] linked in the draft (and found on Wayback machine), here are the domain parameters:

y^2 = x^3 + ax + b

p =FFFFFFFE FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 00000000 FFFFFFFF FFFFFFFF
a =FFFFFFFE FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 00000000 FFFFFFFF FFFFFFFC
b = 28E9FA9E 9D9F5E34 4D5A9E4B CF6509A7 F39789F5 15AB8F92 DDBCBD41 4D940E93
n = FFFFFFFE FFFFFFFF FFFFFFFF FFFFFFFF 7203DF6B 21C6052B 53BBF409 39D54123
Gx = 32C4AE2C 1F198119 5F990446 6A39C994 8FE30BBF F2660BE1 715A4589 334C74C7
Gy = BC3736A2 F4F6779C 59BDCEE3 6B692153 D0A9877C C62A4740 02DF32E5 2139F0A0


texts: Can private key used in ECDSA be discovered when many signatures were colleced?

texts:
Can private key used in ECDSA be discovered when many signatures of different messages were collected (1M+) or may signatures of the same message were collected?
Will small nonce bias be easily exploitable?


texts: Is Diffie-Hellman mathematically the same as RSA?

texts:
Is the Diffie-Hellman key exchange the same as RSA?

Diffie Hellman allows key exchange on a observed wire – but so can RSA.

Alice and Bob want to exchange a key – Big brother is watching everything.

Bob makes an fresh RSA key pair and sends his public key to Alice.
Alice makes a random session key and sends it to Bob encrypted with Bob's public key.
Bob decrypts the session key with his private key.

Alice and Bob have exchanged a key despite the fact that anybody can observe
all the traffic. The maths of RSA and Hiffie Hellman are remarkably similar,
both involving modular exponentiation.

They both work because $(A*B)^C \bmod N$ can be done in two steps, i.e. by calculating $X = A^C \bmod N$ on one side of the transaction, and $X^B \bmod N$ on the other – this trick is the basis of both Hiffie Hellman and RSA. Which make me wonder: Are they really the same thing?

Can we algebraically prove that the correctness of RSA implies the correctness
of Diffie-Hellman?


texts:
Is there a risk when publishing multiple signatures for the same message? For instance, an ECDSA key (using an EC key) and a RSA-PSS signature (using a RSA key).

The context of my question is the use of Web Crypto Javascript library, where the only signature algo implemented by Edge is RSA-PKCS1 (which is not the latest recommended algo).

I was thinking of producing multiple signatures using different algo/keys and let the client check the one it wants.


texts: On the security definition of password-authenticated key exchange

texts:
I found in all PAKE papers, the security is defined as something like this:

Let $Succ(A)$ be the probability that an attacker $A$ successfully distinguished the session key from a random string. Then the advantage of $A$ is $Adv(A) = 2 \times Succ(A)-1$.
Then a PAKE protocol is secure if $Adv(A) \leq n_{se}/|PW| + neg$. where $n_{se}$ is the number of queries made by the attacker, and $|PW|$ is the size of the password dictionary.

From this definition, it seems that the session key is semantically secure only if $|PW|$ is large enough to make $n_{se}/|PW|$ negligible. Does this contradict the definition of PAKE that supports low-entropy passwords? I mean if |PW| is small, then the session key generated by PAKE is not indistinguishable from a random key, so we cannot use it for encryption and so on, isn't it?


texts:
I have some understanding of Cryptography and I would like to know if there is a tool or website to help me choose an algorithm based on my own needs (I'm being vague in purpose).

I'm looking for a website or tool that shows properties of algorithms like:

What is it best for
What is it not very good for
How can it be used poorly
What kind of algorithm is it? (hash, encryption, etc)
Is it reversible?
Is it symmetric or asymmetric?
Does it have known vulnerabilities?
How strong is it against brute force?
How proven is it in the industry?
When was it invented?
Is it fast to run? To decrypt (as appropriate)?
How common are implementations of it in various languages?
What programming languages have implementations currently?

I specifically want information to help me choose the appropriate algorithm based on my needs, not just encyclopedic information about algorithms. And for vulnerabilities, a resource that is maintained and updated would also be invaluable.

Perhaps all this information does not reside in one place, but I'm not really sure where to even start (other than just googling 'how to choose an encryption algorithm' and etc) to research this information.

Edit: Adding some links to articles

Wikipedia category: Cryptographic algorithms
Wikipeida: List of algorithms, Cryptography


texts: Can a Deterministic Signature Algorithm be paired with a Probabilistic Encoding Method?

texts:
I'm working with a C++ library and I’m currently investigating the changes needed to accommodate Deterministic DSA and ECDSA Signatures (RFC 6979). While the RFC 6979 changes are specific, I'm trying to understand more about the breadth of the potential changes to some of C++ classes involved in the implementation.

Is it possible to pair a “Discrete Log/ElGamal”-alike signature scheme (like – for example – DSA/ECDSA), adorn it with determinism (the deterministic $k$), and then pair it with an encoding method which uses randomness (maybe like something found in a PSS, perhaps with a salt)?

I realize RSA-PSS is a different class of signature schemes. I'm less clear or some of the unique or unusual pairings that may be experienced in the field with lesser known schemes.

This question on pairing primitives is about extensibility planning in software. It leaves open the mathematical questions of correctness and proofs. We often have to ask a theoretical crypto question here to ensure the cryptography is well represented, even though it could be off-topic.

Here's a question that touches on similar: Why use randomness in digital signature algorithms?

  De-randomization can be used to turn a randomized signature scheme
  (such as RSASSA-PSS of PKCS#1v2 parameterized with significant random
  salt) into a deterministic one ...


texts: Collision Resistant Hashing from One-Way Functions?

texts: In general, can we construct a collision resistant hash function from a one-way function?


texts:
The source from where I learn states:-

  CRL (Certificate Revocation List) is the primary means of checking status of certificates offline.

But I can't seem to understand how is it possible for a single device (smartphone, computer etc) to store the status of every single certificate that has been revoked in existence? Won't the certificate dump become a little too big incorporating every single certificate that has been revoked?


texts: Two-way secret sharing for authentication?

texts:
Secret sharing, using methods such as Shamir's Secret Sharing allows for t out of n shares to recreate a secret.

For authentication, the secret can be a user ID. A client with a logged-in user can store a token holding both a user ID and secret share. A server can hold another secret share for each user ID.

When requesting something that requires authentication, the client can send the user ID along with its' secret share. The server can use the client share and its' own share for the user to recreate the secret user ID. If the recreated user ID matches the ID that the client claims to be, then the server can proceed to fulfill the request. If not, then the request can be rejected.

Is this authentication scheme secure? If an adversary were to intercept a secret share for a user, would anything other than the user be compromised? Does this method have any practical use?


texts: Comparison Affine Coordinates and Projective Coordinates Addition in Excel

texts:
Kurve : EC : $y^2=x^3 + x + 1$
Generator:$(1,7)$
$p=23$

Result in Affine use Excel:
$P=(1,7)$, $Q=(7,11) \implies P+Q=(18,20)$

Result in Projective use Excel:
$P=(1:7:1), Q=(7:11:1) \implies P+Q=(15:2:9)$

$U = U_1 - U_2\ $ where $\ U_1 = Y_2 ⇤ Z_1, U_2 = Y_1 ⇤ Z_2$
$V = V_1 - V_2\ $ where $\ V_1 = X_2 ⇤ Z_1, V_2 = X_1 ⇤ Z_2$
$W = Z_1 ⇤ Z_2$
$A = U^2 ⇤ W-V^3-2V^2 ⇤ V_2$
Then
$X_3 = V ⇤ A$
$Y_3 = U ⇤ (V^2 ⇤ V2 - A) - V^3 ⇤ U2$
$Z_3= V^3 ⇤ W$

Is the result correct for projective coordinates (X/Z,Y/Z), because it should be same with affine (18:20:1)?


texts: Why can't you just clone encrypted data and use it?

texts:
Let's take a contactless card for example (one for public transport lets say (i.e. MiCard)), the data is encrypted on the card and encrypted on the reader as far as I know.

So how come somebody who could read those cards couldn't just clone the card, copying all the encrypted data onto another card and go around using that? It's all encrypted on the card anyway, isn't it?

If this is the case, why don't people do it and wouldn't contactless credit/debit cards and many other pieces of encrypted data be the same?

** Not sure if this was the right area to ask, apologies if it's not.


texts: If its possible to derive the public key from a private key, why can't we go in reverse?

texts:
I'm looking at source code for BitcoinJ that derives a public key from the private key.

  /**
     * Create the public key from the private key
     *
     * @param       privKey             Private key
     * @param       compressed          TRUE to generate a compressed public key
     * @return                          Public key
     */
    private byte[] pubKeyFromPrivKey(BigInteger privKey, boolean compressed) {
        ECPoint point = ecParams.getG().multiply(privKey);
        return point.getEncoded(compressed);
    }

Since "G" is known, and published for each given curve, what prevents someone from dividing (or multiple consecutive subtractions) to determine the private key?

If possible, would you explain it in layman's terms, and also provide additional concepts I can research the relevant background.


texts: Does a hash function in chaining mode or in counter mode make a better pseudo-random number generator?

texts:
I have two pseudorandom generators:

$f_1$ takes a random seed $l_0||r_0$ $\in \{0,1\}^{160}$ as input and outputs $r_1||r_2|| \dots ||r_k$, where $l_i||r_i = \operatorname{SHA-1}(l_{i-1}||r_{i-1})$ and $l_i, r_i \in \{0,1\}^{80}$
$f_2$ takes a random seed $s \in \{0,1\}^{160}$ as input and outputs $t_1||t_2|| \dots ||t_{k/2}$, where $t_i = \operatorname{SHA-1}(s||s_i)$, where $s_i \in \{0,1\}^{80}$ is the binary representation of $i$.

($l||r$ denotes the concatenation of $l$ and $r$.)

I'm thinking that $f_1$ seems better in a "random" perspective because for each step we use the output from the previous step as input, whereas in $f_2$ we use the same seed together with the position, which seems very predictable. But maybe that doesn't matter since we hash it? Then I would prefer $f_2$ because we get a longer output (more pseudorandomness) from the same amount of random input.

Am I on the right track or have I totally missed something?


texts: What is straight line black box reduction?

texts: I understand the notion of black box reduction. But what is straight line black box reduction?


texts: How does order in KDF formula affect its security proof?

texts:
If the expansion phase of key derivation is captured by the abstract formula (per Krawczyk):
KM = PRF* (PRK, CTX, L)
Then what happens to the security proofs if someone were to swap PRK and CTX.  For example, they insert random but not secret number as the first argument and use the secret in their CTX formation?
If I literarily use the proof in Appendix A, Definition 14 of Krawczyk's paper "Cryptographic Extraction and Key Derivation: the HKDF Scheme", it seems that the attacker would gain a great advantage by swapping PRK and CTX.  If the attacker knows PRK, he can always differentiate the output of PRF from random regardless how secret CTX is.  Is this enough to prove that the swap is a bad idea.
Furthermore, are there any known practical attacks on this swap?


texts: I do many searches but can't find any explanation about "AES analysis using entropy"

texts:
I found this scenario in CRYPTOOL2 templates but there is no explanation how entropy is used. There is just a short description "This template shows how to use a brute-force search to attack an AES-encrypted text. The Keysearcher component searches a subspace of the AES keyspace and uses the entropy of the decrypted plaintexts to find the correct one.
The plaintext with the lowest entropy will rank first in the bestlist.
As input, the Keysearcher receives a ciphertext, which was entered hex-encoded."
What does "and uses the entropy of the decrypted plaintexts to find the correct one." mean here?


texts: Can post-quantum algorithms be run on commercial devices?

texts: Noob alert! Can we run quantum safe algorithms on commercial devices (like phones, laptops, etc)? I've seen some messaging apps and vpn providers marketing themselves as quantum-proof. How likely is that all these claims are bogus for marketing (imo, very)?


texts: What are the characteristics of a quantum secure protocol?

texts: What are the characteristics of quantum secure protocol, and does it always need to be information theoretic to be called as quantum secure? Are the current techniques used in bitcoins quantum secure?


texts: Differences between Work Factor and Time Complexity

texts:
I am interested to know if work factor means the same thing as time complexity.

Quoting Work Factor : Uncovering keys in cryptosystems

  The Work Factor of a cryptosystem is related to its key-length and the
  working mechanism used (encryption and decryption algorithms). For
  example, if the brute force attack method is used to break the system
  (trying all possible combinations of the key), then the work factor is
  directly proportional to the length of the key.

This sounds awfully similar to what time complexity means to me. I hope to find out if the terminologies are similar.


texts: Pre-image resistant but not 2nd pre-image resistant?

texts:
Are there any cryptographic hash functions for which there is a known pre-image attack, or a known second pre-image attack, but not both?

The attack doesn't have to be practical - just anything that beats the security claim of the hash function.

Intuitively, 2nd pre-image attacks would be easier to find than pre-image attacks, but I'm not aware of any examples or that either property implies the other.

I believe there are no known pre-image attacks on the common crop of hash functions in use today, so I'm interested in historic, obsolete and proposed-but-not-adopted hash functions, but not toy hash functions constructed specifically to demonstrate the possibility of such attacks.


texts: Comparing two definitions of one-way function

texts:
I'm reading Rafael Pass's lecture notes on one-way function and came across two definitions.

The first one is: A function $f$ is one-way if $f$ can be computed in P.P.T. and there exists no non-uniform P.P.T. $A$ such that

$\forall x \in \{0,1\}^*, Pr[A(f(x)) \in f^{-1}(f(x))]=1$

However this definition is considered imperfect because (for example) under this definition $f(x)=|x|$ would be hard, because "it will take $2^c$ time to write a valid inverse to something such that $f(x) = c$. " (quoted from the note).

Then it gives the second definition, $\forall$ nuPPT $A$, $\exists \epsilon$ such that $\forall n \in N$

$Pr[x \leftarrow \{0,1\}^n; y \leftarrow f(x): f(A(1^n, y)) =y] \le \epsilon(n)$

It seems like I can't appreciate the subtlety here and I have two questions:

Why does $f(x)=|x|$ take $2^c$ time to write down an inverse.
Why $1^n$ is necessary in definition 2.

Can someone shed some light?


texts: Can CBC ciphertext be decrypted if the key is known, but the IV not?

texts:
Let's say that there is a binary file encrypted with AES in CBC mode (i.e. using a key and initialization vector). If key is known, but IV is not, is it easy to fully decrypt the file?

How hard is it?


texts: Is it safe to convert a 256-bit nonce into a 192-bit nonce by SHA-256ing and then truncating it?

texts: I'd expect a 192-bit nonce derived from a 256-bit nonce by computing the SHA-256 hash and then truncating it to 24 bytes to behave like an approximately uniformly randomly generated 192-bit nonce and hence be good enough for using it e.g. as a nonce for XChaCha20-Poly1305 encryption. Is this correct? If yes, could maybe someone sketch the formal argument, and if no, explain the problem with this approach?


texts: Why is the nonlinearity of this Boolean function evaluating to $\frac12$?

texts:
I am using the method presented in this paper to find the nonlinearity of the function
$$ f: \mathbb{F}^1_2 \to   \mathbb{F}^1_2 \\ f(x) = x$$
The truth table is $f = [0 \space \space 1]$. Now, I read from the paper by Terry Ritter that

Nonlinearity is the number of bits which must change in the truth
table of a Boolean function to reach the closest affine function.

This means the nonlinearity value should be a whole number.
The algorithm to calculate nonlinearity is to first use the Fast Walsh Transform to find the Walsh spectrum, then use the formula
$$Nl(f_k) = 2^{k-1} - \dfrac12 \cdot\max_{a\in\mathbb{F_2^{2^k}}} |W_f(a)| $$
where the Walsh spectrum is calculated by multiplying the truth table of the function by the corresponding Hadamard matrix.
So, since $k = 1$, we use the Hadamard matrix of size $2^1$ giving the following Walsh spectrum:
$$ \begin{bmatrix}0 & 1\end{bmatrix} \begin{bmatrix}1 & 1\\1 & -1\end{bmatrix} = \begin{bmatrix}1 & -1\end{bmatrix} \implies \max_{a\in\mathbb{F_2^{2^k}}} |W_f(a)| = |-1| = 1  $$
Therefore
$$ Nl(f_{k=1}) = 2^{0} - \dfrac12 \cdot 1 = \dfrac12$$
What am I missing?

In case the links are dead, the linked papers are:

Calculating Nonlinearity of Boolean Functions with Walsh-Hadamard Transform by Pedro Miguel Sosa
Measuring Boolean Function Nonlinearity by Walsh Transform by Terry Ritter


texts: How do you prove an encryption scheme is IND-CPA or IND-CCA?

texts: I know for proving a scheme is not IND-CPA or not IND-CCA you can construct an Adversary which has an unfair advantage in an experiment/game, but how would you prove a scheme is IND-CPA or IND-CCA?


texts: Consequences of AES-GCM always encrypting the same plaintext

texts:
I am analysing an authentication protocol. In this protocol AES-GCM is used to encrypt part of the messages.
Regarding the authentication protocol, I made the following observations:

The plaintext that is being encrypted is always the same. It may be assumed that the plaintext is known by the adversary.
Deterministic construction is used for the IV. It can be assumed that the IVs are also known by the adversary.
only two blocks of data are encrypted.

So, the only thing that changes during different runs of the authentication protocol is the IV (but these IVs are known by the adversary).
My intuition tells me that it is not a good idea to always encrypt the same plaintext.
I have the feeling that this may leak information about the encryption key?
So, my question is:

Can the encryption key be compromised if you have enough transcripts of protocol runs?
How many protocol runs would you need (AES-128-GCM is used)?


texts: Can a digital money system exist, that's secure, anonymous and allows offline transactions?

texts:
I just read Offline anonymous electronic money systems and their cryptographical base , which asks for anonymous offline systems. The OP claims eCash is such a system, and the answer claims that fairCash is such a system.

I've added security as a third requirement, since an insecure system seems useless to me. When evaluating a system, I assume that the mint/bank can be trusted, but that the persons who transfer the money don't trust each other, and have all hardware that's in their possession completely under control.

Looking at these three properties, it seems impossible to fulfill them all at the same time. In particular I don't see how you could prevent double spending.

The best offline system  I can think of, allows the bank to see the amount of cash flowing from/to a particular person, but only reveals the actual transaction if he double-spends, and then hopes that the double spent money can be recovered out of protocol(for example in court). But I feel like the reduced anonymity and security are worse than requiring online transactions. Edit: It seems like eCash falls in this category.


texts: Comparing Ciphertext when there is a change in source plaintext p1

texts: So, i know that if there is a change in source plaintext p1, c1 and rest of cipher blocks will be affected as c is required for the calculation in cfb. What i need to know is that how can i show how many blocks will be affected when there is this error. I have tried comparing the two cipher texts(one with no change in p1, and one with a bit change in p1) using diff, but i've had no luck in showing how many blocks are affected with the change in p1. Thanks.


texts: Proving a secret is known without revealing it

texts:
Let's say Alice wants to prove to Bob that she knows a secret S that Bob is also supposed to know. Alice can't be sure Bob is really who he pretends to be, so she needs to make sure Bob can't deduce S from their interaction. Additionally, S could be weak (e.g. "abc123"), so she can't simply send a hash of S to Bob, or any f(S) really since that could be brute-forced.

What are your thoughts on this? Is this even possible?


texts:
I'm building an embedded device that I plan on distributing. Periodically the device will poll my server to check for updates and commands. I'd like the device to verify that any messages(JSON strings parsed by a client written in Go) and updates are actually from me.

My plan is to use use Go's crypto/ecdsa library to generate a private/public key pair for each device, store the public key on the embedded device, and sign every message with the private key. The device will then verify any received messages with its public key.

From what I've learned so far it seems that the RNG (on the server that's signing the messages) could be a potential weak spot. Are there any other obvious flaws/issues I'm missing?


texts: Why does "2xAES-256" provide "99.99%" security strength whereas "1xAES-128" provides "40%"?

texts:
I recently was "directed" to FlipsCloud, a company selling security solutions (as far as I can tell).

In particular I've investigated their page and found a page on their "encryption features".

This page claims a few things (some of which deserve their own questions).

As for this question, I'm asking:

How can one construct the "security strengths" given on the page?

For everyone not wanting to visit this page, he's the chart in question in text form:

  Security Strength of Encryption Technologies
  2x AES-256 bit(CBC) 99.99%
  1x AES-256 bit(CBC) 50%
  AES-128 bit 40%
  RC4-128 bit 30%
  RC4-40 bit 10%


texts: Is it ok to store the plaintext hash of encrypted data

texts:
Is it ok to create and store the hash (unkeyed hash function) of a plaintext before encryption or does it lead to vulnerabilities?
If it is ok are there requirements for the used hash function and encryption algorithm?

Important to mention is that the hash should not be used for integrity checks or something like that.


texts: Help with terms: hash function and a pseudorandom function

texts:
I am a little bit confused about the terms hash function and pseudorandom function. As far as I know, I can use a cryptographic strong hash function as a PRF. The hash function has a IV and is completely public - everybody can look at the construction and at the details. A good hash function maps the input in a pseudorandom way to its output (deterministic).

So a pseudorandom function is quite similar. Here you do not take a fix hash function, rather than you take a function from a set of functions. That model is implied by using a keyed function. So there are often keyed hash functions used for example the HMAC is taken as a PRF.

So in a limited view, is it right to say that a attacker does not know my "internal conditions" of my PRF? (I mean my current Setting: which key i use and which hash function, or if I use HMAC, he does not know my key and my constants and my hash function.)


texts: Verify a RSA signature using only RSA encryption

texts:
I'm trying to verify a RSA signed message, however, the API that I have access to in that environment only has encrypt and decrypt.
I think I understand that verification and encryption with public key are similar. Actually, running the following seems to work:

openssl rsautl -sign -in clear -inkey private_key.pem -out signed
openssl rsautl -encrypt -pubin -inkey public_key.pem -in signed -raw -hexdump

This second command will get the initial clear, padded (then I just need to unpad and verify that it matches the clear). However, the -raw is where I encounter an issue.
As the signed message is the size of the key, I can't encrypt it (the API will refuse, as does openssl if you omit -raw).

I'm not sure on how to proceed. I feel that what I'm trying to do should be possible.


texts: Does DTLS in WebRTC protect from active Man-in-the-Middle?

texts:
I wonder if it does. It seems to me that there is no way for participants to authenticate each other securely. There are, though, signaling servers, but I don't think that they are capable of key distribution.

Is there something I've missed?


texts: brute-force factors of numbers on my computer at home?

texts:
I am currently researching RSA crypto and brute-forcing keys and read about the factoring-problem. There is an increasing difficulty with factorizing numbers of an increasing value, especially when it comes to primes, and this is one of the reasons to why RSA keys are impossible to brute-force.

Not completely unrelated, I was just wondering if I could brute-force factors of specific numbers using my regular computer that I have for personal use. I would like to measure the time it takes to facorize the numbers and how time changes as the numbers grow. Is there a program to download which can do so (facotrize the numbers that is, not neccesary with the time measuring part)? If not then why is it not possible?


texts: How do I prove that this PRNG is easily distinguished from a random sequence of numbers (modulo m)?

texts:
I was studying Crypto, and this question came up. Using a PRG like the multiplicative congruence generator:

$b_{i+1} = a \cdot b_i \mod m$

How do I prove that the output of this PRG, or any PRG's whatsoever is easily distinguished from a random sequence of numbers?


texts: Diffie Hellman Key Exchange (Finding # of bits/digits of secret key)

texts:
As we know that in DH key exchange, both Alice and Bob would agree on the parameter $p$ and $g$. Next, Alice would choose a secret key $A$ while Bob would choose a secret key $B$. Alice would compute $g^A\mod p$ and Bob would compute $g^B\mod p$. They would exchange these computed values and each side would raise their secret key against the received computed value, i.e. $(g^A)^B\mod p = (g^B)^A\mod p$.

From Charlie's (external party) point of view, he would know values of $p$, $g$, $g^A\mod p$ and $g^B\mod p$. Assuming that $g^A\mod p$ and $g^B\mod p$ are 100 digits long, would he be able to determine a bound (in terms of digits or bits) for the respective secret key $A$ and $B$?

Please do point me at any links that is relevant to this question! Thanks & Cheers!


texts: Invalid curve attack: finding low order points

texts:
Background
Here's a description of page 182 of "Guide to Elliptic Curve Cryptography" by Hankerson, Menezes and Vanstone. Here's a quote from that page:

The main observation in invalid-curve attacks is that the usual formulae for adding points on an elliptic curve $E$ defined over $\mathbb F_q$ do not involve the coefficient $b$ (see §3.1.2). Thus, if $E'$ is any elliptic curve defined over $\mathbb F_q$ whose reduced Weierstrass equation differs from $E$’s only in the coefficient $b$, then the addition laws for $E'$ and $E$ are the same. Such an elliptic curve $E'$ is called an invalid curve relative to $E$.
Suppose now that $A$ does not perform public key validation on points it receives in the one-pass ECDH protocol. The attacker $B$ selects an invalid curve $E'$ such that $E'(\mathbb F_q)$ contains a point $R$ of small order $l$, and sends $R$ to $A$. $A$ computes $K=dR$ and $k = KDF(R)$. As with the small subgroup attack, when $A$ sends $B$ a message $m$ and its tag $t=MAC_k(m)$, $B$ can determine $d_l = d \bmod l$. By repeating the attack with points $R$ (on perhaps different invalid curves) of relatively prime orders, $B$ can eventually recover $d$.

Question
I am having a problem understanding one aspect of invalid-curve attacks: given some curve $E$, how does one finds an invalid curve $E'$ ($E$ and $E'$ have same parameters except for coefficient $b$) and a small-order point $R$ on $E'(\mathbb F_q)$? Is there an efficient algorithm for finding curves with small order points?
I would appreciate an example showing how to find such a curve $E'$ and a point $R$ for some "popular" $E$ (e.g. one of the NIST curves).
Related questions
Why do public keys need to be validated?
Attacks on schemes based on elliptic curves when the transmitted points are not on the curve


texts: Is the KDF pbkdf2 included in the openssl suite?

texts:
I'm trying to encrypt a file using DES in CBC mode but when I try to specify the key derivation function it tells me my command is wrong. It only fails when I try specify the KDF and works when I don't. This is the command i'm trying to use - openssl enc -des-cbc -pbkdf2 -in test.txt -out test.bin -pass pass:test

This command is taken directly from my reference so why does it not pick up the KDF? Is it because i'm using the wrong version of openssl (LibreSSL 2.6.4) or do I have to manually add pbkdf2? If so how do I?


texts:
I'm designing a cryptography-breaking assignment for a college-level introductory security course, and I'm looking for a hash function which is reasonably easy (but not too easy) to generate collisions for. The assignment is that the students are given a hash table implementation which uses such a function, and their task is to design a series of inputs which will tank the hash table's performance. I was originally thinking of modelling it off of PHP's associative array attack from a few years ago, but it's actually too simple (for integer keys, the index used is literally just the integer modded by the table size). Any ideas for something that might be a tad harder than this, but not so hard that a bunch of sophomores with a week's worth of crypto lectures couldn't solve it in a reasonable amount of time?

Thanks!

EDIT: To clarify, I'm looking for hash functions which are not cryptographically secure, and can be easily inverted (or at the very least caused to collide) without brute-force search of the input space. As a general rule, hash functions which you could even mistake for cryptographically secure are probably too hard to break for this assignment.


texts: How does order-preserving encryption work on string?

texts:
I have read “How does order-preserving encryption work?”. After that, I completed order-preserving encryption on integer data.

Now, I have four questions in this subject:

Is it possible to apply sum operation on encrypted integer data.
Is it available for string data?
Can i make string operations like finding an encrypted string in a ciphertext, order encrypted strings ... ?
If order-preserving encryption is not suitable for these operations, Does any algrotihm make the job ?


texts: Acceptable assumptions when proving security

texts: Considering the output of a cryptographic primitive, like an encryption scheme (CBC, ...), a hash function or even the output of any schemes based on number theoretic assumptions, is it reasonable (acceptable) to assume that these outputs are random when proving the security of a protocol/algorithm which relies on the use of such a primitive? Is this a good starting point?


texts: Demonstrating the insecurity of an RSA signature encoding scheme

texts:
I'm working on problem 12.4 from Katz-Lindell. The problem is as follows:

  Given a public encoding function $\newcommand{\enc}{\operatorname{enc}}\enc$ and
  a textbook RSA signature scheme where signing occurs by finding $\enc(m)$ and
  raising it to the private key $d \bmod N$, how can we demonstrate the scheme's
  insecurity for $\enc(m) = 0||m||0^{L/10}$, where $L = |N|$ and $|m| = 9L/10 - 1$
  and m is not the message of all zeroes?


texts:
I was reading an article about breaking RSA with PKCSv1.5 padding (http://mslc.ctf.su/wp/google-ctf-spotted-wobbegong-crypto-100/).
It says that while retrieving the message we multiply by the inverse fraction and take modulus of a power of 2 rather than modulo N.

But how do we determine which power of 2 to be used ? Is it a trial and error or can we determine it from the length of the message ?


texts:
I was trying to understand the Bleichenbacher-attack. I went through the paper of Bleichenbacher to understand it bit more. However I tried to get some test vectors to simulate this attack locally but couldn't find it.

Can some please help me in getting smaller test vectors so that I can do some hands on?


texts: Shor's algorithm for discrete log and periodic function

texts:
I am wondering about the following well-known problem:
Let $p$ is a prime number, $g$ is a generator of $(\mathbb{Z}/p\mathbb{Z})^\times$, $b \in (\mathbb{Z}/p\mathbb{Z})^\times$. Find $x$ - an integer such that $g^x = b \mod p$.
When I read about Shor algorithm for discrete log problem I always see the following function
$$ f(x_1, x_2) = b^{x_1} a^{x_2} \mod p$$ and the task is to find the period of the function, i.e. $(\omega_1, \omega_2)$ such that
$$ f(x_1, x_2) = f(x_1 + \omega_1, x_2 + \omega_2) $$.
My question is the following: why do we consider the complex function and don't consider the simplest one:
$$ f(x_1) = b^{x_1} \mod p$$
If we can find the period of the function $\omega_1 < p - 1$ then
$$g^{x \omega_1} = 1 \mod p$$
Thus from small Fermat theorem we have
$$ x \omega_1 = 0 \mod p-1 $$
That can give the discrete log problem solution


texts: What happens when a nonce is reused (WPA2)

texts:
I am trying to understand the KRACK on WPA2. But in their paper (PDF) it just simply states that

  By forcing nonce reuse in this manner, the encryption protocol can be attacked.

But I cannot find an explanation WHY this is possible. I.e. what exactly happens, that when a nonce is reused, the encryption protocol can be attacked?


texts: Balanced Feistel networks: Are there any lower bounds on the computational complexity of breaking a $k$-round Feistel cipher?

texts:
This paper by Patarin presents an attack (section 9) on balanced Feistel networks with $k$ rounds, where the input is a bit-string is of length $2n$. (Since it is balanced, this means each PRF takes as input a bit-string of length $n$).

In this attack, the adversary is able to distinguish a $k$-round Feistel network permutation from a uniformly chosen even-signature permutation with computation $\mathcal{O}(2^{n(\frac{k^2}{2}-4k+8)})$. (Actually distinguishes generators of such permutations.)

Is there a lower bound on the amount of computation required to distinguish a $k$-round balanced Feistel permutation from a random even-signature permutation?


texts: How were codes in WW1 reciphered (to enhance security levels) without them turning meaningless?

texts:
In WW1, the Germans made their communications secret by encoding their messages. This meant that the message's sender would have a codebook with all possible words and phrases he might use listed in alphabetical order. Those were attached to a random number. He would then write down the numbers corresponding to his message. The receiver would have the same book, just reversed. He would have all numbers listed from the smallest to the biggest, and he would be able to decode the message by finding the corresponding word/phrase for each number.
So far, so good. Now, I keep reading about how Germans would add a layer of enciphering to enhance security. I just do not get how this wouldn't be paradoxical with the concept of the codebook. I have two different outcome suggestions, and they both fall short:

Suppose the sender wanted to send the word "hi." He would then encipher this and get, let's say, "xt." He would then look at his codebook and find no number corresponding to "xt."

Suppose the sender wanted to send the word "hi." He would then find the corresponding number for "hi." He would then decipher that number and get a different number. The receiver would then look up the number and find either a non-existing number or a wrong word.
Here are two examples in the literature of the history of cryptography that state how an extra layer was added:

Page 66 in The History of Code Breaking:
"The Zimmermann Telegram was superenciphered (encoded again by using the German Diplomatic Code Book, Code No. 13040)."
Under "VB codebook" in the Wiki page about Room 40:
"Re-ciphering of the code was accomplished using a key made up of a codeword transmitted as part of the message and its date written in German. These were written down in order and then the letters in this key were each numbered according to their order of appearance in the alphabet. This now produced a set of numbered columns in an apparently random order. The coded message would be written out below these boxes starting top left and continuing down the page once a row was filled. The final message was produced by taking the column numbered '1' and reading off its contents downward, then adding on the second column's digits, and so on."


texts: Is ”generating transcripts that are indistinguishable from actual messages in a signature scheme” not universal forgery?

texts:
In the Pointcheval paper “Security arguments for digital signatures and blind signatures”, they have proved the security of Schnorr signature for existential forgery under adaptively chosen-message attack.

The proof requires a simulator that can produce transcripts that are indistinguishable from the actual messages generated by the signer, without knowing the secret key.

I apologize if my understanding is wrong. Can someone shed some light on what they mean by simulating the transcripts without knowing the secret key?

Because – if that is possible – would it not become universal forgery?


texts: Are there recommended modes of operation for lightweight ciphers?

texts:
There are many recommended modes of operation for block ciphers as described by NIST here, e.g. for DES and AES.

However, I am struggling to find any for lightweight ciphers. I am particularly interested in modes of operation for PRESENT, Clefia and other standardised lightweight ciphers, and why they are suggested.


texts: Is iterative sha256 adequate for local password manager?

texts:
I'm fairly entry-level crypto; not a cryptographer by any stretch... I am at the level of ability to implement most of the traditional packages in python; the hashlib hashes and EAS, ECDSA implementations, etc. And generally logically grasp what they're doing under the hood and when they're appropriate. I've come here to learn a bit more about this new breed of PHC 2015 candidates.

I'm working on a "password manager" to manage my logins to social media, email accts and the like.   I tend not to like GUI's, nor did I like any of the implementations I found... so I thought I'd have a go at it myself.  Of course, as I get down the rabbit hole I gain a clearer picture of my own naivety.  Initially... I was just thinking very simplistically... hash the master password w/ sha256... AES-CBC for each site pass... copy to clipboard, ctrl+v and auto remove from the clipboard.  Then I was like... no, we need stronger master pass!  so:

key = sha256(blake(pbkdf(key)))

I was proud for a moment of my implementation... that faded quickly.

I got to thinking about the whole "hash the master password" concept and I realized that it was really meant for server/client situations, with brute being restricted by websocket communications response time and API limits.  With enough time by some malware running in the background and near-unlimited speed on my beast desktop this was still plausibly brute prone?  Not sure to be honest; concerned enough to ponder on...  At this point, I was unaware of "password hacking competition" and the likes of argon2 and friends.  But I saw a problem and of course headed down the ill-advised path of "roll my own".

Two things immediately came to mind.

1) increase ram requirement
2) increase time requirement.

My first attempt was to up the iteration count of pbdfk, which did indeed increase the cost by about 1 second before the python implementation denied me any further iterations.  But I wanted more...

So I devised two simple solutions:

# 1) make the key really big
key *= int(10 ** 8.5 / len(key))

# 2) sha256 it millions of times
for i in range (10 ** 7):
    key = sha256(key)

First gives me about a gig of ram requirement and second slows the response down to 8 seconds.   The ram gives multicore resistance, the time... increases brute time, surely the iterative sha256 makes rainbow tables less likely.  And of course, I could still do something more salty on the way into my iterative big sha256...  ala:

blake(pbkdf()).

I did a little happy dance, but it was at this point that I delved deeper into the rabbit hole and "read the docs" eventually stumbling upon blake2.net:

  You shouldn't use any general-purpose hash function for user
  passwords. Instead you should use a password hashing function such as
  the PHC winner Argon2 with appropriate time and memory cost
  parameters, to mitigate the risk of bruteforce attacks.

At first, I was vilified! I was right!

Then... the "don't roll your own" came over me... and the fact that I was 4 years behind the times in my own awareness. I've since learned argon2 is using blake under the hood.

So I have come here to ask:

Is my method as strong as I expect?
What does argon2 achieve beyond what I'm doing?


texts: Is it generally considered acceptable for app owners to be able to retrieve private keys from users when their apps offer end-to-end encryption?

texts: E2EE promises that data sending between two endpoints can be decrypted by only those two endpoints. If an app offers E2EE but still has functions to retrieve private keys from users for any purposes such as for multi-device sync, is that considered acceptable as the app owner can get the private keys from the users and decrypt user messages when they need as the app resides on the user devices has the functions for retrieving user private key which could be invoked for other purposes such as for legal execution ?


texts: Understanding Diffie-Hellman Key Exchange

texts:
Help me understand the Diffie-Hellman Key Exchange

From what I understand:

Agreed upon numbers: Both parties agree on the value of a large prime number $p$ and a generator $g$.
The users each choose private keys; Alice chooses $a$ and Bob chooses $b$, such that $0<a,b<n$.
The users each calculate public keys: Alice computes $A=g^a\pmod{p}$, while Bob computes $B=g^b\pmod{p}$. Each sends the other their public key.
The users calculate the secret key $k$ as the other person's public key raised to the power of their own private key mod $p$. Alice calculates it as $B^a\pmod{p}$, Bob as $A^b\pmod{p}$.

Example: $p=7, g=4$. Alice chooses $a=2$, Bob chooses $b=3$, Charlie chooses $c=4$. Then the public keys are $A=4^2=16$, and $B=4^3=64$, and $C=4^4=256$.

In that case, Alice and Bob will compute $$k_{ab}=64^2=16^3=4096\equiv1\pmod{7}$$

Alice and Charlie will compute
$$k_{ac}=256^2=16^4=65536\equiv2\pmod{7}$$

Questions:

Why does $p$ need to be a prime number?
How does the size of $p$ affect its security?
What's a generator ($g$)?
Why must the private key be less than $p$?
What is mod?
what maths/types of logic formulate the science behind this kind of cryptology?

Also, please correct me if I've made any errors above. Please feel free to offer any additional information that you think will aid in understanding this concept.


texts: Are there shortcuts for computing ECC Point multiplication?

texts:
I'm trying to learn about elliptic curve cryptography.

Let's say you have point $P$ and 256 bit number $n$ and you want to compute $nP$. It sounds like computing additions one at a time is not computationally feasible. Is there an algorithmic "shortcut" to compute this? If so, how does it work?


texts: Can an encryption method be used as a hash function?

texts:
As I understand, there are a few requirements for a good hash function.

Hard to find any message from a given hash
Hard to find any 2 messages which give the same hash
A single bit change in the input message should lead to change of each bit of the output with a probability of 0.5 (as close as possible to 0.5)
Good collision resistance

So my question is if I have a asymmetric key encryption method, erase off the private key, encrypt the message with the public key, then take the least significant (say) 256 bits. Do I have a good hashing function? Does my hashing function provide some guarantees on the points 3,4? I am fairly sure points 1,2 are fine though. Aren't they?

My aim is to explore the possibility of creating a hash function out of an encryption function. So put aside the fact that messages are usually padded with random information before encryption. Just Encrypt(Message, Public-key).

edit : Some of the answers ask, how can i be sure I destroyed my private key properly. What I can do is even before generating a public/private key pair, I would just create a single random string and call it public key(if the public key has some requirements on the length or other properties, I would generate a string of that particular length). In general I would create a string which is acceptable as an public key by the encryption machine.


texts: The difference between MACs vs. HMACs vs. PRFs

texts:
I have some confusion regarding the difference between MACs and HMACs and PRFs and when to use which term.

If the function is computed using a hash and secret key like the following, is this a HMAC or MAC?

MD5(master_secret + pad2 + MD5(handshake_messages + Sender + master_secret + pad1));

If I have a tag for verifying data, computed using a PRF in the form:
PRF(master_secret, finished_label, Hash(handshake_messages))

Again, my question, is this HMAC or MAC or none, just a PRF?

The above functions are what is used in the Finished messages for SSL 3.0 and TLS 1.2 respectively. The literature use MAC generally. I am not sure if this is the correct term used to refer to them.

Can I refer to HMAC and PRF by MAC?


texts:
The Von Neumann randomness extractor is explicitly mentioned in the randomness extractor page of Wikipedia, but strangely enough that page does not contain any reference to whitening the results of an entropy source.

Two intrinsically related questions:

Is this Von Neumann randomness extractor indeed a form of whitening?
Is whitening simply a part of randomness extractor, or is there another relation between whitening and randomness extraction?


texts: Prepend information about encryption implementation to the stored data

texts:
I want to preface this by saying i will not be using any of this code/information in a live project, this is only for learning/fun (so I welcome some speculation)

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

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

The exact data i wanted to include is:

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

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

So please, tell me why I'm stupid!


texts: Is it possible to obtain AES-128 key from a known ciphertext-plaintext-iv tuple used the encrypt the plaintext?

texts: i have a file, which was encrypted with AES-128 in CBC mode. I know the content of original file and know the iv used to encrypt that file.So, just wondering if it's possible to recover the key used from the information provided.


texts: How to cipher with N public keys and decipher with ANY of the N private keys?

texts:
X = plaintext

Given N key pairs:

P1 = (P1.private, P1.public)
...
PN = (PN.private, P1.public)

I want to find 2 function Cipher and Decipher such as

Cipher(X, P1.public, P2.public...PN.public) = X encrypted
Decipher(X encrypted, P1.private) = X
...
Decipher(X encrypted, PN.private) = X

Does such scheme exist?


texts:
$E(k_1, pt) = c_1, E(k_2, c_1) = c_2, D(k_{new}, c_2) = pt$, where $k_{new} = f(k_1, k_2).$ Sharing $k_{new}$ and $k_2$ should reveal no information about $k_1$.

Clarifications:

Being able to decrypt the ciphertext $c_2$ knowing only $k_{new}$ is the first desired property of the system
One cannot derive $k_1$ knowing both $k_{new}$ and $k_2$.
One cannot easily derive $k_1$ knowing other pairs $k_2'$ and $k_{new}'$. See @poncho's comments.

$D(k_{new}, c_2) = pt$ or $E(k_{new}, c_2) = pt$ doesn't matter as long as you recover the plaintext.

Real world example to clarify things even more:

Alice has a very large database which it chooses to store at Eve's site. Because Alice doesn't want Eve to read the data, nor doesn't she know in advance which data will be shared with whom, she encrypts all the records with a single key ($k_1$).
Now Bob requests access to some specific information. Bob and Alice know each other so Alice gives him access to that subset. However Alice wants to do that efficiently. Also Alice doesn't want Bob to be able to read anything else except the shared subset. Therefore she cannot: a) Decrypt the shared subset at Eve's site and then re-encrypt with a different key (this would expose all the database contents to Eve), b) Retrieve the data from Eve, decrypt, re-encrypt and store back data at Eve's site - this implies a round-trip delay which is prohibitively expensive.

Thus Alice needs a cryptosystem which would allow re-encrypting the data directly at Eve's site, however Eve shouldn't be able to read any plain text (nor the one shared with Bob, nor the rest of the database records). Sharing the decryption key ($k_{new}$) is done through a direct channel between Alice and Bob (e.g. using Diffie-Hellman).

The "cryptosystem" stated in the question is just a way I saw that happening. Note that $k_1$ shouldn't become known to Bob (e.g. if Bob colludes with Eve or other people with whom Alice shares (possibly different sets of) data).


texts: How Were secp*k1 elliptic curve generators chosen?

texts: The Koblitz elliptic curves specified in the SEC2 document https://docs.google.com/viewer?url=http%3A%2F%2Fwww.secg.org%2Fcollateral%2Fsec2_final.pdf all have the nice feature that the parameters are highly non-arbitrary; the modulus is simply a few powers of two put together, and the a and b parameters are 0 and 7. The group order can be forgiven; that's just a number that you get given the other parameters of the curve. However, the choice of generator seems to be very arbitrary. Why did the SEC not choose simpler parameters for the generator (eg. x = 1000, y is even) instead?


texts: Is it possible to apply hill-climbing algorithm to Diffie–Hellman?

texts: If Eve intercepts all the values communicated between Alice and Bob in a Diffie–Hellman key exchange, and applies the hill-climbing algorithm to reverse the modulo function, how will the algorithm know whether it is following the right path?


texts: Security of Diffie-Hellman with multiplication for secret derivation?

texts:
Today I saw this question again which presents an unusual variant of the Diffie-Hellman key exchange. Having thought about it for a while I could find out how functionally works, but have essentially little cue whether it actuappy provides security.

My question is now:
Does the below stated Diffie-Hellman-like key exchange protocol enjoy similar security properties as normal Diffie-Hellman?

First the variables: Let $(\mathbb G,g,q)$ be a multiplicatively-written group where the discrete logarithm problem is hard with prime order $q$ and generator $g$. Let $a,b,x,y \stackrel{$}{\gets} \{0,\ldots,q-1\}$ be sampled uniformly at random. Let $A=g^a, B=g^b$. Let $a,x$ only be known to Alice and $b,y$ only be known to Bob. Let $a,b$ be static and $x,y$ be ephemeral across multiple sessions. Let $K=g^{x+y}$ be the shared secret, which can be computed by both parties after the exchange. Now define the following messages (the letters on the left denote Alice and Bob):
\begin{align}
A\to B&:B^x=g^{bx}\\
B\to A&:A^y=g^{ay}\\
\end{align}

If you are questioning functional correctness at this point note that Alice can trivially compute $g^x$, knowing $x$, and can compute $g^y$ as $(A^y)^{a^{-1}\bmod q}$, yielding $K=g^x\cdot g^y$. The computation for Bob goes analogous.


texts: How to define the statistical distance between two probabilistic algorithms?

texts:
Let
$$
\begin{aligned}
F_{i} \colon \{\, 0,1 \,\}^* \times \{\, 0,1 \,\}^* &\to \{\, 0,1 \,\}^* \\
(k, x) &\mapsto y \\
\end{aligned}
$$
for $i \in \{\, 1,2 \,\}$.
As we known, for every oracle algorithm $\mathcal{D}$ the distance between $F_{1}$ and $F_{2}$ with respect to $\mathcal{A}$ is defined as

$$\mathrm{Dist}_{\mathcal{D}}^{F_{1}, F_{2}}(l) = \left\vert \Pr \left[ k \gets \{\, 0,1 \,\}^l, \mathcal{D}^{F_{1}(k, \cdot)}(1^l) = 1 \right] - \Pr \left[ k \gets \{\, 0,1 \,\}^l, \mathcal{D}^{F_{2}(k, \cdot)}(1^l) = 1 \right] \right\vert$$

I think it is meaningful to consider the computational indistinguishability of two probabilistic algorithms. Let $A_{1}$ and $A_{2}$ be two probabilistic algorithms. Formally, for $i \in \{\, 1,2 \,\}$,
$$
\begin{aligned}
A_{i} \colon S_{l} \times \{\, 0,1 \,\}^* &\to \{\, 0,1 \,\}^* \\
(\alpha, x) &\mapsto y \\
\end{aligned}
$$
Thus, $A_{i}(x) = A_{i}(\alpha, x)$ where $\alpha$ is uniformly chosen in $S_{l}$. We can still define the computational distance between $A_{1}$ and $A_{2}$,
$$\mathrm{Dist}_{\mathcal{D}}^{A_{1}, A_{2}}(l) = \left\vert \Pr \left[ \mathcal{D}^{A_{1}(\cdot)}(1^l) = 1 \right] - \Pr \left[ \mathcal{D}^{A_{2}(\cdot)}(1^l) = 1 \right] \right\vert$$

We know that the statistical distance between two functions is
$$2\mathrm{Dist}^{F_{1}, F_{2}}(l) = \sum_{f}\left\vert \Pr\left[ k \gets \{\, 0,1 \,\}^l, F_{1}(k, \cdot) = f(\cdot) \right] - \Pr \left[ k \gets \{\, 0,1 \,\}^l, F_{2}(k, \cdot) = f(\cdot) \right] \right\vert$$
However, I have no ideal how to define the statistical distance between two probabilistic algorithms.


texts: Can two anonymous parties determine whether they interacted before, without being able to link encounters?

texts:
Assume an anonymous communication system in which anonymous parties randomly meet in pairs to exchange information.

How could two anonymous parties determine whether they have interacted before, without being able to re-identify each other?

(I can only tell whether or not we met before, but I cannot link this meeting to any specific anonymous meeting in the past or future)

Some parties may be dishonest. In that case, we can tolerate false negatives (an honest party thinking that they haven't yet interacted with someone when they in fact have), but we cannot tolerate leaking the number of times they interacted (because this might make a party re-identifiable). In other words, honest parties should be able to tell whether they have met, but no party should be able to re-identify a given party.

The following protocol does not fulfill these requirements because it could leak the number of previous meetings to a dishonest party (see Maeher's comments):

every party has a store of secrets (which starts empty)
whenever two parties meet they use private set intersection to determine whether they share a secret. If they don't, then they haven't met before and they establish a shared secret. If they do then they met before and they do not share additional secrets.

EDITED in reponse to Maeher's comments


texts: Truncating ciphertexts on ring-LWE schemes

texts:
On the section 5.4 of the paper Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme, the authors explain how to discard some bits of the ciphertexts to get smaller ciphertexts and smaller evaluation keys.

The function Discard simply takes a ciphertext $c$ and an integer $i$ (number of words to be discarded) and returns

$\lfloor w^{-i}c \rfloor$

where $w$ is the number of bits of each word.

But, since $c$ is a polynomial with integer coefficients (coefficients in $\mathbb{Z}_q$), I don't understand how this function is discarding bits. To me, it seems like it is only zeroing all the coefficients whose absolute values are smaller than $w^i$.

I also checked the reference from where this technique of truncating ciphertext was extracted, named the paper Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP, but its explanation does not make sense to me as well.

So, do you know how this technique works? Could you give more details or show me what point I am interpreting wrong?


texts: Is it possible for Alice and Bob to both sign a message "simultaneously"?

texts:
Let's say that there is a message which is considered valid if signed by both Alice and Bob.

Alice could sign the message and then give it to Bob, so that he can sign it and give it back to her.

But, for various reasons, Alice doesn't want Bob to have a fully-signed message that she doesn't also have. If she just signs it and sends it, he could sign it and not send it back.

Is there some way that both of them can sign the message (maybe interactively?) so that it doesn't become valid for Bob if it isn't also valid for Alice?

(This could be done by a trusted third party who would simply escrow the message until it had received both signatures, and then release both signatures to Alice and Bob. Of course, I want a solution without a third party.)


texts: Functional difference between stream cipher, XOF, seed expander, KDF, etc

texts:
This question is a request for terminology clarification.

In a canonical XOF interface, the output can be extended as much as needed, but does input has to be variable-length or can be fixed-length in certain constructs?

SHAKE{128|256} are the first well-known standardized XOFs, there are many ad-hoc constructs before it such as OAEP-MGF, AES-CTR, RC4/ChaCha20-based arc4random() function.

For AES-CTR and RC4/ChaCha20, are they also XOF in any sense? If not, what are they strictly speaking?
What does a seed-expander do? Does it take a fixed/variable-length bitstring as input and produce another fixed/variable-length bitstring as output?
What exactly is the relationship between XOF, Seed-Expander, (optionally bring up KDF).


texts: Is it ever unsafe to compress an EC point?

texts:
I am working with a library that outputs EC points in uncompressed form.  To save space, I'm considering modifying said library to use compressed EC points.  Assuming that I keep track of the sign bit prior to compression, is there any risk in compressing said point?

I read this Q and related answer, but want to ensure that I may not be opening the door for other issues.


texts: Is this test result sufficient to steer clear from this RNG for cryptographic applications?

texts:
I'm not really interested in this PRNG.  I'm more interested in understanding what it takes to fail the security threshold for cryptographic applications.  I'm taking the C PRNG as an example.

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
  unsigned int random;
  srand(1);
  for (;;) {
    random = rand();
    fwrite(&random, sizeof random, 1, stdout);
  }
}

Here's the summary of a small crush by TestU01:

========= Summary results of SmallCrush =========

 Version:          TestU01 1.2.3
 Generator:        crand
 Number of statistics:  15
 Total CPU time:   00:00:21.67
 The following tests gave p-values outside [0.001, 0.9990]:
 (eps  means a value < 1.0e-300):
 (eps1 means a value < 1.0e-15):

       Test                          p-value
 ----------------------------------------------
  1  BirthdaySpacings               1.1e-14
  2  Collision                        eps
  3  Gap                             4.2e-9
  6  MaxOft                           eps
  6  MaxOft AD                      1 - eps1
  7  WeightDistrib                    eps
 10  RandomWalk1 H                    eps
 10  RandomWalk1 M                    eps
 10  RandomWalk1 J                    eps
 10  RandomWalk1 R                    eps
 10  RandomWalk1 C                    eps
 ----------------------------------------------
 All other tests were passed

Is this enough to make me steer clear from C's rand()?  What if it had failed only a single test?


texts: Rolling Hash function over untrusted data: how to preserve statistical splitting properties?

texts:
I would like to know if there is a construction for a Rolling Hash function to be used to split the received untrusted data in chunks.
The data is split whenever the hash function drops below a certain threshold and the splitted data is then used to build trees for efficient indexing of such data.
In my case the input data is however untrusted and I need a rolling hash construction that preserves the mean splitting size even under adversarial attacks on the data (which would otherwise make the trees highly unbalanced).
From what I have seen rolling hashes are mainly used in backup applications for deduplication purposes but they operate under the setting of non-adversary data.
Thank you in advance.


texts: Different tools return different ciphertext value for equal input

texts:
I have a Luna G5 Safenet HSM and I want to encrypt a text file containing testtest with 3DES-ECB algorithm. So in the first step I generate a 3DES key on the HSM:

A view of the key generator tool:

Select type of key to generate
[ 1] DES     [ 2] DES2   [ 3] DES3             [ 5]  CAST3
[ 6] Generic [ 7] RSA    [ 8] DSA   [ 9] DH    [10]  CAST5
[11] RC2     [12] RC4    [13] RC5   [14] SSL3  [15]  ECDSA
[16] AES     [17] SEED   [18] KCDSA-1024   [19] KCDSA-2048
[20] DSA Domain Param    [21] KCDSA Domain Param
[22] RSA X9.31                                 [24] ARIA
[25] DH PKCS Domain Param [26] RSA 186-3 Aux Primes
[27] RSA 186-3 Primes
> 3

Enter Is Token Attribute [0-1]: 1
Enter Is Sensitive Attribute [0-1]: 1
Enter Is Private Attribute [0-1]: 1
Enter Encrypt Attribute [0-1]: 1
Enter Decrypt Attribute [0-1]: 1
Enter Sign Attribute [0-1]: 1
Enter Verify Attribute [0-1]: 1
Enter Wrap Attribute [0-1]: 1
Enter Unwrap Attribute [0-1]: 1
Enter Derive Attribute [0-1]: 1
Enter Extractable Attribute [0-1]: 1

Generated DES3 Key handler: 14

After that I checked its attributes:

G:\LunaG5> Cmu.exe getattribute -password 1234567

Select object to query

Handler Label
14      Generated DES3 Key

Enter handler (or 0 for exit) : 14
class=secretKey
token=true
private=true
label=Generated DES3 Key
value=86016e6572617465642044455333204b6579000000000000
keytype=3DES
id=
sensitive=true
encrypt=true
decrypt=true
wrap=true
unwrap=true
sign=true
verify=true
derive=true
startdate=
enddate=
extractable=true
local=true
neverextractable=false
alwayssensitive=true
modifiable=true

As you see above, the value of my generated 3DES key is:

86016e6572617465642044455333204b6579000000000000

Well, in the next step, I encrypt my text file using 1-my HSM, 2-OpenSSL, 3-this online tool. The weird thing is that the output of all are different with each other!

1-My HSM:

Enter your choice : 40
[ 1] DES-CBC       [ 2] DES3-CBC      [ 3] DES3-CTR      [ 4] CAST3-CBC
[ 5] DES-ECB       [ 6] DES3-ECB      [ 7] AES-CTR       [ 8] CAST3-ECB
[ 9] RC2-ECB       [10] RC2-CBC       [11] CAST5-ECB     [12] CAST5-CBC
[13] RC4           [14] RC5-ECB       [15] RC5-CBC       [16] RAW-RSA
[17] DES-CBC-PAD   [18] DES3-CBC-PAD  [19] DES3-CBC-PAD-IPSEC
[20] RC2-CBC-PAD   [21] RC5-CBC-PAD   [22] CAST3-CBC-PAD [23] CAST5-CBC-PAD
[24] SEED-ECB      [25] SEED-CBC      [26] SEED-CBC-PAD
[27] AES-ECB       [28] AES-CBC       [29] AES-CBC-PAD   [30] AES-CBC-PAD-IPSEC
[31] ARIA-ECB      [32] ARIA-CBC      [33] ARIA-CBC-PAD
[34] RSA-PKCS      [35] DES3-CFB8     [36] DES3-CFB64    [37] DES3-OFB
[38] AES-CFB8      [39] AES-CFB128    [40] AES-OFB       [41] ARIA-CFB8
[42] ARIA-CFB128   [43] ARIA-OFB      [44] AES-GCM       [45] XOR-BASE-DATA-KDF
[50] RSA-OAEP      [51] ECIES         [52] ARIA-CTR      [53] SEED-CTR
Select mechanism for encryption: 6
Enter name of file to encrypt: plain.txt

Enter key to use (-1 to list available objects) : -1

Handle 14 -- label: Generated DES3 Key

Enter key to use (-1 to list available objects) : 14

Encrypted data stored in file ENCRYPT.BIN
Status: Doing great, no errors (CKR_OK)

HSM output file content:

2-OpenSSL:

D:\GnuWin32\bin>openssl.exe enc -des-ede3 -e -in in.txt -out out.bin -K 86016e6572617465642044455333204b6579000000000000 -iv 0

OpenSSL output file content:

3-Online tool&Output:

Why I have different outputs?


texts: List of post quantum cryptography protocols

texts:
What are the post quantum cryptography protocols that have been proposed until now?

I know about McEliece cryptosystem, and LWE scheme. What are the others? Can you provide me a list or a website containing such list?


texts: How to verify the integrity of RSA encrypted messages?

texts:
I need to encrypt messages using PublicKeyCrypto and send it to the server, where the message should be decrypted. I'm aware of the Padding Oracle Attack and want to apply a server side integrity check of the incoming cipher messages. In AES there is the so called CCM mode, which performs the integrity checks implicitely. Is there something else for RSA decryption?

I'm using the 'javax.crypto.Cipher' library.


texts: Why is the second XOR operation in OCB mode necessary?

texts:
In Rogaway's OCB mode, the offset (derived from the key) ist XOR-added twice: Once to the plaintext block, and a second time after the Encryption.

I am wondering, why the second XOR operation is necessary. The design is  I believe inspired by the XEX construction introduced by DESX. In that case, the second XOR is needed to prevent a meet-in.the middle-attack, but that's not really a problem for OCB.


texts: Why do you need to apply hash over DH shared key?

texts: I`ve read multiple times that it is not safe to use the shared key resulted from DH key exchange directly and that you need to do a KDF or hash over it and then use the result as a key. Why is it not safe to use the shared key directly?


texts: What role plays Quantum Fourier Transformation in Shor's integer factorization algorithm?

texts: I cannot seem to understand the role or goal of Quantum Fourier Transformation in Shor's integer factorization algorithm. Is it used to collapse all quantum states into one, in which it has a factor of a given input $n$?


texts:
We have SampleLeft function in lattice trapdoors as

Algorithm $\textbf{SampleLeft}(A,M_1,T_A,u,\sigma)$:

$\textbf{Input}$: a rank $n$ matrix $A$ in $\mathbb{Z}^{n×m}_q$ and a matrix $M_1$ in $\mathbb{Z}^{n×m_1}_q$ , a “short” basis $T_A$ of $\Lambda^{\perp}_q(A)$ and a vector $u \in \mathbb{Z}^n_q$, a gaussian parameter $\sigma > \|\widetilde{T_A}\|.\omega(\sqrt{\log(m+m_1)}$

$\textbf{Output}$: Let $F_1$ := $(A | M_1)$. The algorithm outputs a vector $e \in \mathbb{Z}^{m+m_1}$ sampled from a distribution statistically close to $\mathcal{D}_{\Lambda^{u}_q(F_1),\sigma}$ such that $F_1 . e = u$

My question is can we sample a vector $e$ using the above algorithm(or making some changes) such that $e . F_1 = u$ holds? The dimensions of the matrices change accordingly.


texts: RSA digital signature vs authenticated cipher

texts:
I want to provide both confidentiality and integrity for data at rest (many large files stored on disk).

I plan to encrypt the data using AES, which will cover the confidentiality requirement.

So the issue is how to provide integrity:

Instead of AES, use AES-GCM-SHA256 (authenticated cipher). My understanding is that this produces an HMAC (keyed hash) of the encrypted data (and IV), and appends it to the end of the file
After encrypting each file, produce an RSA digital signature and either save it as a seperate file or append it to the encrypted file

What are the merits and disadvantages of each option?


texts: Can a service that can only sign text, be used for encryption/decryption?

texts:
This is somewhat a theoretical question, but I am also interested in whether this is possible in practice.

Assume, that there is a service that possesses a private RSA key, and can sign any data with that key, after the key is unlocked with a password. Something similar to the ssh agent. Once unlocked, you can talk to this service through a protocol, but don't have access to the (unlocked) private key in any way. You hand over the data to sign to the service, and it returns the signature. And you also have the corresponding public key.

Now, the question is, can this service be used for encryption and decryption? I am thinking of something like this for encryption:

You unlock the service with a password.
You have plaintext you want to encrypt.
You generate a random blob of data.
You ask the service to sign this data. You verify the signature using the public key.
You treat the signature (or some hash of it) as a key for symmetric encryption/decryption, e.g. as an AES key.
You encrypt the plaintext with this key, and get a secret.
You store

the secret, and
the random data you used to create the signature.

When you want to decrypt a secret:

You unlock the service with a password.
You take the stored random data.
You ask the service to sign it with its private key. You verify the signature using the public key.
You treat the signature (or some hash of it) as an AES key.
You decrypt the secret with the AES key.

I admit, that I don't know much about cryptography, but to me, this seems like a good (=secure) algorithm for solving the problem, at least in theory. Am I missing something? Is this already known/used somewhere in practice?


texts: Password manager that uses a mix of long and short key derivation functions

texts:
I was reading "A Convenient Method for Securely Managing Passwords, Halderman et al., 2005". In short, the authors say to do the following:

cache = very_long_key_derivation_function(salt,master_password)
save the cache on disk
password_for_site_a = short_key_derivation_function(salt,site_a|master_password|cache)
password_for_site_b = short_key_derivation_function(salt,site_b|master_password|cache)

where

very_long_key_derivation_function is some key derivation functions tuned to require approx 2 minutes
short_key_derivation_function is some key derivation functions tuned to require 1 second.

This forbids to site_a to brute force the secret in order to find the password of site_b (since each try requires 2 minutes), still allowing fast time to calculate the password of a website. If the cache file is stolen, is still necessary to guess the master_password to know the derived passwords.

There are two problems with this method:

the master_password is used each time the user needs the password of a certain site
in order to change the master password (it is used often, it could be seen), all the derived passwords must be changed

I would like to modify the schema in the following way:

k1 = very_long_key_derivation_function(salt,master_password_1)
k2 = short_key_derivation_function(salt,master_password_2)
cache = k1 xor k2
save cache on disk
password_for_site_a = short_key_derivation_function(salt,site_a|(cache xor k2))
password_for_site_b = short_key_derivation_function(salt,site_b|(cache xor k2))

In this way master_password_1 is used only once (the first time the password manager is used), while master_password_2 is used each time the user needs a password for a site. The derived passwords do not depend on master_password_2. Assuming that master_password_1 can not be stolen (since it is used only once), in order to steal a site password both the cache file and master_password_2 are needed. Also, it is possible to change master_password_2 if the user suspects that somebody saw him writing it, by computing:

k1 = very_long_key_derivation_function(salt,master_password_1)
k3 = short_key_derivation_function(salt,master_password_3)
cache = k1 xor k3.
save cache on disk

when the user will use master_password_3 the derived site passwords will be the same as before.

I would use some string derived from the username as a salt, and argon2 as key derivation function. Do you think this could be a good method to manage passwords?


texts: Given enough length, which string of symbols will have the greatest entropy?

texts:
Which arbitrarily long string will have the greatest entropy?

A string constitued of random letters, with each letter having a probability of being picked equal to its frequency of apparition in the english language.
A text written in english.

Let's assume there's only 27 different symbols (letters+space), and each symbol is coded on 8 bits.


texts: public key cryptography and digital signature

texts:
I read the following from Understanding Public Key Cryptography on Microsoft TechNet:

  Using a private key to establish identity shows that the full
  encryption and decryption operation was accomplished successfully.
  Showing a full operation means that plaintext would have to be
  encrypted to ciphertext using a private key and then decrypted back to
  plaintext using the corresponding public key. If this operation is
  successfully shown, the use of the private key, and only the private
  key, is demonstrated.

  To show a successful encryption and decryption operation, the
  plaintext before the encryption and decryption operations must match
  the plaintext after the encryption and decryption operation. Both sets
  of plaintext must be compared directly and shown to match absolutely.
  There must be a control that is used for comparison and validation.

I'm unable to understand what actually is being said here.

Can somebody please explain this in somewhat simpler terms and with a simple example?


texts: Find the initial state of LFSR with n non-consecutive output bits

texts:
Let's say I have (e.g.) $32$ output bits of an $128$ bit LFSR whose period length is $2^{128} - 1$. Those output bits are chosen arbitrarily, so I do not have any consecutive bits.

Let us call the set of of outputs $Z = \{(i,z_i) | z_i \leftarrow s_0 \cdot A^i\}$, where $s_0$ is the initial state, $A$ describes the companion matrix of the LFSR and $z_i$ is the $i$-th output bit (i.e. the left-/rightmost element of the vector $z_i$).

It should be possible to create some sort of equation system to determine (possible) values for the initial state. But so far I am unable to think of a way, since we do not know the feedback polynomial.

If we had 32 consecutive output bits we could chose 96 other bits at random and clock the LFSR backwards - but in this special case that is not applicable.

Each output $z_i$ is the feedback from the previous state. But since we do not know the polynomial, how can we now create a set of equations?


texts:
EDIT: Fixed for clarity of intention

I was reading "The FFX Mode of Operation for Format-Preserving Encryption" when I came across Figure 1 (see below). It's obvious why it's reversible (top-down then down-top) but it's not clear why it should strictly be bijective instead of not-injective or not-surjective? What rules out the possibilities of collisions or skips that make it strictly one-one in both directions?

For example: The round function (Fk) can be block cipher or hash based and we pick a subset of output bits into the next round. A collision at say, Fk(n,T,0), in round zero would then map two inputs at the top to a single input at the bottom. Why is that not an issue? Sorry if I'm missing something but it's been a long night and have missed my morning coffee.

Example Feistel network from FFX paper:


texts:
I am studying LogSpace Merkle Tree Traversal algorithm in "Post Quantum Cryptography". I don't understand the Table 1 on page 58.

My question is: Why within of the $2^h$ rounds for $NEED_h$ exist only one $TAIL$, if tail in the page 42 is defined than intermediate nodes in $STACK_h$?

  Algorithm 2.1 Treehash

  Input: Height $H\ge2$
  Output: Root of the Merkle tree

  for $j = 0,…,2^H-1$ do
   a) Compute the $j$th leaf: $NODE_1 \leftarrow LEAFCALC(j)$
   b) While $NODE_1$ has the same height as the top node on $STACK$ do
        i. Pop the top node from the stack: $NODE_2 \leftarrow STACK.pop$
        ii. Compute theirparent node: $NODE_1 \leftarrow g(NODE_2||NODE_1)$
   c) Push the parent node on the stack: $STACK.push(NODE_1)$
  Let $R$ be the single node stored on the stack: $R \leftarrow STACK.pop()$
  Return $R$

$STACK_h$ is defined to be an object which contains a stack of node values $STACK_h.initialize$ and $STACK_h.update$ will be methods to setup and incrementally execute treehash.The period starting from the time $STACK_h$ is created and ending at the time when the upcoming authentication node is required to be completed is denoted than $NEED_h$.


texts: Attacking CBC with predictable but encrypted IV

texts:
Let P be a secure block cipher, eg AES-128.

Let's say a server has a CBC encryption oracle which uses an attacker-selected yet unique nonce to generate the IV for each message = P(key, nonce). The same key is used to generate the IV from the nonce as to encrypt the message.

This system is not semantically secure against an attacker who can choose plaintexts and nonces (with the stipulation that all nonces must be unique).

A similar system with predictable (but unencrypted) IV has the vulnerability where an attacker can make a guess as to the contents of a target ciphertext.

Is there a comparable attack on this system?

Does this attack still hold if the nonce is merely predictable (ie a counter) instead of attacker selected?

Can this attack work if there is a restriction against sending blocks containing zero-vectors to the oracle?


texts: What is scale-invariance notion of a fully homomorphic encryption scheme?

texts:
I read this paper https://eprint.iacr.org/2012/078.pdf and I didn't understand what does the author mean with scale-invariance perspective.

The perspective in which we view the ciphertext is accomplished by the algorithms used ? I refer to BitDecomp, PowersOfTwo and the tensor product.

Or the perspective is achieved by decryption with divide q ?

Should I view scale invariance perspective of the ciphertext as I view Fourier transform of a signal ?


texts: Encoding of the message in Regev encryption

texts:
In public key encryption from LWE, we do the following steps

$\textbf{PKE.KeyGen($1^n$)}$ takes as input the security parameter n, samples $A \leftarrow \mathbb{Z}_p^{n \times m}$ and $\textbf{e} \leftarrow \chi^m$, and outputs a key-pair $(pk,sk)$ where $sk = s \in \mathbb{Z}^n_q$ and $pk = (A,s^T\cdot A + \textbf{e}^T)$.
$\textbf{PKE.Enc($pk = (A,b^T),b$)}$ takes as input a public key $(A,b^T)$ and a message $a \in {\{0,1}\}$, samples a short vector $r \leftarrow {\{0,1}\}^m$, and outputs a ciphertext $(A\cdot r,b^T\cdot r + a \cdot \lfloor\frac{q}{2}\rfloor)$.

If we now assume that the secret $s$ is a matrix instead of a vector, how can we deterministically encode the message $a$ so that we can recover it during decryption? The error term will also be a matrix in this case where each column is chosen independently of the other from some error distribution.


texts: Is there any way to hire someone to generate a sufficiently small hash of a value + nonce, without knowing value nor nonce?

texts:
Suppose I have a 128-bit value X, and I want a keccak_256(X || nonce) sufficiently small to require a lot of work. Is there any simple/obvious way (possibly interactive) way to hire someone to find me such a nonce, in a way that he doesn't learn about X, and that he doesn't even know what nonce he produced?

I can't fit that particular problem on what zkSnarks seem to enable one to do.


texts: Is my way safe to remove SSL CA Cert by DHT and PoW NodeID for a decentralized system?

texts:
To implement a decentralized system, I wrote a TLS like P2P net stack.
The main idea is removing CA Cert from the whole system by using a DHT for Naming and Key Exchange.
I am not a crypto expert, so if there's any flaw please point it out for me here or Github

First, I use an Elliptic Curve for asymmetric encryption and AES-256-CBC for symmetric encryption.

DH-RPC NodeID is generated by hash of Node PublicKey and an Uint256 Nonce:

NodeID := sha256(blake2b-512(NodePublicKey + Uint256Nonce))

I refer to S/Kademlia's idea to define the number of consecutive 0s in front of the NodeID as difficulty and to impose a minimum limit on the difficulty of the NodeID allowed to be stored on the DHT.
DHT is used to hold the NodeID:PublicKey NodeID:Addr map. NodeID and Nonce are sent to do ECDH getting shared secret after TCP connection established.

GenECDHSharedSecret(APub, BPriv) == GenECDHSharedSecret(BPub, APriv)

The main procedure is described as sequence chart:

Because in the decentralized system NodeID is the URI, not "Bob/Alice.com". So anyone tries to fake NodeB by overwriting the address or public key on DHT without the private key of NodeB will be failed to get the correct shared secret.

Github: https://github.com/CovenantSQL/CovenantSQL/tree/develop/rpc

Known issues:

Add a random uint64 along with NodeID and Nonce sent to remote to add some random for the shared key.


texts: I have studied linear cryptanalysis for block ciphers, but i did not understand how it works on hash functions. Can you give me an explanation of this attack on hash functions?


texts: Can one have an authentic, but repudiable, message without a previously shared secret?

texts:
Bob wants to send a message to Alice, such that Alice can be sure that the message came from Bob, but can't prove it to anyone else.

If I understand right, this means that the same message could have possibly also been constructed by Alice, but not by Eve (who can observe, change, remove and inject messages).

The usual solution would be a MAC using a shared secret, but suppose there is no such shared secret (for example, as Bob and Alice didn't communicate before).

We can provide, however, a public-key infrastructure of some kind, so Alice and Bob know (or can obtain securely) each other's public keys. (Maybe multiple keys per owner, if needed.)

Is it possible to create some (non-interactive, i.e. single-message) protocol such that the following conditions are fulfilled?

Bob can construct a message using only his private key (maybe also his public one) and Alice's public key.
Alice can use her private key (maybe also her public one) and Bob's public key to verify that this message is from Bob.
Eve, who knows neither Bob's nor Alice's private key, can't construct a message which will pass Alice's check.
Alice can construct the same message using her private key (maybe also her public one) and Bob's public key.

What kind of primitives are needed here?

I don't require Bob's message to be encrypted, but your protocol might do so, if this is easier to realize. I only care about the authentication & repudiation part.

(If these conditions are not sufficient or not necessary for authentication without non-repudiation, please point this out, too.)

(This question is inspired by Can I use PGP to sign a message without providing cryptographic non-repudation?, which asks for a solution of a similar problem using OpenPGP and signatures, but doesn't actually specify the requirements. This one is wider and more on a theoretical level.)


texts:
I am trying to figure out what typical formats and sizes, etc. are, for storing ECC public and private keys.
Some quick research turned up X9.62 (to which I don't have access) and SEC1. But then there is also X.690 which includes DER and of course ASN.1. And let's not forget PEM.
If somebody could shed some light onto the relations of these things and what is commonly used I think it would be useful.
Broadly, the question that I am trying to get answered is: What do I need to implement to decently support ECC. That would include ECDH and transferring public keys over the wire to maybe a TLS or SSH implementation but also importing and exporting of keys generated using other tools.
Somewhat related: Public-key format for ECDSA as in FIPS 186-4?


texts:
I was reading a paper on attacks on RSA variants, and the paper equates $\phi(N) = (p^2-1)(q^2-1)$. Before, I have always seen $\phi(N) = (p-1)(q-1)$ and don't understand why it is different here.
I have added a screenshot of one part where they mention this below. Thanks :)