texts: Are GPUs inefficient for calculations on big numbers? Is RSA and EC cypto generally done on CPU only?

texts:
Looking specifically at RSA and EC algorithms which imply doing operations on integers >= 256 bits (>> 64 bits), I have noticed (from my limited experience) that 99% of the software for crunching big numbers is designed for CPU. For example, there appears to be no actively maintained CUDA package for big-number operations (arbitrary length or even 256-512 bit numbers for EC calculations).
Is there a reason for big number calculations (and thus RSA and EC calculations) to remain on CPU? Is it sub-optimal to run such computations on GPU (I understand that GPUs are not optimized for big number calculations because there is no such requirement in graphics, but can't it be efficiently done anyway)? Will this change in the future or will RSA & EC remain on CPU?


texts: Can I use a GnuPG created key for OpenSSH or authentication purposes?

texts:
I created a key pair using PGP (GnuPG) for the purpose of encrypting and signing data (documents, emails, and so on). That key was created with the RSA algorithm, and naturally starts with:

-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: GnuPG v2

I would like to know, if it is possible, to "convert" that very same key pair for the purpose of authentication using SSH (example: AWS instance or some other remote SSH server). I realize that the result would probably yet another key pair in a different format (.pem for example.)

The idea would be to use the same original RSA key pair (and therefore the same secret passphrase) for all the following purposes: encrypting, signing and SSH authentication.

How would I exactly do that and what are the limitations involved (for example, with private key passphrases, etc)?


texts: Is RSA encryption with a private key the same as signature generation?

texts:
It is often said that RSA encryption of a cryptographic hash with a private key is the same as signing (signature generation). And that verification consists of decryption using a public key.

Is RSA encryption with a private key over a cryptographic hash equivalent to  signature generation?


texts: Discrete log accumulator without pairings?

texts:
Here $g$ is some fixed generator of a discrete log group. I don't want the group to be bilinear for efficiency and BDH-skepticism reasons.

Is anyone aware of a discrete log accumulator? What I mean specifically is some function $f(x, A)\mapsto A'$ (that is, $A$ is the accumulator value; $f$ adds $x$ to the accumulator, changing its value to $A'$) such that given $(g^x, A')$ anyone can check whether $x$ was placed in the accumulator.

So I'm roughly asking for an accumulator with the property that an accumulated element $x$ has $g^x$ as a witness.


texts: Decimal point in keyspace notations? (eg 2^54.15)?

texts:
I was reading up on CryptoCat's (pretty ridiculous) programming issues and how is dramatically reduced the key search space (link to bug synopsis)

One thing that caught my eye was

  So 2^54.15 turns into 2^27.08

Unless I'm missing something, the impact of the fractional exponent is negligible. So, any ideas why the author is reporting it as 2^54.15 and not just 2^54 ? I mean for O notations, we usually state only the degree of the highest order polynomial (that expresses algorithmic complexity), ignoring the factors and lower order powers.

So am I missing something here when it comes to expression of keyspaces?


texts: Lattice reduction question regarding the capability of LLL and BKZ

texts:
I've been reading How to estimate the hardness of SIS instances? and following some of its sources, and I want to confirm a few things.
LLL algorithm runs in polynomial time, but isn't capable of producing arbitrarily small basis, and is therefore not very relevant in cryptanalysis in most lattice-based schemes. Is that correct?
BKZ algorithm invokes a SVP (Shortest Vector Problem) oracle polynomial number of times, and the lower-bounded of the norm of the basis it produces is inversely proportional to the block size the SVP oracle operates on, regardless of the norm of the input basis; and the SVP oracle it uses runs in time exponential to the block size. Is that correct?


texts: If you were to design a PKI from scratch, what would you do?

texts: In what ways would you simplify?  What would be changed to be more modern or extensible?  Suppose you have no requirement to adapt to previous protocols.  Links to proposed designs, existing protocols, as well as any ideas are welcome.


texts: why did oaep change from pkcs1 v2.0 and v2.1?

texts:
In PKCS1 v2.1 the OAEP output is prepending with a null byte. Quoting RFC3447,

  i. Concatenate a single octet with hexadecimal value 0x00,
     maskedSeed, and maskedDB to form an encoded message EM of
     length k octets as

        EM = 0x00 || maskedSeed || maskedDB.

In PKCS1 v2.0 (as defined in RFC2437):

   11. Let EM = maskedSeed || maskedDB.

So in PKCS1 v2.1 you prepend a null byte and in PKCS1 v2.0 you don't. What technical difference does that change (and possibly others) create between the two versions of the standard?


texts: Is there a lower limit on message length for signature?

texts:
I was working on a tool that signs small messages (~20 bytes) when a question occurred about message size: What would be the risk of using extremely small/restricted input (say, 5 bytes of hexadecimal chars) messages? Since the data is a hash and replay attack is not a concern, the message wasn't originally salted.

Would a signature and/or collision be easier (/easy) to generate without the private key? Or would that make the private key vulnerable in any way?

In this particular case we are using Ed25519, which does double hashing on the value before encryption, so I don't see an issue for the public key, but I'm still concerned.


texts: Proving security of an encryption scheme

texts:
I have an encryption scheme $Enc(pk, m)$ which outputs ciphertext of the form $c_1 = (pk)^r, c_2 = g^r \cdot m$; where $pk$ is the public key of the form $g^a$, $a$ being the corresponding secret key.

Is this secure?


texts: I test this law with a 7-bits primitive polynomial LFSR. and the run property could be found according to output. Is there any theoretical to prove m-sequence property, I could just find some conclusion on some literature.


texts: "128-bit security" or "128 bits of security"?

texts:
Maybe a silly question but I am wondering what the correct way to specify a security level is:

128-bit security
128 bits of security
Something else entirely


texts: How to produce large list of BigInteger prime numbers (RSA) in fast and efficient way

texts:
Hello fellow experts here, in order to use RSA to encrypt and decrypt in a controlled environment, we will actually need to have a list of prime numbers to do so instead of using library generated RSA keys to encrypt and decrypt.

My current approach here is to actually skip all the even numbers and increment the BigInteger by 2 through looping to select and filter out the possible prime numbers. However this process is really performance taxing (by using BouncyCastle), I was wondering if there was really any faster and efficient method to generate an infinite amount of BigInteger prime numbers that can be used for RSA?


texts:
Hello guys I am trying to implement Certificateless Cryptography algorithm with reference to this base paper. Right now I am trying to implement the code in java. There are some points specified in PDF which I didn't understood. I need some help to understand how should I implement them.

The points are as follows (kindly correct me if I misunderstood any point):

  Pick a generator of $g$ of $Z_p^*$ with order $q$. -> for this step I just followed this link as reference and calculated $g$ as $g^{(p−1)/2}\bmod p=1$
  where $g$ is prime number.
  Choose cryptographic hash in the paper they have specified that they had used SHA-1 to generate hash. I can generate the hash values
  but I am not able to reproduce the hash functions given in base paper,
  does $(0,1)^*$ is used to represent binary.
  Hash usually generates hexadecimal values do I need to convert them into decimal for Raise operation i.e. power
  Does the hash needs to be of fixed size or not.
  Sorry to say but in summary I didn't understood the encryption part of this paper. I know stackexchange is not made to explain how it works
  but I just want a proper guide line so that I can implement the
  application.


texts:
I’m implementing an encrypted messaging web app using JS. When composing a message, the user is provided with the public key of the recipients. A body field is also rendered for every recipient. After the user clicks submit, the original message is encrypted with the recipients’ public keys, which is then inserted into their respective body fields.

Since every user has their own body field (the ciphertext varies between users), a malicious user could write a different message for every recipient. How should I go about tackling this problem?


texts: Pseudo random generator vs block encryption, which is faster?

texts:
If one wishes to encrypt one can either use a pseudo random generator to generate a long sequence and then xor it with plaintext, similarly he can use the seed as key to encrypt the plaintext using block encryption.
If encryption is not of paramount concern, which runs faster, pseudo random generator or block encryption?

I would highly appreciate if there is some survey or report on the running time comparisons.


texts: See any problems with this search-specific homomorphic encoding strategy?

texts:
I'm imagining this for use in the scenario of cloud-stored client-encrypted email, where, when seeking to do a string search across messages, you don't want to have to download every stored message in order to decrypt and search.

[Note that inspiration for this approach is taken from Jones & Mewhort, 2007; I otherwise assert no formal rights to the algorithm, but appreciate props if it's a good idea : O) ]

Initialization steps:

For each unicode character, client generates a D-dimensional vector (where D is large, >1024) where each element is a 64-bit float drawn from a random Gaussian with mean of zero and a standard deviation of 1/sqrt(D). Call these the "character vectors".
Client also generates a "permutation vector" representing a random permutation of the order of elements 1 through D.
All vectors are encrypted and stored by the client for later decryption and use while encrypting messages as described below.

When encrypting a message, a standard strong encryption (RSA, etc) of the message is computed, as well as it's associated "hologram", computed as follows:

For every bigram of characters, the associated character vectors are combined via circular convolution made non-commutative (and therefore encoding the bigram's character order) by first shuffling the second vector's elements according to the order prescribed by the permutation vector generated during initialization. Thus, if & is used to denote this non-commutative circular convolution, then a&b is a D-dimensional vector that is very different from (low cosine similarity with) b&a.
Since all vectors generated in step 1 are D-dimensional, they can be summed to a single vector H that holographically encodes the full set of vectors. That is, if a&b contributed to H but c&d did not, then the cosine similarity between H and a&b will be much greater than the cosine similarity between H and c&d. This isn't lossless encoding (circular convolution causes data loss, as does the superposition of bigram vectors into a hologram), but it'll be good enough...
Now repeat step 1 for all ngrams (up to a reasonable maximum search string length) in the text (i.e. if the text is abc, do a&b, b&c, (a&b)&c, a&(b&c)), continuing to sum each into H. At the end, H holographically represents the content of the message.

When done, client sends the encrypted message as well as it's associated hologram to the cloud for storage.

Steps for searching for a given search string:

Client computes a hologram for the search string exactly as they would for a regular message
Client sends the resulting search string hologram to the server
Server computes the cosine similarity between the search string hologram and each message hologram, yielding a rank ordered set of messages, the top X of which are sent back to the client
For each message returned from the server, the client decrypts the message and performs a standard plaintext string search.

It's possible that this scheme would get a worthwhile security benefit from having two permutation vectors, one for the left-hand vector and one for the right-hand vector, but I'm not clear yet on whether this would be necessary. I described it using one above for simplicity.

Certainly the initialization would need to be high-entropy, probably avoiding a single random seed, but since it's done only once, this shouldn't be too much of a hardship.

Thoughts?


texts: Understanding anonymous credentials. Does someone understand how it works?

texts:
After reading a series of papers CL01 CL02 CL04, I feel like I understand the intuition behind the anonymous credential framework but I don't understand some details the mathematics behind it.
I placed myself in a case example where this system might be useful, namely imagine that you want to prove to some organization that you are over 18 years old and that you eID have not expired. First, you issue an eID from  the government, in which you "hide" (commit) your pseudonym. That is, the government have to issue a signature on all your data (name, birthday date, adres...) and on your committed secret information (pseudonym). I understand how (mathematically) this part is done in CL02, but I have no idea how to adapt it for CL04.
Done this, you would use a zero-knowledge proof of knowledge to prove that you have such a signature to $O$. Then, you would create this proof of knowledge to only reveal your birthday date. But, how would you only prove that you are over 18, without revealing your exact birthday date?
To summary:

How it is possible to use the CL signature based on pairings CL04 to issue a partially blinded signature? In other words, issue a signature on some hidden (committed) data and some known data.
How it is possible to use the CL signature protocols in CL04 to prove that you are over 18, without revealing your exact birthday date?
It is possible to combine credentials (i.e., signatures) to produce one zero-knowledge proof of some subset of data in both credentials at the same time?


texts: How can I map arbitrary group elements to unique integers without using Hash functions?

texts:
Let's say, I have a group $G$ of large prime order $p$. A set $S$ consists of $n$ random elements chosen from $G$. Without using a collision resistant hash function $H$, how can I map elements of $G$ to unique elements in $Z_p$?

I thought about it before posting here. But, finding discrete logarithm for an arbitrary group is hard, right? In theory, it'd satisfy the requirement of collision resistance, but inefficient.

I don't really know the structure of the group beforehand. What I am essentially trying to do is, I am trying to figure out a generic means to map public key ($PK$) of a Public Key Encryption system to $z \in Z_p$, such that a third party can be convinced about the co-relation between the $PK$ and $z$ without revealing $PK$ but $z$ and some form of proof-of-knowledge. Hash functions, due it inherent nature of pre-image resistance, seems unsuitable.


texts: Are there any simple and yet secure encryption algorithms?

texts:
Being very new to C++ and cryptography, I finally managed to implement a version of the Vinegere algorithm. I would like to try something a bit more complicated. I have looked at AES and DES and others like them, but I was wondering if there is something simpler. Something that might use some of the same basic ideas as AES, but is much simpler. Some kind of block cipher maybe?

So I am asking for suggestions for a block cipher that is much simpler than AES, but more complex than a basic substitution algorithm. I have by the way looked into the method used in the Enigma-machines, but from what I understand they do "basically" the same as Vigenere.


texts:
TOTP (Time-based One-Time Password) as I understand is an algorithm that uses the current time as a variable along with a shared key to generate a secured token. Wiki page for reference: http://en.wikipedia.org/wiki/Time-based_One-time_Password_Algorithm

What I wanted to know is whether it is possible to determine the timestamp data (time + timezone) from a particular TOTP value? I can generate the shared key which was used to generate the TOTP value.

The problem I'm facing is that we make use of TOTP to perform validations between our offline Android/iOS clients and our server. However, once in a while we encounter a user whose TOTP tokens fail to authenticate. We ask them the same sundry questions about current time synchronisation and to check their timezone. Often times, users have a hard time determining even this.

So, I was wondering whether I could simply work out the timestamp + tz information myself from the faltering TOTP token, provided I have access to the shared key used to generate the said TOTP token.

Thanks for reading and any help would be greatly appreciated.


texts: Why does the crypto_box functionality in NaCl library exposes the nonce to the programmer

texts:
The idea of crypto_box API in NaCl library is to shield the programmer away from the technical details and provide easy to use functions for encrypting and encrypting messages.

Given what I've just written, I do not understand why the idea of nonce is exposed in this API. Explaining what nonce is and how to use it takes up a significant portion of the documentation and it is quite possible to get this wrong. Wouldn't it be better to just generate a random bytestring under the covers?


texts:
I am quite curious as to how you can perform simple encryption for the Chinese language.
Saw a similar question related to encryption/Chinese here: About cryptography in a character language, however the method of encryption appears to be quite complicated.
If I'm not mistaken, the method described in the answer above, requires something similar to a table which pre-maps certain characters to other characters; or the use of something like an One-time pad - both of which requires a fair amount of prior communication between both parties.
I was wondering if there is something simpler, what I have in mind is something like a Substitution cipher. That is, a way to encode the message easily, and also allowing the message to be decoded easily (if the secret key is known) or cracked given analysis or use of decoding techniques/knowledge.
For example, in English there are many ways to encrypt a message - some common/simple examples ROT13, Vigenere.
However, I can't seem to see how the concept of "pulling apart" a word can apply to Chinese characters.
For example, I can (fairly easily) encode the below using Vignere (key: chocolate), but how would I do so in Chinese?

I am learning Chinese --> K ha nslrgmpn Qjwyeli
我在學中文 --> ?


texts: Can we calculate AES-CBC-PKCS7 ciphertext length based on the length of the plaintext?

texts:
I am currently using AES256 in CBC mode with PKCS7 Padding to encrypt some data. It seems like the output size is not always a power of two, which was what I expected.

Is it possible to calculate the size in bytes of the output, knowing only the input data?


texts: Is there a standard way to use a nonce with HMAC?

texts:
Many protocols use HMAC on messages that include a nonce, but they don't seem to do it in a consistent way. For example, in OAuth the nonce is in the middle of an URL-encoded key-value string, like this:

POST&http%3A%2F%2Fexample.com%2Frequest&a2%3Dr%2520b%26a3%3D2%2520q
%26a3%3Da%26b5%3D%253D%25253D%26c%2540%3D%26c2%3D%26oauth_consumer_
key%3D9djdj82h48djs9d2%26oauth_nonce%3D7d8f3e4a%26oauth_signature_m
ethod%3DHMAC-SHA1%26oauth_timestamp%3D137131201%26oauth_token%3Dkkk
9d7dh3k39sjv7

This is probably because different protocols use the nonce for different purposes. However, I'm interested specifically in using a nonce with a constant message to get different authenticators for repeated messages (with the same key).

Is there a standardized way to include a nonce in HMAC authentication?
Is there any theoretical difference in between $H_K(\text{Msg}||\text{Nonce})$ and $H_K(\text{Nonce}||\text{Msg})$?


texts:
The CTR mode, with its CPA security, is one of the malleable block cipher mode of operations. An attacker can simply modify the bits of the ciphertext stream in their advance. This is due to the lack of integrity and that can be easily prevented with an HMAC. With Encrypt-then-MAC $$(c,IV) = \operatorname{AES-CTR}(IV,message)$$ and $$tag = \operatorname{HMAC-SHA256}(key,IV\mathbin\|c)$$
We have seen lots of real examples on the CBC mode due to the padding oracle attacks over the years. Padding oracle attack, however, is not applicable to CTR mode since it doesn't require any padding at all.

Is there any real attack deployed on the CTR mode over history?*

*Note: This question come into my mind while answering this question; Disadvantages of AES-CTR?


texts: How to choose constants in a cryptographic function?

texts: A number of cryptographic functions have constants built in. For example, the constants used in RFC 2104 for HMAC, or the constants used in s-boxes (e.g., DES and AES), or MD5.  In general, how are constants such as these generated so as not to arouse suspicion of tampering or weakening?


texts: How can I securely encrypt the same message multiple times?

texts:
I want to encrypt the same message multiple times. I want to store the encrypted messages together. I've heard if you do this with RSA, an attacker could decrypt the message with the Chinese Remainder Theorem.

What encryption methods do not suffer from this vulnerability? Would RSA with some random bits added to the message suffice?


texts:
I want to ask that does the common reference string in NIZK have to be
random?

Or can it be anything?


texts: How 2 rounds in AES achieve full diffusion?

texts:
I have read somewhere that 2 rounds is AES provide full diffusion. So I looked it up to find out what it exactly meant. In The Design of Rijndael page 41, section 3.5 and it states that:

  Two rounds of Rijndael provide 'full diffusion' in the following sense:
  every state bit depends on all state bits two rounds ago, or a change in
  one state bit is likely to affect half of the state bits after two rounds.

How does that happen. I would say that it's related with the fact that MixColumns is MDS but why this is achieved in two rounds?


texts: Public-Key Deterministic Encryption : Why does not provide perfect security?

texts:
I've got a question about an assignment . The question is "Why a Public-Key Deterministic Encryption Algorithm does not provide perfect security ?" . I suppose it means according to Shannon .

Any help could be awesome!


texts: Cryptographic hash where the hashing function input is similar to the result

texts:
I was wondering if there is a cryptographic hash where the resulting hash is identical to the input for the hash function.

If this is the case, would it be a weakness in the hashing function?


texts: Is the one-more discrete log problem hard in the Generic Group Model?

texts:
In the Generic Group Model (GGM), a concrete cyclic group of (known) order $n$ is replaced with an idealized version: a random encoding for group elements is chosen, and the adversary only gets access to the encoded form of any input group elements (such as the generator/public key/...), and an oracle to apply the group operation on them. The encoding is unique, so group elements can be tested for equality. It can be seen as the analogue of the Random Oracle Model for groups instead of hashes.
It is well-known that the discrete logarithm problem is hard in the GGM: Shoup showed that any generic algorithm needs $\Omega(\sqrt{p})$ group operations, where $p$ is the largest prime factor of $n$.
My question is whether the one-more discrete logarithm problem (OMDL) is also hard in the GGM. To break OMDL, an adversary is given $k+1$ random group elements, can make $k$ queries to a DL oracle, and must then succeed in finding the discrete logarithm of all $k+1$ inputs.


texts:
Assumptions:

$A$ wants to communicate with $B$
$A$ knows a public key $P_B$ which is trusted by a third party and belongs to $B$
$A$ knows the address of someone who pretends to be $B$

$A$ wants to send a message to $B$ using ECIES:

$A$ calculates a random private key $K$ and the related public key $P$
$A$ calculates a shared secret $Z$ using $K$ and $P_B$ according to ECIES
$A$ derives symmetric keys from the shared secret $k_1|k_2=\text{KDF}(Z_x)$
$A$ encrypts a message $c=\text{ENCRYPT}_{k_1}(m)$
$A$ tags the encrypted message $t=\text{MAC}_{k_2}(c)$
$A$ sends $P|c|t$ to someone who pretends to be $B$

Questions:

Can $A$ assume, that only $B$ can read the message? I think so.
As $B$ does not know anything about $A$ what is the cryptographic purpose of the MAC? As $K$ and $P$ are message specific anyone who knows $P_B$ could have sent this message with a valid MAC to $B$!?
Does removal of the MAC step reduce ECIES' security? I assume, but I don't get why.


texts: Semantic Security and Equal Message Length in the Context of Public Key Cryptography

texts:
A lot of definitions for semantic security make use an experiment $\text{Exp}$ which is performed between a challenger $\mathcal{C}$ and an adversary $\mathcal{A}$ that begins as follows:

$\mathcal{C}$ generates a random key w.r.t. the considered cryptosystem and a given security parameter. $\mathcal{A}$ selects two messages $m_0$ and $m_1$ of the same bit length (i.e., $|m_0| = |m_1|$) and sends $m_0$ and $m_1$ to the adversary (and so on).

Now, assume that the considered cryptosystem is a public key cryptosystem. In $\text{Exp}$, $\mathcal{C}$ randomly chooses a public/private key pair $(sk,pk)$. Assume that the public key $pk$ is given to $\mathcal{A}$. Let $\mathbb{P}$ be the message space determined by $pk$.

The question is whether—for the given setting—$\text{Exp}$ remains valid if $\mathcal{A}$ chooses arbitrary plaintexts $m_0$, $m_1$ from $\mathbb{P}$ or, otherwise, is it still necessary that $|m_0| = |m_1|$ for $m_0,m_1 \in \mathbb{P}$ holds?


texts: Proving that an encryption scheme is susceptible to certain attacks

texts:
I'm currently trying to prove the following:

Where p is a prime number of cryptographic size, prove that:

e(m) = am + b (mod p) where a and b are private is open to a known plaintext attack
e(m) = am + b (mod p) where a, b, and p are private is open to a known plaintext attack
e(m1,m2) = $
\left[
  \begin{array}{ c c }
     m1 & m2
  \end{array} \right]
$ $\left[
  \begin{array}{ c c }
     a & b \\
     c & d
  \end{array} \right]
$ +
$
\left[
  \begin{array}{ c c }
     e & f
  \end{array} \right]
$ mod p

where a,b,c,d,e,f are private and m1 and m2 are two parts of a message is open to a chosen plaintext attack.

I think I've figured out the answer for the first one (it's an affine cipher with variable values for the modulus instead of 26, if the adversary Eve has 2 samples of plaintext-ciphertext pairs then it's not too hard to prove that she can find the decryption function which allows her to decode the entire message).

I'm having trouble with the last two however. With the 2nd one, how will having a few samples of plaintext-ciphertext pairs help Eve find out p? With the 3rd one, I'm not seeing how her ability to choose particular plaintext and finding out their corresponding ciphertext helps her find out how to decrypt the message.

Any guidance would be highly appreciated.


texts:
As the full version of HMQV is very long, I will give a graph  of it below

\begin{array}{@{}l@{}c@{}l@{}}
\hat{A} && \hat{B} \\
(a,A=g^a)&&(b,B=g^b) \\
 x\in_R[1,q-1],\quad X=g^x  \\
& \xrightarrow{\textstyle \hat{A},\hat{B},X} \\
%&& verify \; X \in G^* \\
&& y\in_R [1,q-1],\quad Y=g^y \\
& \xleftarrow {\textstyle \hat{B},\hat{A},Y} \\
&& d=\bar{H}(X,\hat{B}), \quad e=\bar{H}(Y,\hat{A}) \\
&& s_B=y+eb,\quad \sigma_B=(XA^d)^{s_B} \\
&& K=H(\sigma_B) \\
%verify \; Y \in G^*\\
d=\bar{H}(X,\hat{B}), \quad e=\bar{H}(Y,\hat{A}) \\
s_A=x+da,\quad \sigma_A=(YB^e)^{s_A} \\
 K=H(\sigma_A) \\
\end{array}

$a$ and $A=g^a$ are static private key and public key of party $\hat{A}$ ($\hat{A}$ denote the identity of a user ) respectively ,and the same with  $\hat{B}$ .

HMQV appears in 2005, while the eCK model appears in 2007. After that , nobody try to prove the security of HMQV under eCK model, although,intuitively it's secure under eCK. So, I wonder that why  nobody give a proof of it ?  Could someone give a sketch of proving HMQV under eCK model?


texts: The sign of the correlation in linear approximation

texts: ${\text{Let }}g:{\{ 0,1\} ^n} \to {\{ 0,1\} ^n}$ be a round function of an $n$-bit iterated block cipher and let $K \in {\{ 0,1\} ^n}$ be a fixed round-key, and denote ${g_K}(x) = g(x \oplus K).$ Show that $${\text{cor}}(u \cdot x,v \cdot {g_K}(x)) = {( - 1)^{u \cdot K}}{\text{cor}}(u \cdot x,v \cdot g(x))$$


texts: Is there an open source with MIT license implementation of a CSPRNG with seeding written in C#?

texts: I need a CSPRNG written in C# that has seeding functionality but I can't find any implementation out there that seems legit. The only one I found is prangster but it has some requirements to be used. Does anyone know a good and free implementation?


texts:
From what I've looked up on various AES projects, the impression I get is the lookup table is hardcoded with the values from this Wikipedia entry page:

https://en.wikipedia.org/wiki/Rijndael_S-box

Am I correct in this assumption or is the lookup table on that page just for initialization and the table gets updated once further rounds are done in AES?


texts: Why does FIPS 186-4 seem to have an excessively complex q generation?

texts:
So in DSA you have two primes - p and q. q is N bits long (let's assume 160 bits) and p is L bits long (let's assume 1024 bits).

Here's what FIPS 186-4 says about generating the q parameter for DSA:

Get an arbitrary sequence of seedlen bits as the domain_parameter_seed.
U = Hash (domain_parameter_seed) mod 2$^{N-1}$.
q = 2$^{N-1}$ + U + 1 – ( U mod 2).
Test whether or not q is prime as specified in Appendix C.3.
If q is not a prime, then go to step 5.

outlen is the length of the Hash output, in bits, and seedlen is any number > N.

What I'm wondering is...  why not just replace steps 5, 6 and 7 with "get an arbitrary sequence of N bits as the q" and "make the least significant bit 1"?

2$^{N-1}$ gives you the lower bound on an N-sized variable.  U adds the trailing N bytes of Hash(domain_parameter_seed) to 2$^{N-1}$ and "1 - (U mod 2)" makes the final number odd. So it seems like a poor-man's randomPrime(n-bits) function call.


texts:
I'm studying the paper Fully Homomorphic Encryption over the Integers by Marten van Dijk, Craig Gentry, Shai Halevi and Vinod Vaikuntanathan.

I have questions about the proof of Lemma A.1.

In page 6, the element of public key is in the form of $x=pq+r$
and the encryption is
$$ c← [m+2r+2\sum x_i]_{x_0} $$

But in the proof of Lemma A.1., the public key is $x=pq+2r$
and the encryption is
$$ c← [m+2r+\sum x_i]_{x_0} $$

This problem made me confused.
I tried to proof with first definition, but I encounter with another problem.
When I follow the same flow of the proof with first definition,
I reached that the noise term is $$(m+2r+k*r_0+ \sum 2r_i )$$
What I need to next is to get the upper bound of a $|m+2r+k\cdot r_0+ \sum 2r_i|$.
So I got
$$|m+2r+k*r_0+ \sum 2r_i| \leq m+2\cdot2^{\rho\prime} + \tau \cdot 2^{\rho}+\tau \cdot 2^{\rho} =m+2\cdot2^{\rho\prime} +2 \tau2^{\rho}$$

If the definition of permitted circuit in this thesis is correct, at least
$$m+2\cdot2^{\rho\prime} +2 \tau2^{\rho} \leq 2^{\rho \prime +2}$$
should be satisfied.

Can anybody help to get upper bound of noise?

Original question

I'm reading https://eprint.iacr.org/2009/616.pdf

I am reading the proof of Lemma A.1 which is in page 21.

In the page 22, the thesis tells that the noise is at most $(4\tau + 3)2^\rho < \tau2^{
\rho+3}$.

But I cannot follow the inequality.

Could you guys help me to understand the proof of Lemma A.1?


texts: Deterministic encryption for a limited space: using HMAC as IV

texts:
I need a deterministic encryption scheme. Objectives:

Same plaintext is always encrypted to the same ciphertext.
Related plaintexts are encrypted to unrelated ciphertexts. (For example, attacker that knows two ciphertexts cannot learn whether corresponsing plaintexts start with the same prefix.)
Minimum space overhead.
Authenticated encryption, of course.

There are also some conditions that can make it easier:

I will encrypt small chunks of data (few dozens of bytes). It is OK to store them in RAM and then start the encryption.
The data will be padded to the same length all the time. So, we can conclude that the length of the data is some constant.
Not high performance requirements.

My first idea was to derive IV from plaintext using HMAC and then use some authenticated encryption that requires just unique (potentially predicable) IV, like AES-GCM. This requires both IV and authentication tag to be stored alongside the encryption.

But I have an idea how to reduce the space overhead even more: Use (H)MAC of plaintext as both IV and authentication of the message. I know this is generally dangerous scheme close to encrypt-and-mac, so I specify further requirements for primitives to mitigate its risks:

The encryption will not leak anything when decrypting attacker-manipulated data. Stream ciphers like AES-CTR look suitable here, because there are no risks related to padding oracle. It just “decrypts” any attacker-provided garbage to another garbage (rejected by MAC check later) without any side channel if the AES-CTR implementation is correct.
The encryption requires just unique IV, but it does not have any other requirements. Thill, AES-CTR looks suitable here.
The MAC does not leak any data. HMAC (potentially truncated to 128b) looks suitable there, because failing to do so would at least weaken preimage resistance of the underlying hash function.
Encryption uses a key completely unrelated to authentication key, of course. (This requirement might not be strictly needed when using, say, AES-CTR with HMAC-SHA256. However the requirement makes reasoning about security easier.)

The whole schema looks somewhat exotic to me, but I believe that I have resolved risks arising from the unusual design.

Is there any existing work that aims to do the same? Is there any research that would tell me anything about security of this scheme?


texts:
I am aware of basics of public key encryption algorithms , for eg. RSA.
If A wants to send a message to B, A uses the public key of B to encrypt the message A wants to send to B, and only B can decrypt the message using his private key.

What I don't understand is that what exactly is the digital signature, if for eg. A is sending an email to B? Is it the email id? The message that A wanted to send to B? IP address? Is it a random text or string? If it's random, how does B know it was A who sent it?


texts:
I'm developing application in Java that has to store RSA keys in software for foreseeable future (that is, at least 10 years).

The two most common standards of storing private keys are PKCS12 and JKS (Java Key Store). While PKCS12 supports many different algorithms, even the most secure ones are based on 3DES with SHA1. JKS is even worse as the default is based on MD5 and 3DES.

The Bouncy Castle Java library version of JKS is a bit better as it uses PBEWithSHAAndTwofish-CBC for "UBER" version of its key store format.

Are there any standard formats of private key storage that support encrypting the key pair using AES and SHA-2?


texts: How share size is reduced in robust secret sharing?

texts:
THIS IS ROBUST SECRET SHARING SCHEME

The dealer $\mathcal{D}$ wants to share a secret among the participants $\{P_1, P_2, \ldots, P_n\}$, where at most $t$ participants are malicious and $t<n/2$.
 For $i = 1, \ldots, n$, let the distinct elements  $\alpha_{i}\in\mathbb{F}_{2^q} \setminus \{0\}$ be fixed and public, where $q$ is positive integer such that the cardinality of the field $\mathbb{F}_{2^q}$ is larger than $n$.
The dealer $\mathcal{D}$ chooses randomly a polynomial $f(x)\in\mathbb{F}_{2^q}[X]$ of degree at most $t$, where $f(0) = s$ is the secret to be shared, and computes $f (\alpha_{i}) = s_i$ in $\mathbb{F}_{2^q}$, where $i = 1, \ldots, n$.
$\mathcal{D}$ chooses randomly $k_{i, j} = (\alpha_{i,j}, \beta_{i,j})$ from $\mathbb{F}_{2^q} \times \mathbb{F}_{2^q}$, and  computes $y_{i, j} = \alpha_{j,i} s_i + \beta_{j, i}$, where $j = 1, 2, \ldots, n$ and $i = 1, \ldots, n$.
$\mathcal{D}$ privately sends to each $P_i$ the share
$$ S_i = (s_i, y_{i,1}, \ldots, y_{i, n},  k_{1, i}, \ldots, \ldots, k_{n, i}).$$
 Reconstruction Phase:
Round 1: Each $P_i$ sends $(s'_i, y'_{i,1}, \ldots, y'_{i, n})$ to the reconstructor $\mathcal{R}$.
 Round 2: Each $P_i$ sends $(k'_{i, 1}, \ldots, k'_{i, n})$ to the reconstructor $\mathcal{R}$.
 Computation by $\mathcal{R}$:
$\mathcal{R}$ sets $v_{ij}$, $i, j \in \{1,2, \ldots, n\}$, to be $1$ if $P_i$'s authentication tag is accepted by $P_j$, i.e., if
$y'_{i, j} = \alpha'_{j,i} s'_i + \beta'_{j, i}$; otherwise she sets $v_{ij}$ to $0$.

\item $\mathcal{R}$ computes the set $\mathcal{I} \subseteq \{1,2, \ldots, n\}$ with the property that
$$\forall i \in \mathcal{I}: |\{j \in \{1,2, \ldots, n\} | v_{ij} = 1\}| = \Sigma_{j \in \{1,2, \ldots, n\}} v_{ij} \geq t+1.$$

Clearly, $\mathcal{I}$ contains all honest participants.

Using Lagrange's interpolation method, $\mathcal{R}$ computes a polynomial $f(x) \in \mathbb{F}_{2^q}[X]$ of degree at most $t$ such that $f(\alpha_i) = s'_i$ for at least $(t + 1)$ participants $i$ in $\mathcal{I}$.
If no such polynomial exists then output $\perp$,
otherwise, output $s = f(0)$.

NOW IN ROBUST SECRET SHARING SCHEME WITH REDUCED SHARE SIZE WHAT WE CHANGE IS THE FIELD OF KEY SPACE

$\mathcal{D}$ chooses randomly $k_{i, j} = (\alpha_{i,j}, \beta_{i,j})$ from $\mathbb{F}_{2^m} \times \mathbb{F}_{2^m}$, and  computes $y_{i, j} = \alpha_{j,i} s_i + \beta_{j, i}$, where $j = 1, 2, \ldots, n$ and $i = 1, \ldots, n$. Where $\mathbb{F}_{2^m}$ is larger than $n$. And $q$and $m$ are different.

Now i dont understand how share is reduced?


texts:
Is there any TRUE public key cipher beside RSA? Most people would answer Elgamal or ECC, but for what is my understanding (and I know cryptography only superficially), those are not true asymmetric ciphers (because both parties can encrypt and decrypy).

EDIT:

I realized that my question needed better explaining.

The following quote is from the Handbook of Applied Cryptography:

  Definition 1.50: Consider an encryption scheme consisting of the sets of encryption and decryption transformations $\{E_e : e ∈ K\}$ and $\{D_d : d ∈ K\}$, respectively. The encryption method is said to be a public-key encryption scheme if for each associated encryption/decryption
  pair $(e, d)$, one key $e$ (the public key) is made publicly available, while the other $d$ (the private key) is kept secret. For the scheme to be secure, it must be computationally infeasible to compute $d$ from $e$.

Now take for instance Elgamal encryption. Bob chooses the parameters, then sends the public key to Alice, Alice computes the mask $K_M$ (the session key) and the ephemeral key $K_E$, encrypts the message $M$ with $K_M$ obtaining $C$, and sends ($C$,$K_E$) to Bob. Bob can compute $K_M$ using $K_E$ and his private key. The quoted definition is not satisfied. Alice and Bob, in the end, both have $K_M$ which is used for encryption and decryption.

EDIT2:

The reply I got from fgrieu was very satisfying, I was mistaking a shared secret key for a public key. However this made me reflect on another difference between an Elgamal scheme and an RSA scheme. I'm going start with another quote from HAC (Basic Terminology, p.12):

  An encryption scheme consists of a set ${E_e : e ∈ K}$ of encryption transformations and a corresponding set ${D_d : d ∈ K}$ of decryption transformations with the property that for each $e ∈ K$ there is a unique key $d ∈ K$ such that $D_d = E_e^{−1}$; that is, $D_d(E_e(m)) = m$ for all $m ∈ M$. An encryption scheme is sometimes referred to as a cipher.

With this, Elgamal randomized E is not acceptable, because a randomized function can't be the left inverse of another function. Se we can heve $D_d(E_e(m)) = m$ for all $m ∈ M$, but we can't have $D_d = E_e^{−1}$. This is also the reason (I think) why Elgamal cipher can't be usued for digital signatures (Elgamal DS is different from the cipher).

Now my question: is the second quoted definition correct? Or $D_d = E_e^{−1}$ should be "$D_d$ is a left inverse of $E_e$"? Also unicity of $d$ is really necessary?


texts: Key material leak from initialized cipher?

texts:
Let's imagine that cipher (say AES256 in CBC mode) is initialized when application starts:

C = cipher.Create
K = kdf(password, iterations, salt)
C.Initialize(K, iv)
burn(K)

At this point I have initialized cipher C. Key K is burned. Cipher C will be used to encrypt/decrypt data on demand (data source is encrypted file).

If I plan to keep instance of initialized cipher C in memory for lifetime of my running application, can I assume the key material from inside initialized cipher can be captured (memory dump etc) and re-used by attacker? Or in other words, is keeping initialized cipher in memory basically equal to keeping key in memory? If so, what can be done to avoid this kind of leak?


texts: Why do we apply the concept of circuit in homomorphic encryption schemes?

texts:
I am a beginner to the concept of homomorphic encryption. One thing that makes me very confused is why we use the circuit concept or approach to homomorphic encryption. Gentry's paper does not discuss it in detail. Are there any papers or books could make me have a better understanding of it?

(I mean the circuits part.)


texts: CPA-security of a pseudorandom permutation encryption scheme

texts:
Let $F$ be a pseudorandom permutation, and define a fixed-length
  encryption scheme $(Gen, Enc, Dec)$ as follows: on input $m \in$
  $\{0,1\}^{n/2}$ and key $k \in \{0,1\}^n$, algorithm $Enc$ chooses a
  random string $r \leftarrow \{0,1\}^{n/2}$ of length $n/2$ and
  computes $c = F_k(r||m)$. Show how to decrypt, and prove that this
  scheme is CPA-secure for messages of length $n/2$.

I see the decryption could be $d = F_k^{-1}(c) = r||m \Rightarrow r_0r_1 ... r_{n/2-1} m_0m_1 ... m_{n/2-1}$, assuming $n$ is even the receiver knows that he must extract $m$ from the first exact half (from right to left) in the ciphertext sequence. As for the CPA-security, I notice that $F_k$ is non deterministic because of $r$, so for a message $m$ the 2 ciphertexts $c = F_k(r||m)$ and $c' = F_k(r'||m)$ are different if $r \neq r'$. Let $q(n)$ be a polynomial number of oracle queries, then $r = r'$ with probability $$\frac{q(n)}{2^{n/2}}$$ which should be negligible.
Is that correct? And should I say something about the security parameter $n$? I feel I'm missing something here.


texts: Please explain me why we require $2^m$ & $2^{\frac{m}{2}}$ random messages

texts:
Assume that a one-way Hash function is secure and the best way to attack it is by using the brute force attack. It produces an $m$-bit output. Finding a message that hashes to a given hash value would require hashing $2^m$ random messages. Finding two messages that hash to the same value would only require hashing $2^{\frac{m}{2}}$ random messages.

I know only about birthday paradox involving 23 people. How do I relate the birthday paradox with this attack?


texts:
One of the most (in)famous hardware derived random number generators was Lavarand (patent).  It did it with funky lava lamps.  An image of the lamps was hashed and fed into Blum Blum Shub (BBS) to produce a cryptographic bit stream.

How?  The patent refers to using NIST SHS-1 (SHA-1) which outputs a 160 bit hash.  This seems to get reduced to multiple 140 bit hashes and then "The 140-byte value gets fed through the Blum Blum Shub[sic]".  I thought that the seed for BBS was computed via prime multiplication.  How can the seed (typically p.q) just be arbitrary hash output and still perform it's  integer factorisation?  BBS typically utilises a single state of 1000s of bits, not groups of 140.  They did it like this which is a little lite on detail, and steps 3 & 4 from the archived web site don't clear it up any...

I realise that this was all a long time ago.  How can above steps 600 and 605 be connected together?


texts:
I am having a task where I have to evaluate a commitment scheme. I checked already a few questions here, but they have not helped me :( I hope someone is able to help me out in that.

What do I have?

$commit_H$ - perfectly hiding and computationally binding

$commit_B$ - perfectly binding and computationally hiding

Here is $commit_1(m)$ step-by-step.

$commit_1(m)$:

compute $(c_H, d_h) := commit_H(m)$
compute $(c_B, d_B) := commit_B(c_H)$
output $(c_B, (d_B, d_H))$

The first question is if this is a commitment scheme. My answer would be yes, because we have a commitment ($c_B$) and open values $(d_B, d_H)$.

How to open the commitment? $open(open(c_B, d_B), d_H)$

I hope this is correct so far. Now comes the part where I have no clue. I have to decide what type of commitment it is. Is it type B (perfectly binding) or type H (perfectly hiding).

My first thought was that it is perfectly binding. In order to proof this, I am using contradiction.

Contradiction: There exists an algorithm A, such that

$((x_1),(x_2)) \leftarrow A(1^n) ~~(x_1 \neq x_2)$

$commit(x_1) = commit(x_2)$

$commit_B(commit_H(x_1)) = commit_B(commit_H(x_2))$

$commit_B(c_{H1}) = commit_B(c_{H2})$

This would be a contradiction, because $commit_B$ is perfectly binding.

The next step would be to show that it is not perfectly hiding, because my though is that it is type B.

This is where I am stuck. $commit_B$ is not perfectly hiding, which means that an computationally unbound attacker would be able to decommit the first part ($commit_B(c_H)$), but would be stuck at the second part ($commit(m)$), because it is perfectly hiding.

My question would be, what am I doing wrong? Did I misunderstood something? Could someone help me out?

Thanks

Edit: Thanks to the answer from poncho, I get the following solution. It is not completed yet, since I fell unsure about it. Would be nice if someone or even poncho could correct if necessary.

The commitment scheme $commit_1(m)$ is of type $H$. This means, it would be perfectly hiding and computationally binding.

There are 3 things I want to show:

Perfectly hiding
Computationally binding
Not perfectly binding

I would like to start with number 3 - not perfectly binding.

$commit_H$ is not perfectly binding, which means that $\exists m_1, m_2; m_1 \neq m_2$ such that

$c_{H1}=commit_H(m_1)=commit_H(m_2)=c_{H2}$.

$\implies commit_B(c_{H1}) = commit(c_{H2})$

Even $commit_B$ is perfectly binding, after opening $c_B$ it would be possible to open $c_H$ to either $m_1$ or $m_2$ (given unbounded computation) (Thanks poncho).

Next, I would like to show perfectly hiding. I used therefore a game, where an Attacker sends $m_1$ and $m_2$ to $commit_B$ and this is send to $commit_H$. Here is the game I had been thinking of:

We have an unbounded attacker $A$ with an advantage of $\epsilon(n)$.

The probability to win this game is:

$Pr[b=b'] = Pr[Challenger_H(n)=1] = Pr[Challenger_B(n)=b]$ since he passes the messages $m_0$ and $m_1$ without altering them.

$Pr[b=b'] = Pr[Challenger_H(n)=1] = Pr[Challenger_B(n)=b] = Pr[A(n)=b]$.

Since $commit_H$ is perfectly hiding, we get the following equation:

$\frac{1}{2} = Pr[A(n)=b] = \frac{1}{2} + \epsilon(n)$
$\Rightarrow \epsilon = 0$ otherwise it would be a contradiction.

The last thing (can I call it property?) to proof is computationally binding. I am not sure yet how to do that. I am thinking to prove it with computationally and statistically indistinguishability. I will crack me head later on that one too.


texts: Could we use a more efficient hash for signature generation?

texts:
Is it possible to use a more efficient hash - such as one based on GHASH - instead of a cryptographic hash for signature generation?

In other words, could a combination of a fast hash and the private key operation together provide the security that we expect from a cryptographic hash? Could such a scheme be proven to be secure assuming that the underlying primitives are secure?


texts: What is the difference between RSASSA-PSS signing and RSA-PSS signing?

texts:
I read the RFC 8017 and understood the pkcsv1.5 and pss padding techniques. I understood that in RSASSA-PSS signing scheme the signature will be appended at the end of M.

In some websites I read both RSASSA-PSS and RSA-PSS both are same, is it true? If not what is the fundamental difference between RSASSA-PSS and RSA-PSS, can you also please provide me the API's to sign and verify using  OpenSSL for RSASSA-PSS.

Thank You.


texts:
I was wondering if interleaving the resulting crypted data with dummy bytes placed at random positions but known in advance by the peers could improve security (no matter the algorithm and strength used, this is just baby step theory here) or do the contrary (and why).
E.g.:
normal: kIolmspJgheydhNud
with dummies: kI9oklmdspJgfheydshNufd
Update:
after Thomas answer, I realized that my question was not clear where the dummy bytes would go.
My mistake.
So I am interested in adding dummies in the ciphertext. After all encryption of the real text occurred. The net result is to make the ciphertext longer and not logical anymore.


texts: Why VDFs need to be "quickly" verifiable?

texts:
I am very new to the topic, I found it out only today afternoon, so forgive the dumbness of the question should that be the case.
I have tried to grasp the rationale of Verifiable Delayed Functions (whatched all the videos, read all articles), used in many blockchain-related applications. I understand that the 2 properties that the functions need to fulfil are the following:

Sequential: you cannot know the output until you first executed all the necessary steps
Efficiently verifiable: after the function has been computed on an input x, it should be fast to verify that the output y came from executing the VDF on x

Now, the part I don't get is: why should it be efficient? Taking for instance the example of the Random Beacon use case:

A,B,C,D,E submit a random value
A random beacon has to be derived from this random value
We need to avoid that E can manipulate the output of the random value by means of its input, brute-forcing the desired output with many inputs with its incredible parallel CPU power

If a VDF that is not efficient is used, wouldn't the conditions still be met?

A,B,C,D,E submit random value
E needs 1 hour to calculate each single output sequentially, so it cannot really brute force anything
Meantime the random beacon is calculated and broadcasted
Whoever needs to use it, will take another hour to verify it. Annoying, but still feasible.

I understand that this makes everything extremely slow, but is that the only reason to have the efficiency as a hard requirement? Or are there motivations such that the applications would be actually impaired/unsecure? I bet it's the second one, but why?


texts: Have crypto side-channel attacks happened in the wild?

texts:
I'm aware of attacks extracting information via timing and volume. But none that care or attack the actual cryptographic algorithm implementation or end up extracting the key.
Seeking examples if any for such attacks which happened outside the lab, Or evidence where we suspect this was the means of attack used.
Any side channel: timing, sound, power, something else?


texts: Can universal hashing functions be (ab)used as stream ciphers?

texts:
These days, universal hashing functions like GHASH and Poly1305 are very trendy because of their simplicity and speed.

Now during a discussion related to export restrictions, it came up that mainly encryption techniques are regulated and these hashing functions wouldn't be hit by this.

Now to the question:
Can you run a universal hashing function in CTR mode to get a secure stream cipher?


texts: How close to pure math is cryptographic theory?

texts: I'm an undergraduate math student, and I'm thinking about topics for an undergraduate thesis. I have an interest in topological spaces and number theory, but I'm having trouble identifying a relationship between those and cryptographic theory. In On Post-Modern Cryptography, Goldreich talks a lot about rigorous analysis. But it's still not giving me a clear understanding of what type of math a person doing research in theory does in general. Is cryptographic research in the same line as formal mathematical proof? Is there a need for abstract mathematics in modern cryptography? I can program, but application is not really my interest and it would take too long in my degree to add a formal computer science aspect.


texts:
It's well known that by injecting a byte fault during the 8th round of AES 128 just before the mix column the  key can be recovered with $2^{32}$-key space. A brute force attack is then possible but it takes some time.

If instead a byte fault, it is just a bit flip does it reduce the key space for K10? And  why?

In fact I was wondering if there is a kind of propagation of a 1 bit diff between the 8th round and 9th round that could reduce the key space for K10


texts: So I am doing a CTF and I have found a text that is full with hexadecimal encrypted value with XOR (that was a given hint from the previous flag). I don't have the key but I know the length of the key is $8$. I also know that the word Congratulations is in the file somewhere. So, I guessed that if I XORed Congratu with the first 16 hex bytes assuming that I'll recover the key as a result to fully decrypt the message but that didn't seem to give me a correct result. I'm guessing that Congratulations may not be the first, which is why I'm having this issue. Is there anything that you guys recommend to solve this quickly?


texts: Bitwise operation question with shifting involved

texts:
I am trying to find a value of X (32 bits) such that ((X XOR a)+b)<<3 = (X+c) XOR d. <<3 means shift left 3 bits. a,b,c and d are all constants which have been determined elsewhere.

However, I don't want to brute force the full 2^32 combinations. I was told solving it 3 bits by 3 bits from the MSB on the left hand side would help however this feels off to me.

Say I fix the first 3 MSB. This with the left shift that means that the 3 LSB will be fixed, leading to the next 3 bits and so on. It seems to me that fixing any 3 straight bits will end up with all of X being solved. Are 8 tries really all I need to solve this equation?

There's also the possibility that the values of a,b,c and d at the time might create an unsolvable equation too. If I don't find it within the 8 (or more tries if my above paragraph is wrong) it's safe to ditch this and try new values of a,b,c,d right?


texts: In the paper for curve25519 is described how the prime was chosen. But I don't understand why the biggest 255-Bit prime was chosen instead of a 256 Bit prime. Can someone explain this to me?


texts: I want to get a group element $h$ on the elliptic curve secp256k1. The important thing is that no one should know the discrete logarithm of $h$ with respect to $g$. That is, $h$ should be created from a public beacon and not by exponentiating $g$. What's the best way to do this?


texts:
When I put:

sudo watch tail /proc/sys/kernel/random/entropy_avail && dd if=/dev/random of=/dev/zero

It shows that available entropy is "consumed".

What I can't understand is:

Why does generating random consume entropy? Why does generating random bits cause that entropy to become useless?


texts:
I am trying to understand the Lucifer cipher and I cant find any clear understandable example of the cipher.

Can anyone please provide me with a step-by-step example of an encryption using the Lucifer cipher?
Can you describe the relation between Lucifer cipher and Feistel
Networks?
Can you please provide references and links for further reading?


texts: how to understand the universal hash and the leftover hash lemma

texts: I always meet the leftover hash lemma when I read some papers.But I only know the defination of  universal hash and the leftover hash lemma.How to understand them and how to use them?


texts: How can salted passwords work if you don't "keep the salts in the system"?

texts:
In this report on the recent ParkMobile breach, the article has this comment from the company:

“You are correct that bcrypt hashed and salted passwords were obtained,” Perkins said when asked about the screenshot in the database sales thread.
“Note, we do not keep the salt values in our system,” he said.

If they don't "keep the salt values in [their] system", how could they match a user-entered password to match their hashed and salted versions?


texts:
I've been tasked with building up some security exercises (basic CTF training kind of stuff) for work. This should contain a bit of crypto, but my knowledge in this space has been limited to using the right tools, not trying to roll my own, etc, so coming up with an example of bad crypto, but believably real, has been tough.

Specifically one of the flags would be encrypted, say a simple sentence, in a way that would be crackable, allowing for recovery of the plaintext with a bit of know how and some burned cpu.

Could someone point me to an example like that?

Thanks for any input.


texts: RSA signing - does EMSA-PKCS1-v1_5 padding need to be verified?

texts:
I am working with an embedded system that accepts firmware updates only if they are validly signed by a particular 2048-bit RSA private key (the embedded system's bootloader knows the corresponding public key).

On the publishing side, the signature is generated by:

computing the SHA-256 hash of the firmware image
padding it according to EMSA-PKCS1-v1_5 (which involves prepending a fixed 1792-bit string)
signing the concatenated 2048-bit value by exponentiation with the RSA private key

On the embedded side, the signature is verified by:

independently (re-)computing the SHA-256 hash of the received firmware image
recovering the concatenated 2048-bit value from the signature by exponentiation with the RSA public key
verifying that the first 1792 bits of the value exactly match the expected padding string
verifying that the last 256 bits of the value (i.e. the SHA-256 hash computed on the publishing system) exactly match the hash computed on the embedded system

So, the question:

Is step #3 (verifying the EMSA-PKCS1-v1_5 padding) important to the security of the system?

(This is a theoretically-motivated question; I want to educate myself.  It's not a significant added cost on the embedded side to verify the padding.)

P.S. I've attempted to search for existing questions/answers already, and Attacking RSA signature verification that ignores padding is very close.  In that case though, I gather that the implementation basically searched the entire recovered 2048-bit value for a substring matching the recomputed SHA-256 hash; and the possibility of having garbage data after the hash specifically made attacks like this Kindle HDX hack possible.

In this case I'm specifically wondering whether it's a bad idea to simply ignore/remove the first 1792 bits (assumed to be the padding) and only compare the last 256 bits to the expected hash.  Does that open the possibility for the same type of attack?  Or for different attacks?


texts: Are deterministic adversaries as powerful as probabilistic adversaries?

texts:
SOURCE states the following in the proof of Theorem 2:

  Without loss of generality, I will assume that A is deterministic. If A is randomized, we can determinize it by fixing a sequence of coins that maximizes A’s conditional success probability; it is easy to see that this cannot reduce A’s advantage.

Is this correct? Does it mean that we do not need to consider probabilistic adversaries in cryptographic security games?


texts: Mitigating leakage of asymmetric encryption scheme leaking the length of plaintext

texts:
Asymmetric encryption schemes do leak something about the encrypted plaintext: the length of the plaintext. How can this be mitigated?

My solution: Padding the plaintext with some string of the arbitrary length – add 1 and then a string of zeros

What are some other ways this information leak can be mitigated?


texts:
Below is the cipher text I am trying to break and as you can see its rather short which is why I am having so much trouble.

WOYFN ZCMSH VUVTG BFUTW ABTZP FHIMF TFOSU UXFQC HKVKG MPUUQ
MHRXI OVBRZ EPJYF KKVJW GEIOV HUKEB JUNSM THIMF TFKUB ULMMQX

What I know about this ciphertext:

Key is 6 characters long and repeats (Given by the person who encrypted it)
There is a single character missing from the start of the ciphertext! (Also given)
It uses a simple cipher I believe a vigenere cipher.
Friedman IC: 1.143 (kappa-plaintext: 0.4396) which is why i think its a vigenere cipher

I have spent many hours on this but to be honest im not very good at breaking these codes.

My problem that iv run into is that once I break the cipher into its sections they are all very short and hence frequency alaysis fails.

I would really appreciate if someone could either confirm or find the crypto system being used as well as any more information about how one would find the plaintext + key or better yet find the key itself and explain how you manage it with such a short piece of ciphertext

Edit: There was some debate as to the validity of this question so here is some more information from my attempts:

Streams:

?ZUUZFUKUXZKEKSFU IC = 3.6833 (kappa-plaintext: 1.4167)
WCVTPTXVUIEKIEMTL IC = 1.1471 (kappa-plaintext: 0.4412)
OMTWFFFKQOPVOBTFM IC = 2.1029 (kappa-plaintext: 0.8088)
YSGAHOQGMVJJVJHKM IC = 1.3382 (kappa-plaintext: 0.5147)
FHBBISCMHBYWHUIUQ IC = 1.5294 (kappa-plaintext: 0.5882)
NVFTMUHPRRFGUNMBX IC = 0.9559 (kappa-plaintext: 0.3676)

These numbers don't look good. they are almost all drastically off normal distribution for any language.

The main point to my question is:

Does Vigenere Seem like a reasonable fit (given those streams are correct)?
Is it possible to use that analysis in any way? I cant see how it can be effective with only 17 characters per stream. Most letters frequencies are 0.
What other ciphers are possible? How could I identify that they are in use?

I am happy to provide more information I am just not sure what else is useful.


texts: Is there an asymmetric algorithm that can perform double encryption?

texts:
I'm looking for any asymmetric algorithm can perform the serial encryption, by serial I mean double or more encryption with different key (same key size). RSA can not do it since the cipher of the first encryption is to long to perform an other encryption with the same key length.

For example (from Yao, Yang & Xiong 2015):

  We use $C = {\{ m\} _y}$ to denote encryption of a plaintext $m$ with a public key $y$. In addition, we use ${\{ m\} _{{y_{1}}:{y_{N}}}}$ to denote a serial of encryptions under multiple public keys, i.e., \begin{equation}{\{ m\} _{{y_1}:{y_{N}}}} = {\{ \ldots{\{ {\{ m\} _{{y_N}}}\} _{{y_{N - 1}}}}\ldots\} _{{y_1}}}.\end{equation}


texts: Decryption formula of Plaintext Block Chaining (PBC) mode of a block cipher

texts:
Considering that $C_n = E_k(M_n) \oplus M_{n-1}$ formula is used in encryption side of this mode of block cipher, and knowing that instead of M0 a randomly chosen initialization vector (IV) is used in Plaintext Block Chaining mode.
What would be the formula on the decryption side?

$M_n = D_k(C_n) \oplus M_{n-1}$

$M_n = D_k(C_n \oplus M_{n-1})$

Actually, I think as the algorithm has no access to $M$ bits on the decryption side, although I accept that by following $M$ bits, I will get to $M_0$ at the end which is IV and can solve the equations inversely from that point, it would be better to write the above equations as :

$M_n = D_k(C_n) \oplus D_k(C_{n-1})$

$M_n = D_k(C_n \oplus D_k(C_{n-1}))$

But my main question is which of the equation is correct if we want to represent the decryption side's formula?


texts:
What we want?

Encrypt plaintext with ChaCha20 + ECC on curve 25519 (hybrid cryptography) the result would be a data stracture X.

Input: public key on Curve 25519

No authentication required (no AEAD)

What is the minimal storage ovehead of producing a data stracture X as compared to the plaintext.
What are the required steps, and what are the elements of X.

The resulting data structure X should be decryptable by requiring only the corresponding private key.

If we were to cut on storage ovehead even further, at the cost of security (change curve Curve 25519 to something else? idea?)


texts:
The great thing about public key cryptography is that anyone can generate a keypair, keep the private key secret and publish the public key anywhere they want.  This is used in CAs where an administrator presents a CSR containing a public key and gets a certificate back with the same public key signed.  It's also used by Github to allow users to do Git operations via SSH.

Both asymmetric keys and passwords can thus used as a credential.  There's a lot written about best practices for passwords, but I was wondering if there are also similar best practices for asymmetric keys?  Length is a factor of course (the internet tells me that my RSA key should be at least 2048 bits and that my ed25519 key should be at least 256 bits).  Still, even when a key has the correct length, it may be generated by a bad random generator (Debian key).

Do (should) services where the customer has to provide a public key, check this public key for weaknesses? What kind of weaknesses could a key be tested for?  How would you test for these?

Some tests that I think might be useful:

The bit length is appropriate for the algorithm the key is used for (best practices?)
The key is not a known compromised key (public databases?)
The key is not generated using a bad random generator (how would you test this?)


texts: Concrete examples / tutorials of how blockchain/bitcoin works

texts:
I want to understand the crypto details behind the blockchain (at least in the form that bitcoin implements it).

Can you point me to some page or documents that show the details with examples?

I read the Wikipedia page on Blockchain, and it's sort of: I understand everything that I read, but at the end, I'm clueless about how it actually works. (I understand the characteristics of the blockchain/bitcoin mechanism, and I can see how the hashes and the PoW and the Merkle tree are related to accomplishing those characteristics, but no more than that)

I read the Original paper by Nakamoto, and for the most part, I perfectly understand each of the things it says (however, see below). Yet, at the end I'm back to being clueless about how does it actually work.

I think what I need is to see some concrete examples showing the actual detailed structure of things, and also some examples of concrete attacks that would be possible if a particular feature was missing.

Some of the concrete doubts/questions I have are:

What is the nonce and how do we generate them?  (maybe rephrasing: does the nonce represent something specific?)
How does the individual node prove its work?  I perfectly understand everything that §4 of Nakamoto's paper says --- the problem is that it does not say (at least not that I can see/understand) how those principles are incorporated in bitcoin. §4 talks about incrementing a nonce until meeting the constraint (e.g., the hash starting with a given number of zeros). Is that the same nonce shown in the diagram?  If so, how does one know that that nonce was generated honestly and not reused (maybe not reusing the exact same value, but perhaps a value derived from some past value that speeds-up the PoW)?
I guess I'm not too clear on the notion of the "accumulated work" in a chain --- is it just that each block by itself represents a certain amount of work $w$, and a chain of $N$ nodes simply represents $N\times w$ work?
Using a separate key pair for each transaction; though I can see how that addresses the issue of linking different transactions to a same user, if you just randomly generate a different key-pair for each transaction, then what's the point of signing a transaction?  What are you proving by it?  (the usual notion of digital signatures is that you publicize a verification key along with its associated identity --- even if the identity is given by a pseudonym).  I guess for that matter, I'm not too clear on what the role of the digital signature is in the blocks; the idea is anonymous transactions, and the "chained hashing" provides authenticity and tamper-proof (thus, non-repudiation).


texts: when to do elgamal exponentiation computation

texts:
Recetly while studying about cryptographic primtives, I have come across below line in wiki : http://en.wikipedia.org/wiki/ElGamal_encryption

  Encryption under ElGamal requires two exponentiations; however, these exponentiations are independent of the message and can be computed ahead of time if need be.

Does "if need be" in the sentence refering to a static key? or is he saying that we can compute an ephemeral key prior to encryption and send to receiver, then later send the encrypted ciphertext at some other time.
If he is not refering to ephemeral key, I still want to know, are there any times we can really implement such a process using ephemeral.


texts: When using HMAC, does key encoding matter?

texts:
Given:

H is a good hash function with block size L.
K is a key of length >= L (recommended by RFC 2104).
Khex and Kbase64 are ASCII encodings of K.

In the HMAC algorithm, is there a good reason to prefer K over the other encodings?

Obviously the HMAC algorithm would consider these distinct keys of different lengths, and keys over length L are hashed, but the way HMAC works I don't see why using K would increase the security of the MAC.


texts: Difference between special honest verifier zero-knowledge and zero-knowledge property

texts:
Special honest verifier zero-knowledge and zero-knowledge property is defined as follows:

Special honest verifier zero-knowledge(SHVZK):There exists a polynomial-time simulator M, which on input x and a random t, outputs an accepting conversation of the form $(m_1,t,m_2)$, with the same probability distribution as conversations between the honest $(P,V)$ on input $x$

Zero-knowledge property(ZK): Let $(P,V)$ be an interactive proof system for some language L . We say that (P,V) is computational zero-knowledge if for every probabilistic polynomial-time interactive machine $V^*$, there exists a probabilistic polynomial-time algorithm $M^*$ such that the output of the interactive machine $V^*$ after it interacts with the interactive machine P on common input x is computationally indistinguishable from the output of machine $M^*$ on input x.

Assume, there exists a interactive-protocol $\pi$ for language $L$ which  is three move protocol that satisfies zero-knowledge property

Considering $\pi$, the difference between SHVZK AND ZK is Simulator is constructed for only honest verifier in SVZK, whereas in ZK simulator must constructed for even cheating verifier.

Can we say $\pi$ satifies SHVZK?. My doubt is
In SHVZK, simulator produces accepting transcript where as in ZK property there is no condition about acceptance of transcript generated by simulator.


texts: Why are cryptographically secure hashes required for digital signing (RSA or DSA)?

texts:
I know that a cryptographically secure hashing algorithm is required for proper message signing (SHA-1, or I think SHA-2 is the current suggested algorithm). However, why does the hashing algorithm necessarily need to be "strong"?

Seeing as the hashing is done before encryption/signature calculation, wouldn't an attacker need to first have the private key of the signer before being able to cause any damage? What sort of vulnerabilities do we open ourselves up to when we use weak hashing algorithms in DSS?


texts: How to encrypt many files with AES-GCM, without running the key derivation function each time?

texts:
Linked question: AES encrypting multiple files

With a password, I have 100k files to encrypt. (Maybe 100k files today; or maybe 50k today, 10k tomorrow, and 40k files the next week).

Up to now, I did this (pseudo-code):
for each file:
    plaintext = file.read()
    nonce = getrandom(bytes=16)
    key = KDF_PBKDF2(password, salt=nonce, count=1000000)  # very slow for each file!
    ciphertext, tag = AES_GCM_cipher(key, nonce=nonce).encrypt(plaintext)
    write to disk:   nonce | ciphertext | tag

and to decrypt the encrypted file
nonce, ciphertext, tag = file.read()
key = KDF_PBKDF2(password, salt=nonce, count=1000000)    # very slow for each file!
plaintext = AES_GCM_cipher(key, nonce=nonce).decrypt(ciphertext)

Obviously, this is not optimal, since I run the KDF function for each file, and this is slow!

I thought about this solution:
# do this ONLY ONCE for each encryption session:
salt = getrandom(bytes=16)
key = KDF_PBKDF2(password, salt=salt, count=1000000)   # run only once

for each file:
    plaintext = file.read()
    nonce = getrandom(bytes=16)
    ciphertext, tag = AES_GCM_cipher(key, nonce=nonce).encrypt(plaintext)
    write to disk:   salt | nonce | ciphertext | tag

but this has the drawback of having to prepend 16 more bytes (salt) at the beginning of each encrypted file. Is it a common practice?
And above all it has the following drawback when decrypting:
for each encrypted file:
    salt, nonce, ciphertext, tag = file.read()           # since salt may be different for each file
                                                         # we have to run:
    key = KDF_PBKDF2(password, salt=salt, count=1000000) # very slow for each file!
    ...

Since salt is on the beginning of each encrypted file, this means we have to run the KDF function ... for each encrypted file that we want to decrypt! This will be very slow.
We could put them in cache cache[salt] = key, such that if we find the same salt again, we already have the key, but I'm not sure if this is an elegant solution.

Question: which scheme to use to encrypt 100k files (in one pass, or in multiple sessions) with a password with AES-GCM?


texts: How can I do minus on plaintexts in the Paillier cryptosystem?

texts:
We have $E(a)$, $E(b)$ encrypted under the same Paillier key.

As we all know, we can get $E(a+b)$ by calculating $E(a)*E(b)$.

But can we get $E(a-b)$, by calculating $E(a)/E(b)$?

I tried to calculate $E(a)/E(b)$ by using the mpz_divexact function in the GMP library. But I cannot get the correct result.


texts: Words in “index of coincidence” in relation to the Vigenère cipher

texts:
I am trying to interpret the formula for index of coincidence from here…

I am not understanding $f_i$. How can I calculate $f_i$ in this context? Is this the appearance of single word like (a) in the whole sentence or what ? I am trying to solve it manually without using the mentioned website tool, but I am getting the wrong answer.


texts: Side channel attack: Why building an eviction set is possible?

texts: I'm learning about the side channel attack on the cache. I came to know that most of the attack (EVICT + TIME, PRIME + PROBE, PRIME + ABORT) on the cache is initiated by building an eviction set(a group of virtual addresses that map to the same cache sets) from the page table. And I also came to know that this is possible because multiple processes share the same CPU cache. So, my question is, just because of multiple processes sharing the same cache it is possible to build an eviction set from them or there is more to it?


texts:
I am writing a high-school paper on textbook RSA (the mathematical aspect only). Many definitions of the RSA method start off with saying that one should:

Generate two large random (and distinct) primes p and q, each roughly the same size
(http://cacr.uwaterloo.ca/hac/about/chap8.pdf, page 286)

My question is: what does 'large' imply? How many digits - is there a 'limit' to the amount of digits for an suitable prime? In some books they talk about 'bits' and 'strings': I still do not understand what they mean. Please clarify.
Another question: What does distinct mean? What does it imply.
Thank you in advance


texts: I want to calculate a random number (1 to 6) from the output of sha256. Can I assurance the probability of 6 abilities is the same?


texts: Are there any protocols that are truly secure from active and passive MITM attacks?

texts:
Are there are any cryptographic protocols or algorithms that can prevent active MITM attacks or interference when initiating a new connection to a server or someone you have not exchange keys with before?

For example:

Alice's computer ➜ ISP ➜ Internet ➜ ISP ➜ Bob's server

It is known that ISPs are compromised with secret rooms and equipment in use by the NSA/GCHQ especially in USA and UK. New Zealand feeling left out of the spying debacle decided to follow suit in the last few days and they just passed a law forcing ISPs to assist the GCSB in surveillance.

The chain is now really this:

Alice's machine ➜ ISP (hostile) ➜ Internet (hostile) ➜ ISP (hostile) ➜ Bob's machine

Assume either of the ISPs have some device or person which can do an active MITM attack in real-time. For example it detects a key exchange and instead of serving Alice/Bob the real key they give them the attacker's key instead. Which protocol lets Alice or Bob know a forgery has taken place? If they detect a forgery, does this cause a denial of service for Alice or Bob who can no longer communicate without being monitored?

Let's be clear, Certificate Authorities are not the solution. I'm not even sure systems like Perspectives or Convergence would help as Alice's or Bob's machine still need to connect through the hostile ISP to contact a notary or set of notaries to verify the authenticity of the original public key. How can you do that securely if the ISP is compromised? The ISP can simply make a response back to Alice/Bob pretending to be the notary and saying everything is fine.

So how do you solve the authenticity problem in this scenario and prevent active MITM attacks?

What about if Alice and Bob already have a shared secret key (perhaps exchanged in person), does this solve the problem? What protocols can be used then and do they fully prevent active MITM and denial of service?


texts: Best practises to generate IV for AES-CTR in this scenario

texts:
I'm building a cloud storage application that will store files on my servers.

I want these files to be encrypted with AES in CTR mode and the key will be always the same.

I'm wondering what would be the best way to derive an IV.

The encryption will happen on many servers so I can't use progressive values (e.g. incrementing first 8 bytes for every different encrypted file) since I can't keep count across servers.

Numbers of stored files can reach tens of billions.

What's the best practise in this scenario to derive the IV (or maybe a Key + IV)?

Should I use only one key that never changes?
Should I derive a new key for every encrypted file (from the master key)?

Edit:

If key mustn't be the same, would it be secure to do the following:

A new key (256-bit) is randomly-generated for every file.
This key is encrypted with the masterkey in ECB mode (since it's highly entropy data, do we need CBC?)
The file key is appended at the beginning of the file.


texts: Hashing a uuidv4 + time to create a unique id

texts:
First, I am no crypto expert although I am doing the MOOC.

I have an item which has as id: uuidv4

When I create this item:

I create a new uuidv4
check if it already exists
and if not, I store it in the db.

Now this item can be deleted. So lets say that there could be a conversation 'about' this item. And in that conversation is stored the id of the-just-deleted-item. After the item has been deleted, the conversation is not automatically deleted.
If some user now creates a new item (get new uuidv4) and passes the check-if-already-exists test, it could still reference an already existent conversation. THAT'S WRONG

To battle this, I was thinking of appending a UNIX timestamp (in secs) to the uuidv4 when it is created, then hash that, then store the hash. so the same uuid later on will have a different timestamp, and thus be different!

Question(s):
Which hashing algorithm to use?

Or maybe just concatenate the uuidv4 + UNIX timestamp (in secs)?


texts: Almost (epsilon) perfect secrecy - lower bound of keyspace size

texts:
As a newcomer to cryptography, I'm working on Exercise 2.12 in the book, Introduction to Modern Cryptography.

Using the proof of the theorem that says if $E$ is a perfectly secret encryption scheme, then $\lvert K\rvert \geq \lvert M\rvert$),
I've shown that the lower bound for the size of the keyspace is as below:
$$\lvert K\rvert \geq (1-\epsilon)\lvert M\rvert$$

But here's the problem: I proved this under the condition that $$\lvert\Pr[M=m\mid C=c]-\Pr[M=m]\rvert\leq\epsilon$$

So I think I should show that this definition is equivalent to the condition given in the exercise.

My question is whether the two definitions are equivalent, and if so, how can I prove it?


texts: Weakly Sublinear Compact FE from Succinct FE and XiO

texts:
I'm confused about a problem these days and I decided to seek an answer here. The question is about the section 4.1 of the paper LPST16. Let me recall the weakly sublinear compact FE scheme $\textrm{FE}$ from succinct functional encryption scheme $\textrm{sFE}$ and XiO.

$(msk, pk) \gets \textrm{FE.Setup}(1^\lambda)$: it runs $(msk,pk) \gets \textrm{sFE.Setup}(1^\lambda)$
$\textrm{ct} \gets \textrm{FE.Enc}(pk, m)$: it samples a puncturable PRF key and outputs $\textrm{ct} \gets \textrm{XiO}(1^\lambda, G_{pk,K,m})$ where $G_{pk,K,m}$ is a circuit with input length $n = \log s$ and $s$ is the max output length of the circuit $C$, and circuit $G_{pk,K,m}$ works as follows $$G_{pk,K,m}(i) = \textrm{sFE.Enc}(pk,(m,i); \textrm{PRF.Eval}(K,i))$$
$sk_C \gets \textrm{FE.KeyGen}(msk; C)$ outputs $\textrm{sFE.KeyGen}(msk,C')$ where $C'$ on input $(m,i)$ outputs the $i$th bit of $C(m)$
$y \gets \textrm{FE.Dec}(sk_C, \textrm{ct})$: $\textrm{ct}_i \gets \textrm{ct}(i)$ and $y_i \gets \textrm{sFE.Dec}(sk_C, \textrm{ct}_i)$ for each $i$ and outputs $y_1,\cdots,y_{2^n}$

Now I have two questions:

The paper speficies the circuit size of $G_{pk,K,m}$ is bounded by $poly(\lambda, |m|, \log s)$, how can we get this? to the best of my knowledge, I thinks the size of a circuit should be only related to the elements that are hardwired, is that correct? If this is correct, why the size is also polylog in $s$? More broadly, I also want to know how to calculate a circuit size.
Assume that the circuit size is also related to $s$ and $\log s$ is because of the puncturing, the second question is from my imagination. What if the circuit $G_{pk,K,m}$ outputs two encryptions, where one is over $(m,i)$ and another one is over $m$, and what is the circuit size of $G_{pk,K,m}$ now?


texts: Is there a sufficiently memory-hard asymmetric encryption available?

texts:
The Password Hashing Competition offers several memory-hard hashing algorithms that are aware of time memory trade-off and essentially try to make it hard for ASICs and FPGAs to brute-force hashes.

Is there something similar available for asymmetric encryption?


texts: Hash Function representation in identity-based encryption

texts:
Some describe as $H:F_{q}\times G_{2}\rightarrow \{0,1\}^{n}$.Some describe as $H:\{0,1\}^{*}\times\{0,1\}^{*}\rightarrow F_{q}$.
What is the meaning of product function? what kind of operation does it refer to?


texts: How would you find the Blinding factor R in RSA blind signature algorithm?

texts:
How would you find the Blinding factor $R$ in RSA blind signature algorithm when having – for example – $p=11$, $q=3$, message $m=6$, and public key $pk=7$?

The answer doesn’t have to use the numbers in the example. I’m just trying to understand how to find the blinding factor $R$ having any numbers.


texts: Exploration of Blum Micali Security By Seed Size

texts:
I'm new to cryptography and am most intrigued by mathematically based pseudo random number generators. With reference to the Blum Micali algorithm:

$X_{i+1} = G^{X_i} \bmod P$

can security be reduced to a simple stated seed size? I've seen claims that a 20 digit seed was sufficient to pass diehard test.

I've also read analysis that mentions the difficulty threshold of the algorithm is found in the number of operations required to solve the discrete logarithm problem. I'm unclear how this calculation directly correlates to seed size. If a given "hard" threshold is say $2^{64}$ operations, does that correlate to a $2^{64}$ bit sized seed?

Finally, does the security of Blum Micali required secrecy of G and P? I have not seen the secrecy of G and P mentioned in any analysis of security, however, this concern comes about by events such as Dual_EC_DRBG.


texts:
I am wondering whether the following form is a one way function with collision resistance:
$$ax^2+by^2 \mod p$$
where $a$ and $b$ are given, and $p$ is a prime number.

Since the QR (quadratic residue) $x^2 \mod p$ is one way, $ax^2 \mod p$ is also one way.
The same goes for $by^2$.

So, my guess is that the form $ax^2+by^2 \mod p$ is one way. Is that correct?

A few more follow-up questions:

How to formalize a proof that a numeric equation is one way?
Does anyone know an archive collecting all of known one way functions?
If $ax^2+by^2 \mod p$ is not one way, how about $a^2x+b^2y \mod p$?
What is instead of a prime $p$ we have a composite number (possibly with certain assumptions on its factorization)?


texts: Understanding the distinguisher for a PRG

texts: Given the following definition of a psuedorandom generator, I'm having trouble understanding what exactly the "distinguisher" D is outputting, and when?


texts: Overdeterminate system of multivariate equation

texts:
If I have a random too way overdeterminate systems of homogenous non-linear equations and few variables, What's the better way too find a solution, finding a the Groener Basis or just using linearization ?

Thanks


texts:
I have a question about EC-based DLP. I know that getting $k$ is hard when $kG$ is known. ($G$ is a generator)
Question:
Is it still hard getting $kG$ where $x$ is known? (in here, $kG=(x,y)$)
or getting $k$ where $x$ is known?
I think the former is not computationally hard. Am I right?


texts:
I have a couple of Android devices which run my app. Every device has it's own unique serial number - a hex string 16 characters long.

The app needs files, which usually reside on external SD.
These files should be usable only by a device which they are intended for.
So I need to encrypt these files, with a unique key derived from the serial number.

Now the question: What is the best way to derive a encryption key from the serial number? I thought I could just reverse it and use it as input for some hash function. But this is quite obvious I think....


texts: Would data be secure if a cryptographically secure PRNG was used for encryption?

texts:
For example, say you have a client and server. You use asymmetric encryption to securely deliver two seeds from server to client. Each user then seeds two PRNGs (one for incoming data, one for outgoing). Then when they send data over the network, they add a new randomly generated byte (from the outgoing PRNG) to each unencrypted byte. The receiver can decrypt using their incoming PRNG which has the same seed as the senders outgoing PRNG. An HMAC could also be used to verify integrity and authenticate messages.

I was just musing over this idea. I'm a total novice to cryptography, so I'm sure there's something flawed with this. I would just like to know what the flaw is?

(The PRNG I'm looking at is ISAAC which is also a stream cipher, but would this work with any PRNG, disregarding speed?)

EDIT: Also, if not secure by itself, would it be possible to do this on top of AES? Is there no point (AES is already secure enough)? Or would it actually hurt security?


texts: Is it safe to publicly expose PBE-protected PGP secret keys?

texts:
I am working on a PGP scheme where a private key is created offline (and in volatile memory) and must be reused on very rare occasions to sign a piece of exportable data.  The private key is locked using a random passphrase with ~256 bits of entropy, and the passphrase and resultant PGP secret key are written on paper and locked up for later use.  The key needs to remain usable for years in the future.

To simplify the future import procedure by reducing the amount of manually entered data, would it be safe to publicly export the secret key file provided the passphrase is kept locked up?  That way, the secret key can be imported off of a flash drive or similar, while only the passphrase needs to be keyed in.


texts: What is the difference between SHA256WITHRSA and SHA256WITHRSAENCRYPTION digest algorithms?

texts:
I installed djigzo on my android phone and I want to use it for smime mail.
I don't know the difference between choosing SHA256WITHRSA and SHA256WITHRSAENCRYPTION digest algorithms in the settings.

My online search only returned OIDs and code samples. Can you enlighten me?


texts:
I looked into the code for md5_crypt the other day (yes, I know it's insecure), and I noticed that after mushing up everything with strange md5 hashes, it generates a base64 string with a strange order of bytes. You can see that either in the FreeBSD implementation lines 144-155 or in passlib which calls this function.

Why do they do that?


texts:
I was attending a database encryption session at a developers conference. The presenter (who was a published author on the subject) said that MS SQL Server did not support salted hashes in the database, but it does support salting with encryption. This was the first I heard of salting in encryption. I asked for clarification to make sure that was what he was saying.

Is this something anyone else has heard of before? Is this an important practice that I have just never heard of before?


texts:
I'm trying to understand the current context for fully homomorphic encryption. What are the most influential papers that are the basis for the most close-to-practical techniques today?

Of course Gentry's original paper is the most influential, but it is far from practical. A 2011 paper I see that appears to achieve much better performance (also by Gentry) is https://eprint.iacr.org/2011/277.pdf. What other papers published in the last 7 years are worth reading? (I would prefer papers with a post-quantum context in mind).


texts: Cryptanalysis of AES on SSD with TRIM enabled

texts:
Attack scenario:

SSD physically retrieved from a computer that is turned off. The entire disk is encrypted with AES 256-bit (GNU/Linux, LUKS). The SSD has had TRIM enabled for several years and the file system has seen a lot of use, i.e. a lot of files deleted over time (triggering TRIM). Assume that the key used is sufficiently strong to resist any brute force/dictionary attack.

Cryptanalysis:

As far as I understand it, TRIM aids in cryptanalysis in that it will be known which regions of the device are in use and which are not in use.

But exactly how does the cryptanalysis proceed from here? What kind of attack will be performed? Does the attack have a name? Does it have any realistic chance of success? It would be interesting to know if an attack like this ever succeeded, either in an academic setting or known to have succeeded in the field.


texts: Efficient way to combine collection of hashes into a single hash?

texts:
I have a system where each user will submit a set of data. The data will be hashed and their hash will be submitted to the server. My plan is to combine each users hash (converted to bytes XOR'd with the root hash) to generate a final hash. This is done as a means to create entropy so that the final hash can be used to generate a "random" number. It is not possible to generate a pseudo / truly random number on the system, hence the work around.

Currently, I am doing the following on the server (pseudo code) :

//hexidecimal 54673257461630679457 (large prime)

var rootHash = 0x2F6BE6DFD71F8B9A1;

submitData(var userHash){
    rootHash ^= userHash;
}

After all of the user hashes are XOR'd with the root hash, the root hash is converted into a number and then the last 10 digits of that number are used as the "random number."

Users are able to see eachother's hashes, however with a system like this, I figure even if they calculated the final number, submitting new data would change the root hash and thus change the final number generated.

I am not very experienced in this field so my question is, what are some of the cons of using a method like this, and is there a more efficient way to do this?


texts: How to calculate complexity of ElGamal cryptosystem?

texts:
How to calculate time and space complexity of ElGamal encryption and decryption as there are two exponentiation operation during encryption and one during decryption? Here is my code for encryption:

for i=1:d
    pow=pow*g;
    y=pow%p;
for j=1:r
    pow1=pow1*g;
    C1=pow1*g;
    pow2=pow2*y;
    C2=(M*pow2)%p;

I think the first for loop will execute $O(d)$ times and second for loop will execute $O(r)$ so total time complexity of this is $O(d)+O(r)$ as it is not known which is bigger among $r$ and $d$.


texts: In The Ristretto Group, do all points sampled with Elligator have the same order?

texts:
Assume the Hash-to-ristretto255 function Elligator as laid out here. Assume a random hash that is then mapped to a point in the Ristretto group - is this point then of prime order (is it even in the same order order as the basepoint?).
If not, is it guaranteed that the Discrete Logarithm is still hard for the sampled point?


texts:
I'm planning to implement a public mailbox for receiving feedback, and I'd like to use hash-based proof-of-work to frustrate spammers.

First, we want to use 320-bit capacity Gimli permutation as the underlaying primitive for the sponge-based hash function, because

I don't want to make it hard for server to re-evaluate KDF each time there's a message,
it's not available on commodity hardware, which means someone will have to pay for silicon to have it accelerated,
less parameters to tune (capacity/rate and preimage length).

Second, for each message, there will be a time-based challenge (server will allow a small window for error) prepended to each message to be hashed and sent to deter pre-computation attacks.

However, there's a few things I'm not confident about. Namely:

Whats the advantages and disadvantages of using plain hash and KDFs when used in POW?
Besides replay, pre-computation, what are the other attacks that must be considered in designing a secure proof-of-work system?


texts: Standard symbol / notation for "x knows y", or the inverse

texts:
What's the standard way to express "$x$ knows about $y$", or "$x$ has no knowledge of $y$" in cryptographic notation?

Example (PRNG predictor):

$\exists f : P(f(G(k)|_{0..n}) = G(k)|_{n+1}) \geq 0.5 + \epsilon$, for non negligable $\epsilon$, where $f$ has no knowledge of $k$.


texts: Why does WOTS+ need a checksum during signing operation?

texts:
I was reviewing WOTS+ scheme for consideration in our private blockchain, and noticed that it had a small overhead of calculating a checksum as seen in the following pseudocode excerpt from the SPHINCS+ submission to NIST

wots_sign(M, SK.seed, PK.seed, ADRS) {
  csum = 0;

  // convert message to base w
  msg = base_w(M, w, len_1);

  // **compute checksum** <<<<============
  for ( i = 0; i < len_1; i++ ) {
    csum = csum + w - 1 - msg[i];
  }

  // convert csum to base w
  csum = csum << ( 8 - ( ( len_2 * lg(w) ) % 8 ));
  len_2_bytes = ceil( ( len_2 * lg(w) ) / 8 );
  msg = msg || base_w(toByte(csum, len_2_bytes), w, len_2);
  for ( i = 0; i < len; i++ ) {
    ADRS.setChainAddress(i);
    sk = PRF(SK.seed, ADRS);
    sig[i] = chain(sk, 0, msg[i], PK.seed, ADRS);
  }
  return sig;
}
//Algorithm 5: wots_sign – Generating a WOTS+ signature on a message M.

Why is it there? Is it necessary for the security of the scheme?

Update

According to "On the Security of the Winternitz One-Time Signature Scheme", the checksum deters "second-key" and "key-collision" attack should there be a functional forgery oracle. How relevant an attack is it to WOTS+ and to other regular signature schemes?


texts: Question about Cipher Block Chaining(CBC)

texts:
I'm studying at the moment the CBC Encryption method,and I was asked in an excercise how many bits would be wrong after decryption if during the transmission 2 bits are interchanged.
My guess is that the whole bits are wrong due to how CBC works, am I correct?


texts: Elliptic Curve Digital Signature algorithm fails

texts:
I would like to monitor step by step running of ECDSA.

Parameters I am working on:

The elliptic curve satisfies the equation: $y^2 = x^3 + x + 1$.
I picked up the base point $G$ as: $(0, 1)$
Finally, the modulo $p$ is $977$

My private key is $19$. Thereby, my public key is equal to $19\times G$ and its coordinates are $(396, 650)$. Suppose that my hash is equal to $14$.

Then, I picked up a random key. It would be $17$. So, random point would be $17\times G$ and it is equal to $(699, 739)$.

My signature is pair of $r$ and $s$, where $r$ is $x$ coordinate of my random point, and $s$ can be calculated as:
$$\begin{align}
r &= 699\\
s &= ((\text{random key})^{-1} \bmod p)\cdot(\text{hash} + r \cdot (\text{my private key}))\\
&= (17^{-1}\bmod 977)\cdot(14 + 699\cdot19)\bmod 977\\
&= (115\cdot13295)\bmod977\\
&= 1528925\bmod977\\
&= 897
\end{align}$$
So, my signature is $(699, 897)$.

Let's verify the signature
$$\begin{align}
w &= s^{-1}\bmod p\\
&= 897^{-1}\bmod 977\\
&= 403\\
u_1 &= \text{hash} \cdot w \bmod p\\
&= 14 \cdot 403 \bmod 977\\
&= 5642 \bmod 977\\
&= 757\\
u_2 &= r \cdot w \bmod p\\
&= 7699 \cdot 403 \bmod 977\\
&= 281697 \bmod977\\
&= 321
\end{align}$$

Now, I calculate the checkpoint
$$\begin{align}
\text{checkpoint}&=u_1\times G + u_2\times(\text{public key})\\
&= 757\times(0, 1) + 321\times(396, 650)\\
&=(707, 48)
\end{align}$$

Finally, I need to compare the $x$ coordinate of checkpoint and $r$ value of signature. But $x$ coordinate of checkpoint is $707$ whereas $r$ value was $699$. They are not same. This means that signature is invalid. But they should be equal! Anyone can help where I am wrong?


texts: What is the usual block cipher mode that goes with CTS

texts:
I am wondering: what is the most common, or most used, block cipher mode used that goes with CTS (CypherText Stealing)?

Is it ebc or cbc?