texts: Elliptic curves with pairings at 128-bit security in libpbc?

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

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

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

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

Any tips would be appreciated!

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


texts: Why does the prover in an interactive proof run in exponential time with the space of the computation?

texts:
I'm currently trying to gain an understanding of verifiable computation and the strengths and weaknesses of past approaches.

In particular, I've been watching the following YouTube video which talks about interactive proofs as a way of verifying knowledge of a computation. On the slide appearing during time 11:55, it mentions that the prover requires exponential time in the space of the computation. Could anyone explain how this is the case?

I'm also confused as to the statement which says that every deterministic computation has an interactive proof.

I've tried reading the papers below but can't seem to find a clear explanation of these results. Any help would be much appreciated!

References:

  Lund, Carsten, et al. "Algebraic methods for interactive proof
  systems." Journal of the ACM (JACM) 39.4 (1992): 859-868.

  Shamir, Adi. "Ip= pspace." Journal of the ACM (JACM) 39.4 (1992):
  869-877.


texts:
I am familiar with white box cryptography, but somehow I still fail to see its potential applications? Which situations would necessitate using it? Maybe you can even give me an example or two?

I know it is used to protect keys, but one could say: “Hey, come-on, derive a scheme where you don't need secret key”. Or, we could simply use what we have: public key encryption. All that’s to it is to maybe generate session keys and then encrypt/decrypt things using those keys.


texts: Are there any misuse-resistant asymmetric encryption schemes?

texts:
The notion of misuse-resistant authenticated encryption (MRAE) was defined in the symmetric setting by Rogaway and Shrimpton, along with the SIV mode that achieves it. The idea being that modern authenticated encryption cipher modes require a unique nonce and fail more or less catastrophically if a nonce is reused. An MRAE cipher mode maintains a strong definition of security even in this case, although not semantic security.

If we look at digital signatures, then there are also unique values that must be used. This has been a classic vulnerability in ECDSA, e.g., in the Playstation 3 hack or the attacks on Android Bitcoin wallets. The Ed25519 signature scheme is deterministic to avoid these problems, replacing the random value with a hash/PRF over the secret key and the message. RFC 6979 proposes a deterministic variant of ECDSA that is along similar lines. Both seem close in spirit to the SIV construction: replacing a random/unique value with a psuedorandom one generated from the message and a secret key.

But what about asymmetric encryption? For RSA it is common to use either PKCS#1 v1.5 or OAEP padding. Both require random elements for security, and it seems to me that both would not achieve semantic security (IND-CPA) if these repeat as RSA is otherwise deterministic. But it is not clear to me to what extent security is lost in this case. While the deterministic authenticated encryption (DAE) that SIV ensures in this case is not appropriate for public key encryption, does RSA-OAEP achieve the notion of deterministic privacy described in Appendix B of http://web.cs.ucdavis.edu/~rogaway/papers/keywrap.pdf? If not, has anyone ever considered an SIV-like construction for RSA? On the face of it, it would seem you could do the same trick and replace the random seed value in OAEP with the output of a PRF calculated over the message and the private key (and potentially a random nonce too). Would this be secure?


texts:
I have come across some security implementations in which party A will compute MD = sha256(secret + rand) and transmit MD and rand to a counterpart B. If the second party knows the secret, then when it computes sha256(secret + rand), it will match that from sender A and validate it.

This may be a loaded question, but is this secure at all? Meaning, would it be very hard for an attacker to discover the secret given the resultant hash and the random number?

Part 2: Another potentially loaded question
Would it be more/less secure to instead use an hmac using the secret as the 'data'? So HMAC(rand, secret) ?

The goal of both security systems is to ensure that both A and B possess the same key K without transmitting it, but is either more secure? Are these implementations 'traditional' or more of a 'cluge'?


texts: Weak one way functions from strong one way functions

texts:
I'm stuck in a simple question about weak one way functions.

Suppose $f(x)$ is strong one way, is $g(x)=f(x)_0$, i.e. taking the first bit of $f(x)$ a weak one way function? Intuitively, it is, because for any adversary $\mathcal{A}$ the probability of inverting $g$ is $\frac{1}{2} + \epsilon$. So it seems safe to say $g$ is $\frac{2}{3}$-one way.

But apparently one cannot reduce inverting $g$ to inverting $f$, which leaves me no way to prove that statement by reduction. Am I getting it wrong?


texts: What is the maximum number of shares in Shamir's Secret Sharing?

texts:
I am using codahale’s Shamir's Secret Sharing implementation of Shamir's secret sharing from Github.

I am using this to generate a 32 byte random key encryption key (KEK) to encrypt a 32 byte data encryption key (DEK) which is used to encrypt the data on the Kafka producers. The DEK would be part of the payload, but the secret KEK is divided into max shares so that it can be distributed among consumers to recompute it.

What is the maximum number of shares that can be created with a threshold of 2 parts?

If I have to achieve this strategy for 1000 clients/parties, how can I do this?


texts: Chosen Plaintext Attack and Chosen Multiple-Plaintext Attack

texts:
The original CPA game:

The adversary gives two arbitrary messages $m_0$ and $m_1$ to a challenger;
The challenger encrypts an arbitrary message $m_u$, $u∈\{0,1\}$ , and sends the ciphertext to the adversary;
The adversary outputs the guess $u$.

Now I give a revised version of the above CPA game:

The adversary gives two arbitrary sets of messages $M_0$ and $M_1$ to a challenger, where $|M_0|=|M_1|$, and each pair of counterparts are of equal size;
The challenger encrypts an arbitrary set of message $M_u$, $u∈\{0,1\}$, and sends the ciphertexts to the adversary;
The adversary outputs the guess $u$.

If a public-key encryption scheme is CPA-secure is it also secure in this revised version of CPA game?


texts: Are there any LFSR-based ciphers with variable feedback polynomials?

texts:
All LFSR-based stream ciphers that I know of use a fixed feedback polynomial (i.e. the taps are always in the same position). I know that, at least for non-trivial output lengths, it is necessary to ensure that the polynomial is primitive to avoid creating an LFSR with a short cycle. Are there any published stream ciphers which use a secret-dependent or otherwise variable feedback polynomial? I am only aware of one proposed modification to A5/1. If there are good reasons why this design is so rare (just as there are good reasons why data-dependent rotations are rare), what are they?
I can think of a few possibilities:

The security improvement is too slight to be worth the added implementation complexity.

Deterministically selecting a new feedback polynomial with good properties on-the-fly is difficult.

There simply is not enough research into the behavior of LFSRs with variable taps.

To the best of my knowledge, an $n$-bit LFSR requires $n$ bits of keystream to determine the state. With secret feedback polynomials, $2n$ bits are required (using the Berlekamp-Massey algorithm to find the tap positions). Wouldn't this be a simple way to make known-plaintext attacks harder?
Although I'm most curious about LFSRs, an answer describing NLFSRs would also be interesting.


texts: Variant of Schnorr Protocol (Difference pair of response and verification)

texts:
When I am trying to learn deeper to Schnorr Protocol. I found that for deference there is more than one response and verify pair. But I am not sure am I right.

We will use Schnorr Protocol to prove the knowledge of $x$ in $y=g^x$. Here is the details of Schnorr Protocol, first prover send $t=g^r$ where $r$ is a random number to verifier. Verifier send challenge $c$ to prover, next step prover will calculate response and let verifier calculate is it correct by a function. Here is the question.

For $y=g^x$, $t=g^r$ and $c$, we have 3 equation below.

$g^x g^{rc}=yt^c$ $\rightarrow$  $g^{x+rc}=yt^c$
$g^{xc} g^r=y^ct$ $\rightarrow$  $g^{xc+r}=y^ct$
$(g^x g^r)^c=y^ct^c$ $\rightarrow$  $g^{c(x+r)}=(yt)^c$

Can I say I can choose either one of that pair to finish the protocol?

response $s=x+rc$, verify $g^s=yt^c$
response $s=xc+r$, verify $g^s=y^ct$
response $s=c(x+r)$, verify $g^s=(yt)^c$

Am I correct?


texts: Is the "decapsulate" function from lattice based cryptography homomorphic?

texts:
Observing the code example from pqcrypto-kyber, is the decapsulate function $d$ homomorphic?

If $d(ct, sk_i) = ss_i$, is it true that $d(ct, \sum_i sk_i) = \sum_i ss_i$ ?


texts:
Pls I need explanation on How i can design a Cryptography that use multiple passwords or passphrase to open a safe(Lock). For example, if i need five people to unlock a secured device whereby all the five need to enter their individual password before the device can be opened.

Please how can this be done? I don't have much knowledge on this, hence i wouldn't expect all the answers right away. I would appreciate a link, or book or somewhere i can read details about it.
Thanks.


texts: Is there an easy way to calculate "d" in the RSA algorithm?

texts:
Quite frankly, it is a pain to use the Extended Euclidean Algorithm to calculate d (the private exponent) in RSA. The equation used to find d is:

$$ e  d \equiv1~(\mathrm{mod}~ \varphi(n)).$$

Does anyone have a way to solve for d using basic algebra or something simpler? If not, can someone explain how to use the Extended Euclidean Algorithm to find d?


texts: Number of operations for Elgamal cryptosystem

texts:
In page 408 of Hoffstein, Piper, and Silverman's Introduction to Mathematical Cryptography, it says

  "Roughly speaking, in order to achieve $k$ bits of security,
  encryption and decryption for Elgamal, RSA, and ECC, requires
  $\mathcal{O}(k^3)$ operations, while encryption and decryption for
  lattice-based systems requires only $\mathcal{O}(k^2)$ operations".

Why does Elgamal encryption and decryption require $\mathcal{O}(k^3)$ operations?


texts: Hash collision resistance requirements for Lamport signatures

texts:
According to the original paper, Lamport one-time signature scheme uses two one-way functions: $F$ and $G$. The former one, $F$, is used to create a public key by hashing elements of the private key (and also for hashing signature elements when verifying it); the latter, $G$, is used to hash a message when signing and verifying to get the number of bits corresponding to the number of pairs in keys.

As far as I understand, the requirement for $F$ is that it must be resistant to preimage attacks, and $G$, in addition to this, must also have collision resistance.

Given the standard hash function that satisfies all these requirements, I assume that $F$ and $G$ can be the same, e.g. SHA-256, which provides 256 bit security against preimage attacks and 128 bits security against collision attacks. Using it, we have the following key and signature sizes (described as dimensional arrays):

 Private key: [256][2][32]byte   (16 KiB)
 Public key:  [256][2][32]byte   (16 KiB)
 Signature:   [256][32]byte      (8 KiB)

My question is: if we're aiming for overall 128 bit security, can we reduce the output of $F$ to 128 bits instead of 256 bits, leaving $G$ as is. Does $F$ require collision resistance?

For example, if we use SHA-256/128 for $F$ and SHA-256 for $G$, this will give us the following sizes:

 Private key: [256][2][16]byte   (8 KiB)
 Public key:  [256][2][16]byte   (8 KiB)
 Signature:   [256][16]byte      (4 KiB)

Will this give us 128-bit security?

On the Wikipedia page describing Lamport signatures, there's this paragraph:

  For each private key $y_{i,j}$ and its corresponding $z_{i,j}$ public key pair, the private key length must be selected so performing a preimage attack on the length of the input is not faster than performing a preimage attack on the length of the output. For example, in a degenerate case, if each private key $y_{i,j}$ element was only 16 bits in length, it is trivial to exhaustively search all $2^{16}$ possible private key combinations in $2^{15}$ operations to find a match with the output, irrespective of the message digest length. Therefore a balanced system design ensures both lengths are approximately equal.

However I fail to understand it: what are input and output and what message digest length (is it the length of output of $G$, $F$, or both), which part refers to the number of elements in keys and which part refers to the length of a single element? I'd appreciate a better explanation. Thanks!


texts: Arguing security of an encryption scheme

texts:
I have an encryption scheme which masks the message m by multiplying it with a secret random group element i.e $g^r \cdot m$. I should allow decryption and get $g^r$ if I have a valid secret key; otherewise I will only reveal $(g^L)^r$, where $L \in Z_n$ and $g^L$ is known to the adversary.

Is this secure? If yes, how can I argue about the security.


texts:
In several academic literature, the term Finished MACs is used frequently. I wonder, is it really a MAC or HMAC? I am looking at literature in TLS 1.2 vs. TLS 1.2 specs. The specs of TLS 1.2 Finished messages Here says:
   Structure of this message:

  struct {
      opaque verify_data[verify_data_length];
  } Finished;

  verify_data
     PRF(master_secret, finished_label, Hash(handshake_messages))
        [0..verify_data_length-1];

  finished_label
     For Finished messages sent by the client, the string
     "client finished".  For Finished messages sent by the server,
     the string "server finished".

As far as I know, if PFR are used, then it is HMAC not a MAC. Can you clarify to me please:

1) In TLS, is it Finished MACs or Finished HMACs? when some literature uses Finished MACs, is it correct (i.e. is it acceptable abbreviaton)?

2) Is it correct to use MAC instead of HMAc for short?


texts:
I would like to know if there is any security issue in sharing a secret key (of an asymmetric cryptography) between several users.

I know that this secret key is no longer "secret", so it's no longer valid for signature.

The advantage of doing that is to allow a user to send a message to many others (all those sharing the secret key) at a time by encrypting it with the corresponding public key.

But I don't know if this will induce security problems.


texts: Calculating IHVs from known message and hash output

texts:
Here is a somewhat silly and atypical problem I am currently facing. Usually, when it comes to hashes, one is bothered with finding collisions and preimages. My problem is, I need to find the IHV used to initialise the word buffers. The message and the hash function output are considered to be known.

Is there a non-bruteforce solution of this problem related to MD5 or SHA-1?


texts: Countermeasures to prevent integral cryptanalysis against 4-rounds AES

texts:
Integral cryptanalysis against 4-rounds AES is practical (Security of the AES with a Secret S-box). I did two experiments in order to find the impact and remove the integral distinguisher  of 4 rounds:

I replaced key addition $\oplus$ with $\boxplus$ (mod 32 bit)
I replaced the sbox with S1 Sbox in Clefia cipher  (same differential and linear probability).

but the integral distinguisher is still present.

Further reading lead me to find that BelT cipher (Finding Integral Distinguishers with Ease) has no integral distinguisher after three rounds.

Questions:

Where is the exploitable integral structure in AES-like?
What countermeasures are taken to remove integral distinguisher?
What is the advantage taken in BelT cipher?


texts: What is the name of this public key encryption cryptosystem?

texts:
I have been trying to find the name of a public key encryption cryptosystem that I learnt as an introduction to cryptography some years ago but the only scheme I could find was something similar but not the same called "Learning with errors". The scheme I am trying to find the name of works as follows:
Let $q$ be the private key where $q$ is a large prime.
Make a large list of $n$ items with each item being $q * z_n$ where $z_n$ is a different large and random prime number for each position in the list.
So $z_1$ may be $q*a$ and $z_2$ may be $q*b$ where $a,b$ are different primes.
Make this list the public key.
The sender will be sent the public key by the recipient and the sender will encrypt his message $m$ by first taking a $ ^nC_r $ set from the public key list where $r$ is a random number and $1 < r < n$.
Then they sum all the values in this $ ^nC_r $ set and add $m$ to this sum to get the encrypted message $t$.
Note: $m$ must be $ < q $ (we assume it is known that $q$ has some minimum value).
The encrypted value is sent to the recipient and to decrypt it they do $\frac{t}{q}$ to get $m$.


texts: Is the discretization of the Guassian distribution on torus still a discrete Gaussian distribution?

texts:
Let $\rho_s(x) = e^{-\pi x^2/s^2}$ be the Gaussian measures, then the discrete Gaussian distribution on $\mathbb{Z}$ could be defined as $D_{\mathbb{Z},s}(x) = \rho_s(x)/\sum_{n\in \mathbb{Z}}\rho_s(n)$.
In [Regev05], the distribution $\Psi_s(r)$ on torus $\mathbb{T}=\mathbb{R}/\mathbb{Z}$ is defined :
$$\Psi_s(r)=\sum_{k=-\infty}^{+\infty}\frac1s\cdot exp\left(-\pi \left(\frac{r-k}{s}\right)^2 \right), r\in \mathbb{T}$$
then, it can be discretized as a distribution on $\mathbb{Z}_p$ :
$$\overline{\Psi}_s(i) = \int_{(i-1/2)/p}^{(i+1/2)/p}\Psi_s(x)dx, \ \ i\in \mathbb{Z}_p$$
What I want to know is: if the $D_{\mathbb{Z},s} \mod p$ is the same as the $\overline{\Psi}_s$ on $\mathbb{Z}_p$ ?


texts:
I am trying to understand how Attribute Base Encryption (ABE) works. So, after downloading libfenc library from here, I built the source code on Ubuntu 12.04 without any error.  Afterward, I tried to follow the library commands as follow:

Create the master secret and public parameters:
abe-setup -m CP

Generate key for user's attribute:
abe-keygen -m CP -a 'ONE,TWO,THREE,FOUR,FIVE' -o userCP.key

Encrypt the input file under a given policy:
abe-enc -m CP -i filename.txt -p "((ONE and TWO) or THREE)" -o outfile

With each executed command a file is generated (three files among which the encrypted file is created).
Now, when I try to decrypt the encrypted file "outfile" using:
abe-dec -m CP -k userCP.key -f outfile.cpabe
no file is generated at all, and I don't know if the encryption mechanism works or not !! does the code works or not !! am I missing something ?
EDIT (from comment)
Through this question I am seeking understanding the ABE encryption. It is not about the library AT ALL. it is about the basic understanding of the ABE mechanism. Believe me, the code itself is useless.


texts: How to turn adversary against encryption of zeroes into adversary against random bits?

texts:
I recently read the article Nonce-Based Symmetric Encryption by Rogaway, where he presents two different notions of indistinguishability, which he calls ind$ and ind, respectively. Here's the definitions of these to notions:

First, let $A^g$ be an algorithm with access to an oracle $g$, and let $\Pi = (\mathcal{E},\mathcal{D})$ be an encryption scheme with key space $\mathrm{Key}$.

Ind\$ is then defined as follows:
$$ \mathbf{Adv}_{\Pi}^{\mathrm{ind$}} = \mathrm{Pr}[K \xleftarrow{$} \mathrm{Key} : A ^{\mathcal{E}_K(\cdot)} \Rightarrow 1] - \mathrm{Pr}[A ^{\mathcal{$}(\cdot)} \Rightarrow 1],$$

where $ \$(\cdot)$ is a random oracle, returning random bits equal to the block size of $\mathcal{E}$. In other words: ind$ asks an adversary to distinguish between messages encrypted by the real encryption scheme and random bits.

Ind is defined as:
$$ \mathbf{Adv}_{\Pi}^{\mathrm{ind}} = \mathrm{Pr}[K \xleftarrow{$} \mathrm{Key} : A ^{\mathcal{E}_K(\cdot)} \Rightarrow 1] - \mathrm{Pr}[K \xleftarrow{$} \mathrm{Key} : A ^{\mathcal{E}_K(0^{|\cdot|})} \Rightarrow 1].$$

That is, ind asks an adversary, when quarrying the input message $M$ to the oracles, to distinguish between the real encryption of $M$, and the encryption of $0^{|M|}$.

He then claims that

  "It is easy to verify that the ind$-notion of security implies the ind-notion, and by a tight reduction".

My question:

Intuitively, the implication seems easy enough:
If $\Pi$ is ind\$-secure, then encryption of $0^{|M|}$ will be indistinguishable from random, so we just get the "ind\$-game". However, how would you go about showing the tightness of the reduction? Usually I'm used to doing this by a reduction like so: assume you have an ind-adversary that breaks the ind-security, how can you turn this into an (effective) adversary against the ind\$-security of $\Pi$? But I don't really see how an adversary against ind can be turned into an (effective) adversary against ind\$.


texts: Is email an example of public-key cryptography?

texts: It seems like email is at least analogous to public-key cryptography, the public portion of the key being your email address, and the private portion of the key being the password to the email account. Is this merely an analogy, or is email in fact an instance of public-key cryptography?


texts:
Is there any simple probabilistic MAC $\Pi=(\operatorname{Gen},\operatorname{Tag},\operatorname{Vrfy})$ with UF-CMA security but without UF-CMVA security?

How can an attacker efficiently use the $\operatorname{Vrfy}(\cdot,\cdot)$ algorithm to break the MAC scheme?

Paula


texts: What cryptographic paradigm is appropriate for this use case?

texts:
This is a very newbie question...

I have to quickly implement a solution for our application that works like this... We have a binary executable that is given a configuration file. I need to encrypt the configuration file such that a non-trusted user can be given the binary and the encrypted config file (and maybe a public key or something) and he should be able to run the binary with the encrypted file. We're not concerned with the user disassembling or reverse-engineering the binary itself for now.

Could you suggest a cryptography paradigm &/or c++ crypto library that will allow me to do the above? I was thinking of encrypting the config files with a public key, the private key of which would be embedded in the executable but I'm not sure if that is a secure way of doing things.

Thanks


texts:
AES-128 requires 10 rounds ( AES Description, Wikipedia )

However Bruce Schneier has recommended AES-128 use 16 rounds ( Schneier on Security: New Attack on AES )

Could that be implemented as two full encryptions of AES-128? That is:

AES_128_ENCRYPT(key, data, mode); // 10 rounds of normal AES 128
AES_128(key, AES_128(key, data, mode), mode); // would this be 20 rounds of AES?

Would this need to be with two separate keys like in Triple DES ( Triple DES, wikipedia )?


texts: Does blinding work against side channel on RSA?

texts:
In the so called "blinding" technique for RSA, prior to decryption, the ciphertext is multiplied by random $r$ raised to the power of $e$; e.g., $C$ is replaced with $C\cdot r^e$; and then after decryption, the result $(C\cdot r^e)^d\equiv C^d\cdot r\pmod n$ is divided by the random $r\pmod n$.

Is that efficient against timing or power attack? I saw that technique in some articles, nevertheless I though that the power / timing attacks are aiming at discovering the bits of the exponent $d$, and if so, the value of the cipher text, whether its $C$ or $C\cdot r^e$ does not really matter, does it?


texts: Understanding WPA2 authentication in details

texts:
As far as I know, WPA2 authentication consists of a 4-way handshake. The first message is from the AP, containing the ANounce, a random number generated by the AP, The second message is from the client, containing the SNounce concatenated with a MIC of the ANounce, the third is from the AP containing the GTK concatenated with some MIC and the last is simply an ack.

In the case of PSK, PMK = PBKDF2(HMAC−SHA1, PSK, SSID, 4096, 256). So supposing I have psk = "personal-key" and ssid = "net-name", the function would be  PBKDF2(HMAC−SHA1, "personal-key", "net-name", 4096, 256)

   4 iterations of 4096 hmacsha1 xor chains concatenated to form 256b

I do not understand though how the PTK is generated. According to this question, PTK is generated from HMAC-SHA1 of length 512 of PMK as key and (ANounce || SNounce || AP MAC || Client MAC) as text, but how can it generate data of 512b length if SHA1 only outputs 160b? Isn't HMAC-SHA1 equal to SHA1(key XOR opad || SHA1(key XOR ipad || text))?

My second problem is how MICs are computed. I know that they use some message and a key. In WPA2 case, the key is the KCK, the first 128b of PTK, but what is the algorithim used in the computation?

And the third problem is how GTK generated and what is the message inside de MIC that is sent on the third message.


texts: Attacking RSA signature verification that ignores padding

texts:
I am looking at a RSA signature verification that is quite obviously flawed and am wondering if there's a way to exploit that flaw in practice.

Signature is generated using RSA with PKCS 1.5 padding, i.e. $S = M^d \mod N$, where $M$ is a padded message: $M = 00 \| 01 \| FFF ... F\|00\|m$ and $m$ is the raw message being signed, which is always a 64-char pseudo-random ASCII hex string (it's a hash value).

When verifying signature, however, there is no check for padding. Verification is done by computing $M = S^e \mod N$, converting M to a byte array and then simply looking for a substring $m$ in $M$.

Modulus $N$ is 2048 bits and public exponent $e = 65537$.

Attacker can obtain a limited number of valid signatures (of a padded message) but there's no direct control over what $m$ will get signed (it's a time-base hash value).

Do you see any way to forge signature of attacker-chosen $m$ so that it'd be accepted by this flawed verification procedure?

Thanks!


texts: Several questions about Paillier cryptosystem

texts:
I have several questions concerning the original Paillier cryptosystem as described in Paillier, Pascal (1999).
"Public-Key Cryptosystems Based on Composite Degree Residuosity Classes".
EUROCRYPT. Springer. pp. 223-238. http://www.springerlink.com/content/kwjvf0k8fqyy2h3d/?MUD=MP

Notation:
$p$ - unencrypted message, plaintext
$c$ - encrypted message, ciphertext
$r$ - random factor
$k_{pub}$ - public key
$k_{priv}$ - private key

I have a Paillier-encrypted ciphertext ($p$) that is no straight encryption but the result of an arbitrary number of various true or mixed homomorphic operations or re-randomizations.

Assuming I know $p$ and the corresponding private key $k_{priv}$.
Am I able to compute the random factor $r$ from this so that a reencryption of $p$ with $r$ would be identical to $c$, i.e. $E(p, k_{pub}, r) = c$ ?
if positive answer to 1, how do I compute $r$?
if positive answer to 1, is it possible that there exists another $r'$ so that a different plaintext $p'$ encrypted with $r'$ would also result in $c$, i.e.
$Enc(p, k_{pub}, r) = c = E(p', k_{pub}, r')$, $p \neq p'$, $r \neq r'$ ?
if positive answer to 3, could this $r'$ be efficiently computed, i.e. could the owner of $k_{priv}$ be trusted if he would provide $r$ to a given $c$ as (Zero knowledge) proof of correct decryption?


texts: Help me about Advanced Encryption Standard (AES)

texts:
Suppose $E_k$$(a, b, c)$ is encryption of values $a, b$ and $c$ with key $k$ through encryption algorithm AES (AES-128) and each $a, b$ and $c$ are 300 bits integer values.

Also Suppose this algorithm in my question situation work in CBC mode.

If $V_1= E_k(a, b, c)$ and $V_2= E_k(c, a, b)$, my questions is:  are the two values $V_1$ and $V_2$ equal or not?


texts: Dangers of using AES CTR without authentication - can you recover the plain text?

texts:
I understand that if a system uses AES in CTR mode (or other modes) without authentication that an attacker can flip bits to try to get the system to do something it wasn't intended to do (or wasn't intended for the attacker specifically to do).

What is not so clear is, does the lack of authentication mean that the attacker can somehow recover the plain text? I'm specifically thinking of a case where firmware is encrypted with AES-CTR but has no authentication. The attacker can take publicly available encrypted firmware intended for the device, alter it, and send it to the device. Is the attacker somehow able to decrypt the firmware by doing this?


texts: How does the zuc algorithm complete the synchronization?

texts:
I have already read the following documents:

Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 & 128-EIA3. Document 1: 128-EEA3 and 128-EIA3 Specification

Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 & 128-EIA3. Document 2: ZUC Specification

Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 & 128-EIA3. Document 3: Implementor’s Test Data

Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 & 128-EIA3. Document 4: Design and Evaluation Report

and I know the ZUC algorithm use the iv to synchronize for the frame, but I still don't understand how iv synchronization is implemented in real applications. Is the method for implementing synchronization similar to that in the WEP algorithm as show below?

In the WEP algorithm the output of the process is a message containing the IV and ciphertext, is the output of the ZUC algorithm also a concatenation of IV and ciphertext ( IV || ciphertext )?


texts: Why Might XOR's Lead to Hash Functions Lacking 2nd Pre-image Resistance?

texts:
My hash function is as follows:

Cut the string in half (assume even length of 2m)
XOR's the two halves together
Take the result of the XOR and pass it to a function (a one-to-one and "onto" function) that simply does:

$f: \{0, 1\}^m \rightarrow \{0, 1\}^m$

I'm being asked to prove why this hashing strategy is not second pre-image resistant (though it is pre-image resistant) but I'm getting hung up.

I know a 2nd pre-image means finding $x' \neq x$ s.t. $h(x') = h(x).$

I also know that different strings can result in the same XOR:

$1010 \oplus 1111 = 0101$ and so does $0000 \oplus 0101.$

I think I'm just lacking complete understanding of the concept.  Thank you in advance for your help.


texts:
I'm sure there's a proper name for this, but I have no idea what it is.  When my family fled Europe, one of the remaining items are a letter and a key from a bank.  The general idea was that whomever has the letter and the key, was allow to open a box that then had ... something that is lost to history.  One family member went with the letter, and the other with the key.  The interesting thing for me about this system is that it does not matter who has either the letter or the key, but the letter is signed by a specific banker of record.
In modern cryptography, is there a similar system where there is two party authentication system for information where one party has a signed "letter", and the other party has an unsigned "key".


texts: is MAC double-hashing enough to prevent length extension attacks?

texts:
I know that
$$mac=\operatorname{SHA1}(secret\mathbin\|message)$$
is prone to length extension attacks, but what about:
$$mac=\operatorname{SHA1}(\operatorname{SHA1}(secret\mathbin\|message))?$$
In order for someone to do a length extension attack of that, won't they either have to bruteforce the secret or bruteforce the initial $\operatorname{SHA1}$ itself? (the first of which should be unfeasible with a good secret, and the second of which should be just as expensive, or maybe even more expensive, than just bruteforcing the new hash itself?)
(edit: originally had a second question about HMAC here as well, but I think I'll take that in a separate thread, sorry about the confusion in the comments)


texts: mapping a 256 bit random number to a 3 bit number

texts:
I am making a 2 player dice game that runs for n rounds. To create random dice roles im using a concept a understood from randao.

each user generates n sha3 hashes recursively of a random seed : e.g.

H[0] = sha3(sha3(seed))
H[1] = sha3(sha3(H[0]))
...
H[n] = sha3(sha3(H[n-1]))

During the nth round, we xor the H[nth] value of each user to be used as a random value for that round:random_result

My Question: What is the best strategy to map the 256 bit random_result to a 6 sided dice without completely botching the entropy?


texts: How to submit a new method of encryption?

texts:
I came up with a truly new method of applying modulo-2-addition encryption function in stream ciphers which is inspired by a mechanism used to prove a mathematical theorem. How can I determine whether my method is cryptographically correct and considerable? If so, how can I officially submit or formally register it in my name? And finally, can I make money thorough this method just by selling it to an encryption company or organization?

EDIT

Hi everyone, thanks for all answers and comments. It seems quite heartening.
I know that modulo 2 operation is equivalent to XOR (exclusive OR operation in Boolean Algebra) gate in electronics. As you all know, the overriding issue concerning the security of stream ciphers is how to generate truly random key streams, and actually my newly-inspired method mainly deals with this issue. I mean this method can produce or generate random key streams in an entirely new way for either stream or block ciphers. I finally decided to publish my workings on this topic very soon for gaining cryptographic credits rather than just making money.


texts: AES-128 Decryption in Objective-C just slightly off

texts:
I have been asked to integrate a home-grown CRM system with a 3rd-party data service provider (DSP).  The DSP has encrypted the information they are providing.  I only have their decryption instructions, which are as follows (verbatim):

Encryption Type: AES128
Mode: CBC
Padding: PKCS5 (.net usesPKCS7)
Password: jayjay
Encryption reference:(link below)

decryption example as provided by the DSP

The DSP instructions also contain some sample data, namely:

Sample Encrypted data:

h6KlotyqYvipjQHICwJK25mqY+2GC6qc/qf5fCBoGYaxe2zQad/j6Dxo6H259PretcjkUcBsgMl+vFkYPXGwH vbZMqMPCIznBrdZeSWP+Hie7YdLRYp9V5/JKLTIZZlZAG7Vii8DepV5KXjbat4qGxNTVRAvDQ8tT9xZbzEbzY 7Sb9q/f9TE/yardrrgDntw9WywTDbU4Yfg3BEC0jIKFg==

Sample Expected Decrypted data:

123456^CustIDLookup^John^Doe^Placeholder Name^ATS^217 General Patton Ave.^Suite 208^Mandeville^LA^70471^United States^985-809-0600^postmaster@atsleads.com

So, my mission, should I choose to accept it, is to arrive at the decrypted example.  This is for use within a native iOS app, so I need to code the decryption in Objective-C.

So far, my results for the decrypted data NSString look like this:

__NSCFString *  @"(\0\x1d\r\x040D^CustIDLookup^First Name^Last Name^Title^Company^Address 1^Address 2^City^State^Zip^Country^Phone^Email"   0x00000001780ee700

i.e. I am getting this result string:

\0\x1d\r\x040D^CustIDLookup^First Name^Last Name^Title^Company^Address 1^Address 2^City^State^Zip^Country^Phone^Email

I have shown my code below.  I can get very close to the expected decryption, but I can't match it exactly - the first 5 chars are wrong.

Can anyone shed any light on this issue, and perhaps steer me in a direction that would allow my decryption code to decipher the data correctly?  I'm no expert on encryption, but it seems strange to me that I'm very close but am not yet enjoying my cigar.  In my reading so far I have seen comments stating that AES128 and PKCS5 don't make sense together, but I don't if this has any bearing on things.

I have coded an NSMutableData category (extension) as follows:

@implementation NSMutableData (AES)

- (NSMutableData*)DecryptAES: (NSString*)key
{
    int blockSize = 16; // Actually kCCKeySizeAES128, but hard-coded for experimentation
    char  keyPtr[blockSize];
    bzero( keyPtr, sizeof(keyPtr) );
    bool rc1 = [key getCString:keyPtr maxLength:sizeof(keyPtr) encoding:NSUTF8StringEncoding];
    if (rc1==NO){
        NSLog(@"getCString failed");
    }

    size_t numBytesEncrypted = 0;
    NSUInteger dataLength = [self length];
    size_t bufferSize = dataLength + blockSize;
    void *buffer_decrypt = malloc(bufferSize);
    NSMutableData *output_decrypt = [[NSMutableData alloc] init];
    char ivBytes[8] = {0,0,0,0,0,0,0,kCCModeCBC};
    //char ivBytes[8] = {0,0,0,0,0,0,0,0}; // same results with this line
    int ivLength = sizeof(ivBytes);
    NSData* initialisationVector = [[NSData alloc] initWithBytes:ivBytes length:ivLength];

    //CCCryptorStatus result = CCCrypt(operation, algo, optarg, key, keylength, iv, datain, datainlength, dataout, dataoutavailable, dataoutmoved)
    CCCryptorStatus result = CCCrypt(kCCDecrypt , kCCAlgorithmAES, kCCOptionPKCS7Padding , keyPtr, blockSize, initialisationVector.bytes, [self mutableBytes], [self length], buffer_decrypt, bufferSize, &numBytesEncrypted);

    if (result!=kCCSuccess){
        NSLog(@"CCCrypt did not work");
    }

    output_decrypt = [NSMutableData dataWithBytesNoCopy:buffer_decrypt length:numBytesEncrypted];

    if(result == kCCSuccess) {
        return output_decrypt;
    }
    return NULL;

}

@end

I am then calling this category as follows:

NSMutableData* originalStringAsData = [[NSMutableData alloc] initWithBase64EncodedString:self.originalString options:nil];

NSMutableData* decryptedData  = [originalStringAsData DecryptAES:@"jayjay"];

NSString* decryptedString1 = [[NSString alloc] initWithData:decryptedData encoding:NSUTF8StringEncoding];

Any help would be hugely appreciated.


texts: choices for k in binary finite field modular reduction algorithm

texts:
In the Guide to Elliptic Curve Cryptography there's this algorithm:

My question is...  what is $k$? Is it just some random value we pick? If so are some numbers better than others?


texts:
I read somewhere MD5 is broken in terms of collision, but I am wondering if it is broken in terms of pre-image resistance?

Given a hash of Md5, is it possible to find the original message of it? If so, what would be the complexity and time to crack it?


texts: Key generation for DH key exchange - benefits of using KMI

texts:
Context
We need to generate a key pair in order to perform DH key exchange with the other party.
Some suggest to use a KMI solution (think: AWS KMS or like) in order to generate the key pair.
Questions

What would be the benefits of using a separate KMI solution to generate key pair for DH key exchange?
Are there any benefits over on-the-fly generation using a proper library (in this context)?
Would there be any generic reason to keep key pair used solely for key exchange, after the key exchange has been completed?


texts: Security when using same salt for different passwords, compared to using different salts?

texts:
I have this question I am struggling about:

For example, someone suggested improving UNIX authentication by defining 3 different passwords for a user that are stored in the shadow file. All three passwords are stored with the same salt value.

When a user wants to authenticate to some system, he must provide in the $i$ attempt to login, the $i$ mod 3  password. For example, in the first attempt he will provide the first password, in the second and fifth attempt he will provide the second password. Is such alteration to UNIX system increases security or not? And what happens when all passwords are stored with different salt value?


texts: find master key given all but last decryption round keys

texts:
I have all but the last round key in AES-256 CBC decryption, and would like to build the master key, but I am unsure how to go about it.
I have read I can convert decryption roundkeys to encryption roundkeys via forward MixColumns. Then perhaps xor key n-3, n-2 to get n-1 (one i need). Does S-box substitution come into play here?
Or is there a keyschedule generator based on decryption roundkeys rather than encryption... thank you for the help.


texts: what are the most common stream ciphers algorithms?

texts:
say that we have an unknown stream cipher which output bytes and which have more than 10 years of existence. What can be the most probable algorithms if we consider the most 'populars' stream cipher algorithms?

In order to find the most 'popular' stream ciphers, where can I find some statistics about the most implemented stream ciphers since 2000?


texts:
Consider the following experiment:

  Let there be a machine which runs (ie. continually clocks) an LFSR of size (ie. number of bits) $b$, having a button that, when pressed, extracts the next $t$ bits from the LFSR, prints them onto a paper ticket, deposits the ticket into a sealed, opaque urn, and complements every bit in the LFSR (ignore, for the sake of argument, the case where the LFSR gets reset to all zeroes); the machine continues to run normally afterwards.

  Now place this machine in a room, completely isolated from the outside, and have a number (say $n$) of players form a line and, one by one, step into the room and press the button. After all $n$ of them are finished, retrieve the sealed urn.

  The LFSR's feedback polynomial, initial state and clocking frequency are public parameters, as are the numbers $b$ and $t$.

Now there's an attacker whose purpose is to match at least one ticket in the urn to one of the players. The attacker has access to all the public parameters, knows the order in which the players are lined up, can measure the time each one enters the room (but cannot, obviously, know exactly when a player pushes a button, since that happens inside the isolated room), and may collude with a fraction q of the players in order to achieve its goal.

The questions, then, are:

Which parameters (ie. $b$, $t$, $q$, clocking frequency is a little trickier) can ensure the attacker has no more chance of succeeding than he would by guessing?
Would replacing the LFSR by an ASG be any better? any worse?

A note on clocking frequency: for technical reasons, the clocking frequency is forced to be relatively low, say no more than 2kHz (ie. one clock pulse every one two-thousandth of a second).

A note on collusion and what the players can and can't do: the players can be assumed to have at their disposal a timing device of their choosing, with the accuracy they see fit (if this proves to be too powerful an advantage, an analysis with restrictions is greatly appreciated!); a player does not see the number they get (they actually don't get it per se, since the number goes into the urn).

The rationale behind all this is that we're trying to generate true-ish random numbers from an LFSR: the random variable to harness is the times at which the button is pressed, the LFSR is there just to provide for confusion of the generated values; if one where to use the number of seconds since the experiment's beginning, the attacker could easily match the tickets to the players; if one where to use the LFSR without complementing, the attacker could compare them according to the order in which the LFSR (all of whose parameters are public) generates them; I believe (with absolutely no basis!) that complementing after each extraction could do the trick.

English is not my mother language, I'm sorry if I haven't made myself clear enough, please do ask for clarifications if needed.

This is not homework, tough it may look like it :)

EDIT: It has been brought up more than once in the answers that knowing so much and being able to do so much, gives the attacker too much power, so i decided to make the LFSR's initial state secret. Now the last paragraph in the explanation above should read:

  The LFSR's feedback polynomial and clocking frequency are public parameters, as are the numbers $b$ and $t$. The LFSR's initial state is secret, and unknown to the attacker.


texts: How can I implement the "Multiplication Modulo" and "Addition Modulo" operations in IDEA?

texts:
I am currently working on IDEA (International Data Encryption Algorithm), and I don't know how to perform Multiplication Modulo and Addition Modulo.
This is how IDEA operates:

IDEA operates on 64-bit blocks using a 128-bit key, and consists of
a series of eight identical transformations (a round, see the illustration)
and an output transformation (the half-round). The processes for encryption
and decryption are similar. IDEA derives much of its security by interleaving
operations from different groups — modular addition and multiplication, and
bitwise eXclusive OR (XOR) — which are algebraically "incompatible" in
some sense.

Bitwise eXclusive OR (denoted with a circled plus ⊕).

Addition modulo $2^{16}$ (denoted with a boxed plus ⊞).

Multiplication modulo $2^{16}+1$, where the all-zero word (0x0000) is
interpreted as $2^{16}$ (denoted by a circled dot ⊙).


texts: Distinguishing joint probability distributions

texts:
Assume that we have a probability distribution $P(X,Y)$ for the joint probability of random variables $X$ and $Y$. Let $P(Y, Z)$ be analogous distribution for $Z$ and $Y$. Based on these we can define a joint probability distribution of $P(X,Y,Z)$.

Let, $P'(X,Y)$ and $P'(Y,Z)$ be analogously probability distributions where it is known that $P'(X,Y)$ is computationally indistinguishable from $P(X,Y)$ and $P(Y, Z)$ is computationally indistinguishable from $P'(Y,Z)$. Based on these we define a joint probability distribution $P'(X,Y,Z)$.

Do the indistinguishability conditions on the initial distributions imply that $P(X,Y,Z)$ is computationally indistinguishable from $P'(X,Y,Z)$?


texts: Order of an elliptic curve defined over a prime field

texts:
I found the following algorithm to find the generator of an elliptic curve:

Find the order of the curve - N.
Choose any random point on the curve - P.
Find the order of that point - n.
Calculate co-factor - h=N/n.
Find the generator - G=h x P.

Here, let us assume the order of the generator G is n_g. It accounts to say n_g x G=O.
On replacing G from step 5, we can observe that n_g x (h x P)=O.
From this we see that n_g x h >= n_g which makes P a stronger generator with an higher order.

How should I counter this argument?


texts:
For a long time I've been under the impression that all of encryption uses xor at its basic level.

Is this true? What other method could be used to encrypt plaintext with a key? Asymmetrically, as while as symmetrically?

There are hundreds of ciphers, aes, blowfish, ect. They are all different, but do they all rely on xor?

It is a dumb question, however it was never asked (at least on google).


texts: What will happen if I use RSA encryption for plaintext larger than RSA bit size?

texts:
I have often read that using RSA for encrypting bigger size plaintext is not good solution.

What I understand is that using RSA encrytion is best for small plaintext and most effective if it is smaller than 'bit size' of RSA. For instance, if I use RSA with a 2048 bit size then the plaintext that I can encrypt must be smaller than 256 bytes.

Is this true? What happens if the plaintext is bigger than 256 bytes? Why is there a problem with larger plaintext when performing RSA encryption?


texts: Are My Answers for This RSA Question Correct?

texts:
I am very new to cryptography and so I am looking for feedback on this question on RSA. Please let me know if I have made any mistakes, Thank you!

(a).

RSA Algorithm:

-choose two primes p,q

-compute n = p * q

-compute phi = (p-1)*(q-1)

-choose e such that 1 < e < phi and gcd(e,phi) = 1 where gcd is greatest common divisor

-e is the public key

-calculate d such that d = phi * k + 1 / e for some integer k

-d is private key

-cipher text c for plain text

-m is computed as: c = m^e mod n

-plain text m for cipher text c is computed as m = c^d mod n

  p = 83 ; q = 89 then,

  n = 7387

  phi = 7216

  e = 193

  d = 4811

  c = 4336 => 2^193 mod 7387

b)

No, 11 is not a valid private key

Cipher text using 11 as private key is "2048".

Where as decrypting using d = 4811 is 2404 which is not equal to original 2

c)

private key "d = 4811" for public key 25


texts: How does the verification process associated with this signature scheme work?

texts:
My cryptology professor asked us to show that while the following signature scheme is conceptually valid, that it is inherently insecure, however, I am not sure how to demonstrate that the associated verification process produces an equality if the signature is valid.

The protocol works as follows given:

A publicly shared prime $p$;
A primitive root of $p$, $a|a<q$
A private key: $x|x<q$; and
A public key: $y=a^x\bmod{q}$
A cryptographic hash function $H=\texttt{SHA1}$

A signature $s$ can be generated for $m$ as follows: first, compute $h = H(m)$; if $\texttt{gcd}(h, q-1) \neq 1$ append $h$ to $m$ and calculate a new hash, and continue the process until $h$ and $q-1$ are relatively prime.

Then, calculate $z|z\cdot h\equiv x\bmod{q-1}$ and return the signature $s = a^{z}$.

In order to verify $s$, a user verifies that $Y=(a^z)^{h}=a^{x}\bmod{q}$.

For example, in order to sign a message $m$, where:

$q=6043$
$a=5$
$x=1098$
$y=485$
$h\leftarrow H(m)=612515367434372930600221767499032307523881412051$
$z\leftarrow z\cdot h\equiv x\bmod{q-1}=8513$
$s\leftarrow a^{z} = 5845$

Given the signature $s$, a user can verify that the signature is correct by verifying that $y=(a^{z})^{h}=a^{x}\bmod{q}$, however, I am not sure how to evaluate

$$(a^{z})^{h}= a^{x}\bmod{q}$$

since $h$ is (relatively) large. I (think) that I need to evaluate the following expression, however, I am not sure if its computationally feasible since:

$$(a^{z})^{h}\rightarrow s^{h}\rightarrow 5845^{612515367434372930600221767499032307523881412051}$$

Meaning that in order to verify the signature, I would have to perform the following calculation:

$$(5^{8513})^{612515367434372930600221767499032307523881412051} = 5^{1098}\bmod{6043}$$

Normally, I would use fast modular exponentiation here, but $h$ is absolutely enormous. For a while, I thought that maybe I misunderstood the protocol and $h$ should be reduced modulo $q$, but, again, maybe I just have an embarrassingly flawed understanding of the protocol?

How do you think I should verify the signature?


texts: For calculating the index of coincidence for each sequence

texts:
I was learning about the finding the key length reading the following web site...
http://practicalcryptography.com/cryptanalysis/stochastic-searching/cryptanalysis-vigenere-cipher/

and I really don't understand some part of the example shown in the web.
They assume the key length is 2 and extract the two sequence 1,3,5,7.... and 2,4,6,8...
and from these two sequences they calculate the I.C.

I wasn't sure how they calculate the I.C. for each sequence. Do they find the frequency count of each letter from a to z, and calculate the I.C using the following formula?


texts: Can you break an RSA modulus if you know $k \cdot \phi(n)$ where $k$ is a large prime?

texts:
Given some RSA modulus $n$, can you factor $n$ if you are given $k \cdot \phi(n)$ where $k$ is also a large prime?
(Of course, you could factor $n$ if you were given $\phi(n)$ as discussed here, but that approach does not work when you cannot factor $k \cdot \phi(n)$, right? )


texts: Many designer claimed that their cryptography scheme has 80-bit security. So how to calculate the time of attcking this 80-bit security cryptography scheme, such as 80-bit security RSA using a kind of CPU?


texts:
I'm following these three articles:

Kleptography: Using Cryptography Against Cryptography,
Kleptographic Attack on Elliptic Curve Based
Cryptographic Protocols and
Elliptic Curve Kleptography .

In the first article, a kleptographic attack based on a DLP cryptosystem is described. In particular, we can read (pg 67) that $$ z \equiv g^{c_1-Wt}Y^{-ac_1-b} \bmod p$$
where $c_1$ is the private key of Alice (the sender); $Y \equiv g^X \bmod p$ is the public key of Eve (eavesdropper); $g$ is a generator of $\mathbb{Z}_p$ and $a,b,W$ are three integers used for precaution. Indeed, even if a user is able to invert the hash function $H$, then it is still impossible to detect if the device has been contaminated with a SETUP mechanism (pg 68-69).
In the second article, an analogous of this attack is presented in the context of elliptic curves. Here (pg 139907, algorithm 5)
$$z = (c_1-Wt)P+(-ac_1-b)Y $$
where $P$ is the base point of a strong elliptic curve $E$ over $\mathbb{F}_q$. Here, there is not a well know theory such as quadratic-residues and their distributions $\mathbb{Z}_p$. Indeed, in 3 we can read: "This kind of
probabilistic detection by the user is very difficult in
elliptic curve cryptosystems compared to discrete log
systems where quadratic residuosity can be used to test a possible relation between the attacker’s public key and $z$".
Then, my first question is:  could the SETUP attack applied to EC be simplified? For example, deleting some extra number $a$ or $b$?
However, in the third article, $z$ is a little more complicated than what we saw in the first two papers.
\begin{equation}
z = (ac_1 + h \cdot j)P + (bc_1+e \cdot u)Y
\end{equation}
where $a,h,e,b$ are fixed integers, and $j,u \in \{0,1 \}$ are uniformly and independently chosen at random.
Therefore, my second question rises. What is the best implementation of the SETUP attack in ECDH? The second article or the third one?
Here, the "best implementation" means that comparing the algorithms in 2 and 3, we want to find them faster and easier algorithm which leads to the same result and which is the safest. Indeed, the security is based on the randomness of $z$, and in 1 is explained why. Following this first direction, one can think that the algorithm in 2 is secured as the first one 1. However, on elliptic curves, strange things may happen, and in order to obtain the randomness of $z$, we should use the third algorithm 3. I don't think this is the case, i.e. I think 2 it's enough to reach the wanted level of security, without using extra integers $a,u$ as in 3.


texts: What kind of operations are involved in NTRU?

texts:
I've read that lattice based algorithms involve matrix-vector products. Is this the case of the NTRU algorithm?

When I've read the details of the NTRU algorithm, I've seen products of polynoms. Where are the matrix-vector products?


texts: How do pairings behave on G2/twist points off the prime order subgroup?

texts:
$\newcommand{\F}{\mathbb{F}}$
Consider the ate pairing defined on a curve $G_1 = E(\F_q)$ and $G_2 = E'(\F_{q^r})$ where $E'$ is a twist of $E$ with the twisting isomorphism defined over $\F_{q^r}$. Say $G_T \leq \F_{q^k}^\times$ and the pairing is $e : G_1 \times G_2 \to G_T$.

Suppose $p = |G_1|$ is prime. My question is the following: how does $e$ behave on points in $G_2$ which are off the distinguished order $p$ subgroup?

Here is a guess: Let $G_1 = \langle g \rangle$ and $G_2 =\langle h \rangle \times K$ where $h$ has order $p$. My guess would be that for $k \in K$ we have $e(g^a, h^b k) = e(g^a, h^b)$. Is it correct that off subgroup components are "killed" when paired with a $G_1$ element?


texts: Concerns about use of MAC in my specification

texts:
Here is the pseudocode for a routine I am designing:

encrypt(password, string):
  nonce1 := generate_random_nonce()
  nonce2 := generate_random_nonce()
  key := derive_key(nonce1, password)
  encrypted := cipher(nonce2, key, string)
  return (nonce1 || nonce2 || encrypted || mac(key, encrypted))

I realized that an attacker with the encrypted text might be able to brute force the key, since a mac is not slow to compute (like key derivation).

I thought about using a third nonce for the mac key instead of the ciphertext key, but the mac key should be secret so this isn't an option.

  How should I correctly use a MAC to authenticate the ciphertext (and thus plaintext) in this situation?


texts:
Consider the following very simple cipher, where, to send length $n$ bit-strings, we randomly correspond the numbers $1, 2, 3, ..., N$ with $n$ bits, so the key is the correspondence between each integer and the bit value it maps to.  Then, to share a bit-string, Alice will send Bob a permutation of the integers $1, 2, ..., N$.

Obviously this cipher is not good for use, but I am wondering the following: am I correct in assuming that so long as the adversary does not obtain any plaintext/ciphertext pairs, Alice and Bob can share multiple messages with the same key, as each new message, to the adversary, is just a permutation of the numbers $1, 2, ..., N$?


texts: High-latency anonymous communication minimum delay?

texts:
High-latency anonymous communication (e.g. Mixmaster and Mixminion) delay messages for a long time using mixers to anonymous communications. I understand that it has applications for email and p2p but not for good for responsive applications such as web browsing and instant messaging.

I've gone through the papers for them but couldn't find the relevant information.

How long exactly are the delays? minutes, hours, days?
Can these be set? is there a minimum bound for it to be defined as safe? I asked this because I'm wondering if it could be somehow applied to web browsing


texts: OpenSSL & TLS1.2 with aes-cbc and initialization vector

texts:
I'm trying to manually decrypt DTLS traffic using OpenSSL and TLS 1.2. The cipher suite im using is AES256-SHA256 as listed here. Im able to decrypt the packets with the key that the server and the client negotiate during the handshake without issues, but what i don't understand is that i can set the initialization vector to any value or even null and still i can decrypt the packets.

Here is a code snippet from the program that receives the packet:

EVP_CIPHER_CTX *ctc = EVP_CIPHER_CTX_new();
EVP_DecryptInit_ex(ctx, EVP_aes_256_cbc(), NULL, key, (const unsigned char)"not a real iv");
...
EVP_DecryptUpdate(ctx, (unsigned char*)payload, &len, (unsigned char*)payload, len);
EVP_DecryptFinal_ex(ctx, (unsigned char*)payload + len, &len);

And that decrypts the data fine with the bogus IV.

So apparently either the encryption / decryption is not done in CBC mode.
Or does OpenSSL derive the IV by the decryption key somehow from the packet ?

What i am missing or/and not understanding here ? The DTLS rfc did not talk about this either.


texts:
I'm currently reversing an AES implementation for disk encryption. The odd thing I'm stumbled about is a key schedule where the encryption round keys are not the same as the decryption round keys (in "reversed order"). Altough the first 4 bytes, i.e. the first round key for the encryption, and the last 4 bytes, i.e. the last round key for the decryption, are the same. The other round keys are totally different.

Is there an optimization that requires the round keys to be computed in a different manner?


texts: Determine if a public key point y is negative or positive, odd or even?

texts:
Take an elliptic curve cryptography public key (x, y) and its additive inverse (x, -y). How do you identify which is the positive point and which is the negative point?

Examples:

Private key 1 -> (x, y)

x = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798L

y = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8L

-y = 0xb7c52588d95c3b9aa25b0403f1eef75702e84bb7597aabe663b82f6f04ef2777L

Private key 2 -> (x, y)

x = 0xc6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5L

y = 0x1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52aL

-y = 0xe51e970159c23cc65c3a7be6b99315110809cd9acd992f1edc9bce55af301705L

Private key 3 -> (x, y)

x = 0xf9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9L

y = 0x388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672L

-y = 0xc77084f09cd217ebf01cc819d5c80ca99aff5666cb3ddce4934602897b4715bdL

Also, how can you identify which public key is odd and which is even?

For example: private key 1 x,y is odd, private key 2 x,y is even (based with pub key).


texts: Appropriate length of the challenge string for challenge-response authentication?

texts:
How to select the necessary length of the challenge string for challenge-response authentication to claim that there is no threat of the shared secret exposure?

I can think of the following:

Possible number of given responses in some time considered as "reasonable".
Algorithm used for calculating the response.

Are there other factors?

How to calculate the "safe" challenge size if, for example, my system can respond 10^12 times during the lifetime of the key, and the response is calculated with HMAC-MD5(key || challenge)?


texts:
I would love to get help figuring out how to prove the following theorem:
If there is an Encryption scheme for a single bit CPA secure then an Encryption scheme can be created along with a variable of bits which is also CPA secure.
I built a reduction, $Adversary$ for the single-bit scheme ($A$) that simulating the $Adversary$ of the variable of bits Encryption scheme ($A'$). $Adversary$ $A$ answers $A'$ Encryption queries so that he encrypts bit by bit and passes it back to him. When $A'$ outputs 2 messages $m_0$,$m_1$ from the same length to the challenger I am getting stuck.
I would greatly appreciate any help.


texts: Calculating Multiplicative Inverse for Rijndael S-box using EEA

texts:
I am currently learning, and I'm stuck on something that I thought is very simple. On many academic sources they suggest using Extended Euclidean Algorithm to calculate the multiplicative inverse for calculation of the S-Box, but I could not find a proper explanation how to do that. Every practical approach calculates log+antilog and uses that. But I'm stubborn and I want to use EEA!

I got my algorithm from here: https://www.youtube.com/watch?v=fq6SXByItUI

For my calculations I used values 0xCA and 0x53.
When I multiply them using the Rijndael finite-field multiplication I get 1. So I know that they are each others inverses. But when I put them inside EEA I get a different value :(

0x53 = 83
0xCA = 202
0x11B = 283 (Rijndael Plynomial)

283 = 3 * 83 + 43   |   34 = (1) * 283 + (-3) * 83
 83 = 2 * 43 + 15   |   15 = (-2) * 283 + (7) * 83
 34 = 2 * 15 + 4    |   4 = (5) * 283 + (-17) * 83
 15 = 3 * 4 + 3     |   3 = (-17) * 283 + (58) * 83
  4 = 1 * 3 + 1     |   1 = (22) * 283 + (-75) * 83

The final result is correct according to google calculator.

When I use modulo 283 on both sides I get:

1 = (-75) * 83 = (283 - 75) * 83 = 208 * 83

So I got 208 instead of 202!

My experimental implementation of this procedure is here.

public static int RijndaelInverse(int a)
{
    int old_s = 0; int s = 1; int new_s = 0;
    int old_t = 0; int t = 0; int new_t = 1;
    int old_r = 0x11B; int r = 0x11B; int new_r = a;

    while (new_r > 0)
    {
        int quotient = r / new_r;

        old_s = s;
        s = new_s;
        new_s = old_s - quotient * s;

        old_t = t;
        t = new_t;
        new_t = old_t - quotient * t;

        old_r = r;
        r = new_r;
        new_r = old_r - quotient * r;
    }

    if (r > 1) return 0;
    if (t < 0) t = t + 0x11B;

    return t;
}

I tried substituting the multiplication with RijndaelMultiply and subtraction with RijndaelSubtract but that broke the whole algorithm and gave me crazy values. I think it's because the algorithm requires negative values to work, and there is no easy way of dividing polynomials that I know of.

Does anyone know how to correctly use EEA with Rijndael finite-field?

[EDIT] Working implementation

public static uint RijndaelInverse(uint a)
{
    uint old_s = 0; uint s = 1; uint new_s = 0;
    uint old_t = 0; uint t = 0; uint new_t = 1;
    uint old_r = 0x11B; uint r = 0x11B; uint new_r = a;

    while (new_r > 0)
    {
        var r_msb = (int)Math.Log(r, 2.0);
        var new_r_msb = (int)Math.Log(new_r, 2.0);

        int quotient = r_msb - new_r_msb;

        if (quotient >= 0)
        {
            old_s = s;
            s = new_s;
            new_s = old_s ^ (s << quotient);

            old_t = t;
            t = new_t;
            new_t = old_t ^ (t << quotient);

            old_r = r;
            r = new_r;
            new_r = old_r ^ (r << quotient);
        }
        else
        {
            new_s = s ^ new_s;
            s = s ^ new_s;
            new_s = s ^ new_s;

            new_t = t ^ new_t;
            t = t ^ new_t;
            new_t = t ^ new_t;

            new_r = r ^ new_r;
            r = r ^ new_r;
            new_r = r ^ new_r;
        }
    }

    if (r > 1) return 0;

    if (t > 0xFF) t ^= 0x11B;

    return t;
}


texts:
I am read the Lemma 2 (pp13) in the paper "Kazukuni Kobara and Hideki Imai: Semantically Secure McEliece Public-Key Cryptosystems –Conversions for McEliece PKC– (PKC 2001)".

Related to the question "Why… for any $Hash_z$ and any $Gen$?", the author of the paper replies;

  The reason why "for any $Hash_z$ and any $Gen$" is that if the sentence is
    not included the cryptosystem may be broken due to weak $Hash_z$ or $Gen$.

I know the hash strong definition:

There exist no x and x' with x != x' so that h(x) = h(x')

In this case are $x=Hash_z$,  $x'=Gen$" and $h=A$?
Are the $Hash_z$ and $Gen$" from Lemma 2 the same that $Hash_z$ and $Gen$" of Figure 5 of that paper?


texts: The right way to encrypt sensitive data with an user password

texts:
I am developing something like 1Password and I want to be sure that method that I use is secure. Main idea of the app is storing user passwords, and is protected with a global master password. Main scope of this post is to be sure that algorithms and logic will protect user's sensitive data from brute force, rainbow table attacks, even with special ASIC hardware

Algorithm

**All generated data are using secure random generating_random_data

Creation

User define a Master Password
I generate random Master Key, secret high entropy key
I generate random Master Salt, this is not secret and will be appended to final public binary
Derive using Argon2id from Master Password and Master Salt, 96 bytes

32 bytes Derived Key
32 bytes Derived Hash
32 bytes Derived Salt

Hash using Blake2b from Derived Hash and Derived Salt and name result Pre Hash
Hash using Blake2b from Pre Hash and name result Public Hash, this hash is not secret and will be appended to final binary file
Encrypt using Authenticated encryption XChaCha20Poly1305Ietf -> Master Key, with previously Derived Key and name result as Public Encrypted Master Key
Save into a Public binary file Master Salt, Public Hash, Public Encrypted Master Key

Opening

Read Master Password from user's input
Read Master Salt from user's Public binary
Derive using Argon2id from Master Password and Master Salt, 96 bytes

32 bytes Derived Key
32 bytes Derived Hash
32 bytes Derived Salt

Hash using Blake2b from Derived Hash and Derived Salt and name result Pre Hash
Hash using Blake2b from Pre Hash and name result Public Hash
Compare Public Hash from step 6 with saved in Public binary Public Hash that was previously saved in step 8 when created
If NOT equal throw invalidPasswordOrCorruptedData
If equal Decrypt using Authenticated encryption XChaCha20Poly1305Ietf -> Public Encrypted Master Key with previously Derived Key from step 4 and name result as Master Key
Use Master Key to encrypt and decrypt user's sensitive data

Summary

From above logic it is clear that we encrypt Master Key with derived data from user's password and then use that Master Key to encrypt all other sensitive data

Questions

Is this logic enough for protecting user's secrets ?
Will it protect from brute force, rainbow table attacks ?
Are there any steps that must be eliminated or useless ?

Remarks

I am using libsodium, swift-sodium for all crypto operations, and follow libsodium's best practice and suggestions

By default I am using 10 iterations and 64M of RAM for argon2id


texts: Are there any long term RC4 bias based exploits?

texts: The RC4 cipher possibly exhibits low level bias in it's long run PRNG keystream.  I'm specifically excluding short term bias attacks which I'm defining as outputs < 1024 bytes.  Are there any real world attacks that exploit this feature?


texts: Although SHA-1 theoretically has collisions, HMAC-SHA-1 which is based on SHA-1 is still widely used (in TLS for example) and is considered to be secure. How is that possible?


texts: LFSR, different bits from different initial states

texts:
Suppose we useLFSR, which gives output $x_1x_2x_3\dots$ from some particular initial state. From another state, different from previous, same LSFR though, it gives sequence $y_1y_2y_3\dots$

Intuitively for some $i$ inequality must hold truth $x_i\neq y_i$, but "intuitively" isnt exactly convincing, neither "empirically"

Is it really truth that for some $i$ bits will be different ie $x_i\neq y_i$, and if so - why?


texts: Random Number Generation with a Entropy pool versus Seed

texts:
To give a little background I'm currently implementing a crypto library in JavaScript.

I have started porting across Linux's random number generator because its both publicly scrutinized, it is open-source, and is extremely well documented. After browsing around other implementations before settling on Linux's RNG, most of the other implementations like the Mersenne Twister and other PRNGs all use single byte seed values as their single source of entropy and to add more entropy you simply XOR the seed value with your "stream of entropy". Linux's RNG however uses a pool of entropy which consists of, as it sounds, a larger array of "seed" values in which all are considered to have a high amount of entropy. To add entropy, you simply XOR the entropy into the pool and mix it around with a few polynomials and hash it all to hide the internal state.

What I want to know is what are the benefits of using an entropy pool over a single byte seed value? It also sparks the question, considering Linux's RNG is used almost globally across the entire kernel and by every application requiring random data, is the "seed" or entropy source dependent on its use case? If only one application will be using the RNG at a time, is a single byte seed just as secure as a larger pool of entropy? Is the only reason Linux uses an entropy pool is to not give away any hints on internal seed state if other applications pull random data from it?

I guess what I'm trying to ask is what are the benefits of using a single byte seed value over an entropy pool, and is an entropy pool relevant for single user RNGs where only a single, trusted user uses the RNG?


texts: What advantage does facebook's new encrypted access_token have?

texts:
When a user on facebook grants an app access to their account, an API key is issued to the app. This key is app and user-specific. This process is described in Facebook's developer documentation.

Until recently, API keys could be parsed- they contained the app's numeric ID, the user's ID, and other information (timestamps, validity, etc) encoded and used by Facebook to track the app and grant/revoke permissions.

As described in Facebook's documentation, https://developers.facebook.com/docs/oauth2-https-migration/, the access tokens given to apps are now encrypted. What does Facebook accomplish by encrypting the access token? Other than the fact that you can no longer tell by looking at it what user and app it belongs to, nothing is changed from what I can tell. If the token is stolen, it can still be used, encrypted or not, to access the user's account.


texts: Counter mode uses a counter that is incremented for each block. Doesnt predictability of this counter expose the scheme to attack? I mean if you are incrementing some nonce, then I have a good chance of guessing the next value


texts: Mathematical calculation to determine probability of observing the character space used for a set of string inputs

texts:
I am designing some methodology to determine the composition of wireless router security passphrases in terms of the character space used to generate them.

The problem I am having is I am unsure what formula or technique I can use to calculate the number of strings I would need to observe in order to determine the full character set which was used to generate these passphrases.

I was thinking along the lines of the birthday paradox but I am not sure if this is applicable for my problem.

The algorithm to deduce the string composition is simple: the passphrase strings will be read and every character will be processed. If the character hasn't been seen before, it will be added to a temporary array and if the character has been seen before, it won't be added. Thus, at the end the array will store all the unique seen characters from the processed strings (the passphrases in question).

Let's say the character space that the router manufacturer used to generate these passphrases was 62 different characters in size. For example:

abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789

(a-z lowercase, A-Z uppercase and 0-9)

These generated passphrases are just strings like these for example:

2UAYnCtL
YR3kLX49
MJLDJIgt
xouq9KOV

Considering that each passphrase is 8 characters in length and that these passphrases are randomly generated by picking characters at random from that example character space mentioned above, how many strings will my algorithm need to see before it can build a complete representation of the above mentioned character space ?

Or in other words how can I determine the minimum number of strings which need to be observed in order to have a high probability (or close to 1 probability) of my algorithm being able to recreate that character space mentioned above ?

Please let me know if anything is unclear. Thanks for your input !


texts: Williams' $p+1$ in tandem with Pollard's $p-1$?

texts:
Since the success of the $p - 1$ algorithm depends on $p - 1$ having "small" prime factors, or at least smaller than a reasonable smoothness bound, and Williams' $p + 1$ method has the same constraint for $p + 1$, it seems to me that it would be extremely unlikely for neither $p - 1$ nor $p + 1$ to be smooth. So if we were to construct, say, a tough 500-bit (RSA-type) semiprime such as

$n = pq = \ $ 2218295966162666629041316944231086113195058068148716022472522769336934503490317077398434252307822130896437753111872862038992461352826985916137012449841,

where $p$ and $q$ are both "safe" primes to guarantee worst-case performance for the $p - 1$ algorithm (that is, $(p - 1) / 2$ and $(q - 1) / 2$ are both Sophie Germain primes), would it make sense to attempt the $p + 1$ algorithm after $p - 1$ had bailed out? In other words, is there anything to be gained by trying that before ECM or bringing out the "big guns" of QS or NFS?

Oh, and I also generated the above semiprime with $\frac{p}{q}$ large enough to thwart factoring via Fermat's difference of squares method:

$\left|p - \sqrt{n}\,\right| \gt \sqrt[4]{4n}$.


texts: When is factoring semi-primes thought to be hard?

texts:
In Lattice Cryptography, problems like LWE or SIS have relatively easy to specify distributions that are thought to be average case hard.
I'm curious what specific distributions on semi-primes $(p,q)$ such that $N = pq$ is a certain bit-length are thought to be average case hard.

Essentially, there are many different special-case factoring algorithms for when $(p,q)$ have some special structure (I've found Pollard's $p-1$ algorithm, William's $p+1$ algorithm fairly easily, things like Coppersmiths seems to apply if some number of the bits of $p$ or $q$ leak.

What I'm curious about is which of these attacks on semi-primes with special structure are devastating enough such that proper generation of $(p,q)$ should explicitly check that they don't have that structure.

In a certain sense this question is asking for current "best practices" for RSA modulus generation, but with the intent of getting pointers to why best practices are what they are (as in which attacks they avoid).


texts: WebCrypto SubtleCrypto RSA sign/verify AND encrypt/decrypt?

texts:
I have a project where I'd like to use public-key cryptography in both typical sign/verify situations and encrypt/decrypt situations.  For example, I'd like to create a self-signed X.509 certificate for Bob (certificate request containing PubK.bob, signed by PrivK.bob to form Certificate.bob), and I'd also like to conduct transactions like:

Alice selects document key DocK, encrypts document DocK[document], computes PubK.bob[DocK], and sends PubK.bob[DocK] to Bob.
Bob uses PrivK.bob to recover DocK from PubK.bob[DocK], then decrypts DocK[document] to receive document from Alice.

However, the RSA keys that can be generated by crypto.subtle.generateKey (RSASSA-PKCS1-v1_5, RSA-PSS and RSA-OAEP) can only be used for either ['sign','verify'] or ['encrypt','decrypt'] -- if you try to generate a key with all four usages, you get Cannot create a key using the specified key usages.

Is there a subtle crypto reason not to use a single RSA keypair for both sign/verify and encrypt/decrypt operations?

Is there a standard way of dealing with this?  A good way of doing it using WebCrypto?  (I can imagine putting an encrypt-capable public key into Bob's certificate, along with the verify-capable one, but that seems redundant, and also makes my certificates a little different from what other certificate-management tools are used to dealing with.)


texts: Hashing function as a cipher in CTR mode

texts:
Can we use hashing function in CTR mode as a cipher? And our key could be a random initialization vector.
Are there any practical problems with that idea, that we don't do this?


texts: What are the fundamental roots of modern symmetric encryption?

texts:
In academic pursuits, we often have people (and their ideas) who are considered fundamental to the subject, such as Bayes and probability.
In cryptography, it's obvious to see that the Diffie-Hellman problem is fundamental to modern key exchange algorithms.
Can modern day symmetric encryption methods be similarly traced back to particular fundamental roots or building-blocks? If so, what are they?
Is there a common grandparent (or few) that most modern symmetric crypto such as AES or ChaCha can be undeniability related to?


texts:
If 3DES/TDES (officially TDEA or Triple DEA - Triple Data Encryption Algorithm) encryption is used twice, using 6 different keys K1-K6 :

ciphertext = EK6(DK5(EK4(EK3(DK2(EK1(plaintext))))))
plaintext = DK1(EK2(DK3(DK4(EK5(DK6(ciphertext))))))

would be such encryption more strong and less vulnerable to attacks than a regular 3DES ?

Furthermore, instead of E-D-E-E-D-E encryption and D-E-D-D-E-D decryption, would such double 3DES work with D-E-D-E-D-E encryption and E-D-E-D-E-D decryption as well?


texts: Encryption using deterministic CSPRNG as secure as CSPRNG

texts:
As a beginner it seems that a scheme derived from a CSPRNG should be as secure as that CSPRNG. Is this a correct assumption? Are there restrictions or known special cases? A rough outline would be:

Generate an IV using a non-deterministic CSPRNG.
Use that IV to seed a deterministic CSPRNG.
XOR each byte of input with a byte from the d-CSPRNG #2.
Concatenate(IV, output of #3)
Use key to seed a deterministic CSPRNG.
XOR each byte of #4 with a byte from the d-CSPRNG #5

In pseudo-code:

# encrypt
iv = randomBytes(IV_SIZE)
c1 = xorUsingPRNG(plaintext, dCSPRNG(seed = iv))
iv_c1 = iv ++ c1
c2 = xorUsingPRNG(c1, dCSPRNG(seed = key))

# decrypt
iv_c1 = xorUsingPRNG(c2, dCSPRNG(seed = key))
iv = iv_c1[0:IV_SIZE]
c1 = iv_c1[IV_SIZE:]
plaintext = xorUSingPRNG(c1, dCSPRNG(seed = iv))

Both the Key and IV are of reasonable size (meaning they are significantly larger than just a few bits).

Are there any known attacks that would work on such a scheme - under assumption that the CSPRNG used is secure.

If the CSPRNG is secure and produces "random" numbers than the output of (any_data XOR random_numbers) should have the same properties in terms of randomness/distribution for as long as those two are independent.

If the CSPRNG is secure then even if one knows or choses the plaintext it shouldn't be feasible to reconstruct the seed used nor should it be possible to extract the keystream because of the randomization in #3.

Obviously the following doesn't work:

Seed a d-CSPRNG with the key
XOR input with output of d-CSPRNG

because this is trivially broken with known/chosen plaintext attacks.


texts: Does resuing pederson commitment preserve the hiding property?

texts:
Assume you have a pedersen commitment scheme where the commitment is:
$$\mathcal C_1 =C(m,r)=g^m\cdot h^r$$
with $g,h$ being public generators in a public group $(G,\cdot)$ in which the discrete logarithm is hard. Assume now, we reuse this scheme to produce another commitment $C_2 = C(m, r') = g^m \cdot h^{r'}$ for the same message (but using another random value) and share that also.
Would generating two commitments in this scheme still preserve the perfect hiding property?
Also consider the case where we generate $C_1, \dots, C_n$ commitments for the message $m$. Could we - given those commitments - with non-negligible probability distinguish this from a series of commitments with $C'_1, \dots, C'_n$ that we generated for different messages, so $C_i = C(m_i, r_i)$, where $m_i \neq m_j$ for $1 \leq i < j \leq n$?
My intuition is that would not preserve the hiding property, since we could just divide the different commitments and observe a difference - is this correct?


texts: Fastest known Elliptic Curve Cryptography "solution" (coordinate systems (multiple?), algorithms, precomputed values etc)?

texts:
I am writing an Elliptic Curve Cryptography SDK in pure Swift, and currently I am only using Affine Point and simple Double-and-add. I am soon about to work on a faster solution.

I am asking for help with the fastest known ECC arithmetic. Of course, we have different types of curves, so the answer is probably that some solutions only apply to certain curves (e.g. for Montgomery Curves we can use "Montgomery ladder" which seems fast).

(This question itself probably contains some errors, misunderstandings or inaccuracies, I apologize for that I am quite new to this. Give comments about my question I will correct it and type which corrections I did in an edit.)

Different curves/forms?:

Edwards
Montgomery
Weierstrass
Hessian

Point multiplication algorithms

The wikipedia page about Elliptic Curve Point Multiplication gives a good overview, listing some different algorithms:

Double-and-add
Windowed method
Sliding-window method
w-ary non-adjacent form (wNAF) method
Montgomery ladder (Only for Montgomery curves?)

Coordinate systems

I know that I can use a combination of different coordinate systems:

Affine
Projective
Jacobian (Weighted Projective)
Modified Jacobian
López–Dahab
Chudnovsky Jacobian

Promising papers

The paper Complete addition formulas for prime order elliptic curves by Renes et al from 2015 (download from iacr.org) lists many different algorithms some of which mixes different coordinates systems looks promising.

The paper Fast elliptic curve point multiplication for WSNs by Ravi Kodali from 2013 (download from researchgate.net) proposes a mixture between Projective and Jacobian coordinates in combination with w-ary non-adjacent form (wNAF) method. It shows some promising results.

Does anyone have a reference to a study, implementation of different algorithms or otherwise "truth" about which solution - a set of coordinate systems and algorithms that enables the fastest known Point multiplication for e.g. X25519 (Curve25519) (Montgomery curve) and secp256k1 (Not Montgomery)???


texts: How do Quadratic Residues work and how do they relate to Diffie Hellman?

texts: Can someone explain Quadratic residues to me in english? I keep reading forums with all the math symbols and it's hard to follow. And how are they incorporated in Diffie-Hellman? Is there a difference in using them vs cubic residues?


texts:
We have a message denoted $M$. Let us suppose that we have a collision-resistant hash function $h_0$ with output length $n$. We then consider two other independent (different) hash functions $h_1$ and $h_2$, with output length $n/2$. For instance, we can choose SHA-256 for $h_0$, and SHA-256 with a truncated output (128 bits) for $h_1$ and $h_2$. Note that $h_1$ and $h_2$ are obtained by domain separation, i.e. $h_1=\operatorname{lsb}_{128}(\mathrm{SHA256}(M\| 1))$ and $h_2=\operatorname{lsb}_{128}(\mathrm{SHA256}(M\|2))$.

We now consider the hash function $h_3$:
$$h_3(M)=h_1(h_0(M)) \| h_2(h_0(M))$$

I have read that the concatenation of two independent hash functions appied on the same message does not increase the security when the message is long. What about the above $h_3$ function, when compared to $h_0$? In terms of collision-resistance and second-preimage resistance.


texts: Secure equivalent for giving an unknown card, applied to magician's card tricks

texts:
I suspect that this is already something trivial, but I can't find the answer, probably because I don't know how to search the cryptographic primitive that refers to my problem.

Imagine the typical card trick from your favorite magician. He/She offers you one random card, and you take one card where the magician doesn't know which card is. After that, the trick consists in guessing the card, doing their things.

My question is... Is it possible to have a protocol that resembles the first part? It would be something like, user authenticates to the server, and the server sends one, and only one, card (or any other information segment), where it's guaranteed that the server that sent the card doesn't know which card was sent to that user.

Thanks in advance.


texts: If the output size of SHAKE128/256 is variable, why is the security fixed at 128/256?

texts: The general idea is that the security strength of a good hash function is equal to half it's output length. The output length of SHAKE128 and SHAKE256 is variable, but their strengths are still said to be 128-bit and 256-bit, respectively. Why is that the case?


texts: Weakness of Hash_DRBG when entropy is mixed in gradually

texts:
NIST SP800-A states (Appendix C p. 89):

  There are known problems with Hash_DRBG when the
  DRBG is instantiated with insufficient entropy for the requested security strength, and then later provided with enough entropy to attain the amount of entropy required for the security strength, via the inclusion of additional input during a generate request. However, these problems do not affect the DRBG’s security when Hash_DRBG is instantiated with the amount of entropy specified in this Recommendation.

There is no such warning about HMAC_DRBG.

What are those known problems? The publication does not give a reference for this.

This may or may not be related to weaknesses in an early draft of Hash_DRBG. The concern is the same, but those weaknesses are supposed to have been fixed, so there shouldn't be any remaining “known problem”.

I know that HMAC_DRBG may be preferable for “theoretic” reasons — Hash_DRBG relies on much stronger assumptions about the underlying hash. But weakness in the face of an entropy source of worse quality than expected is a practical concern in many scenarios. In what way is Hash_DRBG weak when initially instantiated with low entropy, that mixing in entropy later doesn't fix?


texts: Randomness re-use in LWE encryption scheme

texts:
Let me describe the scheme first, it is the scheme proposed by O. Regev when he introduced the LWE assumption.

$sk = \textbf{s} \in \mathbf{Z}_q^n$
$pk = \textbf{A}\textbf{s}+\textbf{e}$ where $\textbf{A}\in \mathbf{Z}_q^{m\times n}$ and $\textbf{e}\leftarrow \chi^m$
$ct=(\mathbf{r}\mathbf{A},\mathbf{r}pk+\lfloor \frac{q}{2} \rceil x)$ where $\mathbf{r} \leftarrow \{0,1\}^m$ and $x$ is the message

I know that this scheme is secure under randomness reuse, that is for 2 different messages $\mathbf{x}_1$ and $\mathbf{x}_2$ and secret keys $\mathbf{s}_1$ and $\mathbf{s}_2$, the following scheme is secure against chosen plaintext attacks:

$ct = (\mathbf{r}\mathbf{A},\mathbf{r}pk_1+\lfloor \frac{q}{2} \rceil x_1,\mathbf{r}pk_2+\lfloor \frac{q}{2} \rceil x_2)$

Here is my question: If an adversary has one of the secret keys, say $s_1$, is the message $x_2$ still secure against him?

I've been searching around but I only found about security when the adversary doesn't know any key.


texts: For the symmetric-key encryption algorithm, is it possible to use the exponent and modulo to be the keys

texts:
For example:

Encrypt with: $M^{k_1} \bmod k_2$

where $M$ is message, $k_1$ and $k_2$ are independent keys

If it is possible, what is the decryption algorithm?

Thanks!


texts: Is it safe to reuse ECDH asymmetric keys for authentication?

texts:
Alice, Bob, and Carol each generate ECDH keypairs.  Alice and Bob establish a communication channel and negotiate an AliceBob secret.

The question is:  Is it safe for Alice and/or Bob to reuse their keypairs to negotiate a new AliceCarol and/or BobCarol secret?

The intended use is authentication.  Each party can persistently store the others' public keys, and persistently store or deterministically recreate their own private keypair.  Each party could establish a new communication channel with another party at a later time, verify that the other party's current public key matches their previous public key, generate a random message M and send it to the other party.  The other party can then use the negotiated secret to HMAC sign M to generate M' and send M' back.  At this point, M' can be verified by the originating party re-calculating M' using the negotiated secret, thus validating the other party's identity.


texts:
We're building a data service that is expected to go out through a single "fat pipe" channel. The design requirement says that the data in the channel must be protected by authentication and encryption. I'm ready to argue that the strongest encryption for such a system (single channel, multiple subscribers) is the "cable box" method - a single key for all subscribers.

Is there a more secure method than this - one that doesn't have the same key for every subscriber?


texts: why doesn't quadratic residue attack work with Elgamal encryption with decisional diffie Hellman assumption?

texts:
I was reading this notes http://www.cs.umd.edu/~jkatz/gradcrypto2/NOTES/lecture4.pdf

It's given that discrete log assumption is not enough for semantic security, I'm assuming there maybe chance of getting quadratic residue even if we choose x and r so that both are not even.

But what about decisional diffie Hellman assumption? Isn't it just same? Can't the adversary similarly select one message which is quadratic residue and do the same attack?


texts:
In a Diffie-Hellman exchange, the parties need to agree on a prime p and a base g in order to continue. Assuming some application that's going to want to initiate handshakes with some large portion of its users, each of which only needs to be realistically secure for a few hours,

Approximately how large should p be?
How often should p be changed, if ever? Every n handshakes, every m hours/days/weeks?
Is there a trade-off between dynamic generation/size of p?  Is it better to find a single ~120 digit prime and always reuse it or generate a ton of ~28-38 digit primes and randomly pick one per handshake?
Am I even asking something approaching the right questions (and if not, could you point me in a better direction)?

Intuitively, it seems that the size of the chosen secret integers has more to do with the channel's security than the uniqueness of p, but I'm still asking since I'm no mathematician.


texts:
To perform a bit flipping attack, the previous block is modified by using XOR. This results in an altered plaintext. However, now the ciphertext of the previous block is altered, hence it will result in an invalid format. Am I correct or am I missing something?

For example, suppose I have the following plaintext name=jcconvenant;photo=picture.jpg;admin=false;colour=red;

and the correspoding ciphertext c26a5697689463d662f540e55e2a1ecef9c5df20133dfe49d6d3c369679a95ff4f4c5a490f530b2a2f25db40da64f1e9302724ce61b9a435e23f4d600252a143

Suppose we perform a bit flipping attack and get the following ciphertext
c26a5697689463d662f540e55e2a1ecef9c5df20133dfe49d6c1d07071c495ff4f4c5a490f530b2a2f25db40da64f1e9302724ce61b9a435e23f4d600252a143

Then the resulting plaintext will still look corrupted.

¶ä╚°  h8ì│►Nƒz│Ioé¤ßkü2KÀQiý4I@pg;admin=true;;colour=red;

Is there a way to perform bit flipping while still obtaining a valid plaintext?


texts: Defining correct secured channel from endpoint to server

texts:
I'm new to cryptography and have a question regarding encryption usage.

The scenario is as follows:

I have an endpoint hardware device (CPU - ARM A7 1.2 ghz) which runs Ubuntu 14.04.
This hardware device needs to communicate with a server (CPU - Xeon family) which also runs Ubuntu 14.04.

What is the most secured way to implement on this channel?
Does only symmetric encryption is enough? or it is better to use a-symmetric for key exchange?
What else can be added to this channel? digital certificates? MAC's for integrity?

Thanks for the answers


texts: Information theoretic message authentication code (MAC)

texts:
Let's $\ a,b\ $ be two (pseudo)random independent values, and $m$ be a message, where $a,b,m \in \mathtt{F}_p$, where $p$ is a large prime number.

Question 1: Is $\ am+b\ $ an information theoretic MAC?

if yes

Question 2: Is there any paper/textbook uses it?


texts:
I have been stuck all day trying to understand how to show that an Encrypt-and-Mac ($SE_{EaM}$) scheme is not IND-CCA secure. I have seen this similar post, however it is slightly different and the notation in the selected answer confuses me.

The line of thought I want to follow is this: While the $MAC$ is perfectly UF-CMA secure it could still reveal information on the message since its computed directly from it and not the ciphertext (like in encrypt-then-mac). Consequently this would mean that $SE_{EaM}$ is not even IND-CPA secure, and therefore not IND-CCA secure. I want to know first if this line of reasoning is sound.

In terms of actually showing this, is it feasible to simply suppose that the $MAC$ scheme could afford no privacy to the message whatsoever. The post I referenced seems to have done that by adding the message in the clear to the actual tag ($t = m|t$), if I misunderstood I would appreciate clarification. If this is valid how could I use this in a IND-CPA game of $SE_{EaM}$?

I hope it will then become clearer how to show in a reduction that since IND-CCA implies IND-CPA, my $SE_{EaM}$ scheme is not IND-CCA. Or maybe I am looking at it completely wrong, in which case do let me know.

Thanks and happy new year!


texts: Can one reduce the size of ECDSA-like signatures?

texts:
Using $n$-bit ECDSA, a signature has a size of $2·n$. It is possible to recover the public key from this signature, which shows that there is a publicly visible redundancy in the signature.

Is it possible to exploit this redundancy to reduce the signature size to $n$ bits, sacrificing key recovery?

I suspect it's not possible, but I don't know enough about elliptic curves to be sure.


texts: Is $F(x) =Ax+b$ a pseudorandom function or not?

texts:
Consider the following keyed function $F$: For security parameter $n,$ the
key is an $n\times n$ boolean matrix $A$ and an $n-$bit boolean vector $b$. Define
$F_{A,b} : \{0, 1\}^n->\{0, 1\}^n$ by $F_{A,b}(x) = Ax + b$, where all operations are
done modulo $2.$ Show that $F$ is not a pseudorandom function.

I have thought for a whole day but could not conquer it, so hope to get the solution here. Thanks.


texts:
I am trying to implement the following Schnorr non-interactive zero-knowledge protocol: https://tools.ietf.org/html/rfc8235#page-7

I'm using the libsodium 1.0.16 and GNU MP libraries.

I just can't seem to get it working. Here are some questions:

    In the setup of the scheme, Alice publishes her public key
    A = G x [a], where a is the private key chosen uniformly at random
    from [1, n-1].

    The protocol works in three passes:

   1.  Alice chooses a number v uniformly at random from [1, n-1] and
       computes V = G x [v].  She sends V to Bob.

   2.  Bob chooses a challenge c uniformly at random from [0, 2^t-1],
       where t is the bit length of the challenge (say, t = 80).  Bob
       sends c to Alice.

   3.  Alice computes r = v - a * c mod n and sends it to Bob.

   At the end of the protocol, Bob performs the following checks.  If
   any check fails, the verification is unsuccessful.

   1.  To verify A is a valid point on the curve and A x [h] is not the
       point at infinity;

   2.  To verify V = G x [r] + A x [c].

Regarding step (3) on the computation of r = v - a * c mod n it means that this step is using regular modular arithmetic?

Regarding step (2) on the verification V = G x [r] + A x [c], can you please explain how that would hold? Is the following equivalent: V = ed25519_scalarmult(r, ED25519-BASE) + ed25519_scalarmult(c, A) where ed25519_scalarmult(scalar, point i.e. publickey)? And most importantly that + is Ed25519 point addition?


texts: Hardware AES: can we have a decryption implementation only?

texts: I'm wondering if implementing only the AES decryption can reduce the hardware cost? And does anybody have some examples of the cost (speed, size) of hardware AES implementation?