texts: Who provides prime numbers for cryptographic protocols?

texts:
I am currently writing a thesis about different cryptographic protocols like DH-Key exchange, TLS or IKE.
Most of them rely on a prime number earlier or later, so for security reasons I wondered if this prime number is supplied by the user and if yes that leads to the question if I can manually provide it (for example to use a pseudoprime to break the underlying primitive more easily).
I really tried to search online, but there are very little information about this part of protocols. I hope you can help me with that.
Thank you for your time and answers :)


texts: Is my XTEA encryption key safe if I publish my firmware both as plain text and encrypted?

texts:
I'm using this bootloader that implements XTEA encryption for uploading an encrypted firmware to small MCU:

https://github.com/nyholku/diolan-plus2

the actual XTEA code is here:

https://github.com/nyholku/diolan-plus2/blob/master/fw/xtea.asm

It is not my code but to me it looks like it uses 16 byte key and 64 iterations
and seems to be pretty much equivalent to the wikipedia XTEA C-implementation.

Now my questions is, is my encryption key safe if I publish my firmware both as plain object code i.e. plain text and encrypted?

The firmware size if max 48kB out of which several kilobytes at the end will be 0xFF.

How about if over the years I publish number of ( <50 ) such plain text / encrypted text pairs?

I've read from the interweb that this should be safe but because the subject is so complex I would like to make sure I don't make a rookie blunder.


texts: What happens if I modify the Merkle–Damgård hash method?

texts:
Does the Merkle–Damgård hash function still offer Collision Resistance (CR) when the following changes are made? Each case is independent from the other.

Here is what I want to modify:

Say I want to get rid of the IV at the beginning and replace it with the first block of the message ($M_1$). That is, $T_0 = M_1$ and the 2nd tag $T_1$ will be generated using the compression function $h$, so that $T_1 = h(M_1,M_1)$. Instead of what it should have been: $T_1 = h(IV,M_1)$.
Instead of using IV as the first tag $T_0$ and adding the message length in the last block, set $T_0$ to be the the message length $q$ (such that it is padded to the block length).
Instead of outputting the result of Merkle–Damgård $H(m) = h(T[i-1]; M[i])$ we just output $T[i-1] || M[i]$, where $||$ denotes concatenation. Assuming in this version of Merkle–Damgård, the last block will just be the length of the message.

Can someone tell me if any of this cases offers Collision Resistance? Please explain why this is the case.


texts: Usefulness of blockchain technology in private sector

texts:
I understand that blockchain technology works for cryptocurrency.
But I don't get why it should be used in private sector.
For example, I often read that it is useful to monitor the supply chain of food.
But why is that? If a company uses blockchain technology for that, how does it work?
From my understanding, in that case it is hard to get a distributed blockchain.
But with a non-distributed blockchain, I only see disadvantages.
Why not use a good old standard database in such cases?
Am I missing something?


texts: How do you prove that if f(x) and g(x) are negligible, then f(x)/g(x) is not?

texts:
I can use an example: the case where we have $x$ such that $f(x)=g(x)$. The quotient is $1$, a non-negligible function. However, we can't conclude that all functions $f(x)/g(x)$ are also negligible.

How can I formally prove this?


texts: SHA-256 Reversing A String of Equal Length

texts: I've done a lot of reading on how SHA-256, I've found that SHA-256 is irreversible because more data is fed into the hashed string than the hash string contains.  But, what if the data that was inputted was equal in size to the output string, a string of 64 characters is inputted a string of 64 characters is outputted.  Would it be possible to reverse the hashed data back to the original string?


texts: An insecure signature with message recovery, Dan Boneh

texts: Someone can help me to resolve this questions from the book of Dan Boneh (University of Standford)


texts:
I am in attempt to understand relative insecurity of certain encryption schemes. Particularly of interest is DES and RC2. I know AES is better and should be used to encrypt. But practically, if something is encrypted with (1) DES or (2) RC2 (3) RC4 what level security is achieved.

In affect I am asking:

If a adversery is given a {DES/RC2/RC4} ciphertext, is it possible that they can decrypt or can a determined adversary definitely decrypt?


texts: Shamir Secret Sharing - How to reconstruction secret? Example

texts:
I try implement Shamir Secret Sharing.

In this video: https://www.youtube.com/watch?v=j7Ngtl1cCpY is example.

But for another three share holders is can't reconstruction secrete.

For example:
a)
a(1) = 15
a(2) = 6
a(4) = 10

b)
a(1) = 15
a(2) = 6
a(5) = 6


texts: Bit Commitment - from any One Way Permutations

texts:
In the Wiki Page on Commitments, it is given that a commitment scheme may be perfectly binding or perfectly concealing but not both.

But in the following section about Bit-commitment from any one-way permutation, they mention that "This scheme is concealing..." and  "Perfect binding follows..."

It does seem like this commitment scheme is both binding and concealing. What am I missing here?


texts: Why are collision attacks important when talking about MAC schemes?

texts:
I'm reading Ferguson, Schneier, and Kouno's Cryptography Engineering, and it has a section on MACs. It discusses different types of MACs, but it seems to claim that to acheive 128-bit level security, you need a 256-bit MAC due to the birthday attack.

Why is this the case? Why are collision attacks a concern in MACs? I think that to break a MAC, you need a preimage attack to guess the plaintext, or a second-preimage attack to forge messages. In these cases, the birthday attack is irrelevant since it only finds some random collision, which may not be relevant to the data stream being attacked.

What am I missing? It seems that in general 128-bit MACs are much more popular (GCM and CCM and all those fancy AEAD modes have 128-bit authentication tags); surely they can't have only 64 bits of security? Is Cryptography Engineering simply paranoid?


texts: Origin of the Chi-Squared test statistic for serial test (two bit test)

texts:
On page 181 of Handbook of Applied Cryptography Chapter Five, it states the following:

  The purpose of this test is to determine whether the number of occurrences of 00, 01, 10,
  and 11 as subsequences of s are approximately the same, as would be expected for a random
  sequence. Let $n_0$, $n_1$ denote the number of 0’s and 1’s in s, respectively, and let $n_{00}$,$n_{01}$,$n_{10}$,$n_{11}$ denote the number of occurrences of 00, 01, 10, 11 in s, respectively. Note that
  $n_{00} + n_{01} + n_{10} + n_{11} = (n − 1)$ since the subsequences are allowed to overlap. The
  statistic used is
  $$ X_2 = \frac{4}{n-1}(n_{00}^2+n_{01}^2+n_{10}^2+n_{11}^2)-\frac2n (n_0^2 +n_1^2) +1$$

Where does this statistic come from? I'm not entirely sure, and the book doesn't explain it's derivation. Normally, $ X=\frac{(Z-\mu)^2}{n^2}$ for Chi-Squared test ( if i recall correctly), but I don't see how this can result in the expression above. For each $n_{ij}$, the approximate value is $\frac{n_i+n_j-1}{4}$, and the expected value would be $\frac{n_i+n_j}2$, but how do we combine them in such a way that we get the expression for $X_2$?

If this belongs in Math, rather than Cryptography, I can happily delete and move it. I just figured since the question is cryptography related, it may receive better attention here.


texts: What is the "single-letter characterization of the secrecy capacity"?

texts:
I'm reading a paper [1] in which secrecy capacity are being discussed under the following terms:

  A single-letter characterization of the secrecy capacity that holds for the general case remains unknown until now (if it exists at all). Only a multi-letter description of the secrecy capacity has been established so far.

What do the terms marked in bold mean, either in plain English or expressed in terms of entropy/mutual information/etc ?

[1]: Secure Communication under Channel Uncertainty and Adversarial Attacks - Rafael F. Schaefer, Holger Boche, and H. Vincent Poor


texts: Static Salt In Argon2 For Converting ECDH Shared Secret Into AES Key

texts: I am using Argon2 to convert an ECDH exchange result into the correct format for AES-256 encryption. However the library that I am using for Argon2 requires a salt. Are there any weaknesses of using a static, hard-coded salt for the Argon2 key format conversion?


texts:
I wanted to get an idea on how the whole cold-storage private/public key generation works for different cryptocurrencies. So I was playing around with BIP32 deriviation path on:
https://iancoleman.io/bip39/#english

I noticed that for example BTC, XRP, PIRL all have the same BIP32 root key and BIP32 extended private/public key, but DOGE was completely different.
Why is that? BTC hashing algorithm is SHA256 and PIRL uses Scrypt, their root seeds are the same, while DOGE which uses Dagger has a different seed and private/public key.

The second part that I don't understand is the generation process of addresses for different cryptocurrencies, is there a web site where I could look up on how it's done? The only one I found is for bitcoin here https://www.mobilefish.com/services/cryptocurrency/cryptocurrency.html#refMethod2


texts: Fewest qubits required for the discrete logarithm problem and integer factorization

texts:
According to a paper from 2002, the most efficient circuit to factor an $n$-bit integer requires $2n+3$ qubits and $O(n^{3}\lg(n))$ elementary quantum gates, assuming ideal qubits. Later on, according to a paper from 2008, it is shown that it requires $6n$ qubits to solve the discrete logarithm problem as it applies to elliptic curves. What I want to know is whether or not this is the theoretical lowest number of qubits required, and whether or not this information is still up to date. For Shor's algorithm specifically, there are three questions I have. Are these statements up to date and correct?

RSA 2048 requires, at minimum, 4099 qubits ($2048 \times 2 + 3$)
DHE 2048 requires, at minimum, 4099 qubits ($2048 \times 2 + 3$)
ECDHE 256 requires, at minimum, 1536 qubits ($256 \times 6$)

I know there are several similar answers on this site, but many of them are contradictory or only reference the original 2002 paper, and none of them answer whether or not this is the known theoretical lowest number of qubits required, or just the current state-of-the-art.


texts: How represent message in Menezes–Vanstone elliptic curve cryptography

texts:
I ask about represent message in Menezes–Vanstone elliptic curve cryptography I now encrypt function as follow

$C_1 = (M_1 * K_1)  mod\ P$

$C_2=(M2 * k_2)  mod\ P$

My question is about how much the size of $M_1$ and $M 2$, if we assume we are working on the 256 curve.
Does the size of $M_1$ is one character and $M_2$ is also one character or $M_1$ is 32 byte
 and $M_2$ is 32 bytes.
I hope anyone clarification about my problem.

I need any proposal.


texts:
PGP Digital Timestamping Service webpage mentions

The service operates in a number of different "modes" depending upon the required results. The current modes are:-
post: forwarding an outbound message with a proof of posting certificate
clear: the received message is clearsigned and returned to the sender
header: the received message (with headers) is clearsigned and returned to the sender
text: the received message is signed and returned ASCII armoured to the sender
pgp: the received message (which must be ASCII armoured) is assumed to be a PGP file which is then signed and returned to the sender
binary: the received message (which must be ASCII armoured) is assumed not to be a PGP file which is then signed and returned to the sender

What is a clearsigned message? I searched around quite a bit using Duck Duck Go, and on this site but I couldn't find an explanation.


texts: What exactly is Let's encrypts chain.pem file?

texts:
While trying to understand the use or meaning of the fullchain.pem file created by let's encrypt I stumbled upon this post in which fullchain.pem is explained as:

fullchain.pem is a concatenation of cert.pem and chain.pem in one file. In most servers you’ll specify this file as the certificate, so the entire chain will be send at once. Some clients require you to specify the above two files separate. In that case you won’t need

While chain.pem on the other hand is described as

chain.pem contains the intermediate certificate, the certificate from Let’s Encrypt containing the public key which is “coupled” to the private key which signed your certificate (the one above). This intermediate certificate is required for clients to verify your certificate;

But I have troubles really understanding what this means. By this I mean what exactly is intermediate certificate and where does it come from.
I understand the concept of CA's and the fact that CA issue certificates. I understand that the certificate issued by the CA which is put to use is the end user certificate.
I also understand the chain of trust, where there are intermediate CA between the end user certificate and the root CA.
What I can't understand is how let's encrypt can know all the possible intermediate CA between the root CA and the end certificate.
I mean it is possible to know all the CA, that the root CA itself signed. But what if those other CA's created other CA's that ends up issuing the end user certificate, how can this ever be in chain.pem?
Which then begs the question, how can those end user certificate's be ever verified, since it seems the full chain of trust, the full intermediate CA is not known in chain.pem?
Anyone kind enough to help me understand the setup? Thanks!


texts: Is it secure using LWE-based cryptosystem under RLWE-based parameters?

texts:
I'm computer guy having trouble with cryptography.

I recently read the BGV Homomorphic encryption paper which was constructed under both LWE and RLWE assumptions.

I was implementing Threshold version of BGV encryption [AJW12] using HElib optimized under the RLWE assumption, and I found out that [AJW12] proved the security under the LWE assumption.

A paper [LN16] says that the RLWE is a special instance of the LWE problem.

So, I think that [AJW12] encryption under RLWE parameters is still secure, but I'm not sure.

Am I right?


texts:
I'm working with an implementation that creates a blinding value for RW signatures with the following C++ code:

Integer r, rInv;
ModularArithmetic modn(m_n);

do {
    // Do this in a loop for people using small numbers for testing
    r.Randomize(rng, Integer::One() /*min*/, m_n - Integer::One() /*max*/);
    rInv = modn.MultiplicativeInverse(r);
} while (rInv.IsZero() || (Jacobi(r % m_p, m_p) == -1) || (Jacobi(r % m_q, m_q) == -1));

The Jacobi tests were added to remediate Sidorov's Breaking the Rabin-Williams digital signature system... and CVE-2015-2141.

Instrumentation is showing the loop can execute 1 time to 10 or 12 times (I believe the expected average is 8 times).

I feel like there's a way to speed up the execution of the loop. I started looking in the HAC and Google Scholar, but I did not find a related article or paper. I tried a couple of naive speedups, but they did not produce expected speedups or bound the worse case. The first was to generate a random integer in the range $[1, n - 1]$ that was congruent to $3 mod 4$. The second was to generate two smaller integers in the range $[1, p - 1]$ and $[1, q - 1]$ (both congruent to $3 mod 4$), and then multiply them.

Is there any way to speed up the execution of the loop so that the blinding value $r$ usually satisfies the condition in 1 or 2 tries or so?

Or is the implementation above ideal?

A related question is Rabin-Williams, blinding and size of Integer r? In this question, I explored smaller random integers to mask the operations.


texts:
I have a few questions about how to use zk-snark. Since the basic logic of using zk-snark is:

using a circuit to represent a problem,
generate an R1CS from the circuit,
transform R1CS to QAP and then we can run zk-snark

For the first part, is there any specific definition or feature for the problem, and could all problems, which can be verified, be converted into circuits and use zk-snark to generate proofs?
Besides, how to flatten a problem into a circuit, by programming or using mathematical methods?


texts: Low weight linear $\varepsilon$-universal hash function

texts:
According to the definition, an $\varepsilon$-universal linear hash function family, given a field $\mathbb{F}$, is a set of linear transformations $\mathcal{H} \subseteq \mathbb{F}^{m,n}$ such that for any $\mathbf{v} \in \mathbb{F}^n \setminus \{0 \}$ if $H \sim U(\mathcal{H})$
$$
 \Pr[ H \mathbf{v} = 0 ] \leq \varepsilon.
$$
My question is whether it is possible to have an $\varepsilon$-universal linear hash function family with low Hamming weight (over small order field, say $\mathbb{F}_2$), that is, calling $w( \cdot )$ the hamming weight of a vector over $\mathbb{F}^n$, we want to have a constant $M$ such that for "almost any" $H \in \mathcal{H}$
$$
  w(H \mathbf{v}) \leq M \cdot w(\mathbf{v})
$$
Now, I've ruled out the possibility to have $M = 1$ as this implies that the column of $M$ need to be vectors of the kind $\alpha \cdot e_i = (0, \ldots, \alpha, \ldots, 0)$ in the $i$-th position and one of the vectors $e_1$, $e_2$ or $e_1 - e_2$ is going to be mapped to zero with non negligible probability. Can one do better? For instance can $M = \Theta(\log(n))$ or $M = \Theta(\sqrt{n})$ be achieveable? Is there any result in the positive direction?


texts: Hashing high entropy key into AES format

texts: If I have a high entropy key (ECDHE shared secret), what type of hash should I use to format this into an AES-256 key? Is Sha256 or Sha3_256 sufficient to maintain entropy or do I need to use a KDF (Scrypt / Argon2) and exchange the salt during the handshake??


texts:
Given an element $g$ in a cyclic group $G$ of known order $m$ its easy to test if $m$ has even or odd order. In other words $\textrm{ord}(g) \pmod 2$ can be computed easily.

In some cases where the order of the group is unknown it is also easy to test if $g$ has even order for a large subset of $g$ in $G$.

For example, if $g$ is an element in ${\mathbb{Z}_n}^*$ and the Jacobi symbol $\left(\frac{g}{n}\right)$ is $-1$ then $g$ has even order. (If it is $1$ then we can't say anything.)

What other examples are there of cryptographically interesting groups $G$ where it is easy to test if $g$ has even order (or odd order) for a large subset of $g$ in $G$?


texts: "Memory-Hard" vs. "Memory-Bound" Functions?

texts:
One of the approaches in order to prevent Sybil or DoS attacks is CPU-bound PoW. However, because of the influence of Moore’s law, the memory-based approaches are suggested.
As actually there are two different terms: (1) memory-hard functions and (2) memory-bound functions;
Does it mean that we have two different memory-based techniques?
And if yes, What is the difference between these two terms?


texts: Implementing Inferno's ECIES: Creating a symmetric key from sender's public key

texts:
I'm coding(in C#) an offline(no network or server), hybrid file encryption app, implementing Inferno's ECIES.  The user's private key is to be stored either on the pc drive or on a usb key, after being encrypted with a key(password) hashed with ~ 1 million Scrypt iterations. The user can load his key into protected memory once the app is started. Loading the key takes a huge 20 seconds but it would be a one-time/session delay if the following is acceptable:

For files meant to be kept by the user(some are sent, some are kept), is it secure to produce a "shared" symmetric key with the user's own public key? This would allow the user to have one password to remember(instead of one for each symmetric and asymmetric key) and since the symmetric key produced this way has a high entropy, hashing iterations are not necessary when saving/loading files, something that happens very often during a session.

The code itself is working but that does not tell me if the approach is secure. Just to make sure I'm clear, here is a shortened code example:

    internal static void SendText(string text, byte[] ephemeralPublicBlob, string file)
    {
        CngKey receiverKey = ephemeralPublicBlob.ToPublicKeyFromBlob();
        var ephemeralBundle = receiverKey.GetSharedEphemeralDhmSecret();
        var ephemeralPublic = ephemeralBundle.EphemeralDhmPublicKeyBlob;
        var ephemeralSymmetric = ephemeralBundle.SharedSecret;
        var textSegment = new ArraySegment<byte>(text.ToBytes());
        var ciphertext = SuiteB.Encrypt(ephemeralSymmetric, textSegment);

        using (FileStream fs = new FileStream(file, FileMode.Create, FileAccess.Write))
        {
            byte[] sent = Utils.Combine(ephemeralPublic, ciphertext);
            fs.Write(sent, 0, sent.Length);
        }
    }

    internal static string ReceiveText(string file, CngKey masterKey)
    {
        string decrypted = null;
        using (FileStream fs = new FileStream(file, FileMode.Open, FileAccess.Read))
        {
            byte[] received = new byte[fs.Length];
            fs.Read(received, 0, (int)fs.Length);
            var ephemeralPublic = new ArraySegment<byte>(received, 0, 104);
            var cipherText = new ArraySegment<byte>(received, 104, received.Length - 104);
            var sharedSecret = masterKey.GetSharedDhmSecret(ephemeralPublic.ToArray().ToPublicKeyFromBlob());
            decrypted = SuiteB.Decrypt(sharedSecret, cipherText).FromBytes();
        }
        return decrypted;
    }

So, in the first function(SendText), if I pass the sender's(instead of receiver's) public blob as the byte[] argument, the code works, but am I leaking/messing something?


texts: Nomenclature of Certificate Authorities and Certificates in PKI

texts:
In PKI there are different terms to identify certificate authorities in the chains. All terms I know of are as follow:

Root
Subordinate
Super
Intermediate

I see all terms used interchangeably in the combination with “certificate authority (CA)” and “certificate”. I read a lot of web pages as well as books and my personal understanding from all of this is as follow:

A CA is called a root if it’s certificate has no super certificate.
A CA is called a subordinate if it’s intermediate certificate has a super certificate of another subordinate or root CA.

What is the actual meaning of the four terms and their relation to each other?

  How is this question of a practical matter to cryptography?

I‘m not entirely sure if this question fits this StackExchange or if it should go somewhere else. However, I consider this question to be directly related to cryptography since it is about PKI and the nomenclature is specific to the world of cryptography and PKI.

The practical matter comes into play during communication – especially in documentation – regarding PKI, CAs, and certificates.


texts: Creating a license system based on asymmetric encryption (RSA or ECDSA)

texts:
I’ve spent a couple of days researching the topic of creating a license system for my desktop software. While I fully understand that there’s no perfect copy protection, this approach seems to have the best balance for me.
There are a couple of details that I can’t fully get my head around before starting with the implementation. I’d really appreciate if you could share your thoughts on the following topics:

1. Encrypt or Sign? (answered -> sign)

In my understanding both encrypting and signing the license information on my server-side with my private key would work. The desktop client would either have to decrypt or verify the signature of the license text-file with the embedded public key. The only difference I see is that in the latter case the content of the license file is humanly readable while the encrypted version is not.
Would you rather encrypt or sign the license file? Why?

2. Hash or directly encrypt/sign the License? (answered -> signing automatically hashes it)

Let’s say the license information text consists of about 300 bytes. Would you recommend to sign/encrypt it directly, or hash it and then sign/encrypt the hash? I’m asking this because I’ve read different statements that asymmetric encryption isn’t suitable for large data. But what’s the limit?

3. Revoke a License?

What’s the best way to revoke an already issued license? I understand that having an online blacklist is probably the most accurate solution, however I don’t want the software to be dependent on an Internet connection and the reliability of my server. So I guess the alternative is to have black-listed licenses within the application being maintained with new releases? In that case what exactly would I create a list of? The signed/encrypted license (probably too big with a growing list)? A hash of it? Something completely different?

Edit:
Combining the replies so far I guess the first two questions can be combined to "Sign it and don't care about the content length".

The third question however remains unclear to me. I'd like to point out that I don't want to have a dependance on an online server for not bothering honest customers. After all forced online connections bring more annoyance than security.
So there needs to be kind of an "offline solution", even if less secure. Please reconsider question #3 under this aspect.

Actually I'd even like to extend question #3 by the following scenario:

4. Replace stolen/hacked private key
In a worst case scenario the private key might get stolen or somehow hacked, so the attacker is able to create a license generator himself. What would I have to do in this case? I can't blacklist some licenses like in #3, so instead I'd have to replace the key pair, wouldn't I? However in my understanding that would also mean that all customers would require to receive new licenses when updating to a new version with the replaced public key. Is there some clever solution for only blacklisting licenses with the old key pair that have been created after a certain date so the already created licenses before some date stay intact? I understand that it'd require some kind of timestamp system that an attacker can't fake. Is there such a thing?

Thank you!


texts: AES CBC encoding of decomposable OAuth2 tokens

texts:
We're building a stateless RESTful API that relies on the content of OAuth2 tokens to identify users and what they have access to. Users authenticate with other means and are given a token, which they then use to authenticate API requests for an hour or so till it expires.

Since we want it to be stateless, we can't use random tokens with a lookup table. The token basically consists of username + start timestamp + end timestamp. (The token is considered valid if it has a valid user and the current time is between the start and end timestamps.) We encrypt the token before sending it to the user and decrypt it each time we get it back in a request.

If we naively encrypt the token with AES in ECB mode, the ciphertexts for a given user's tokens end up very similar to one another, because the usernames encrypt to the same ciphertext every time, and I assume somebody who knew what they were doing could XOR a few tokens together and recover the key fairly easily.

If we encrypt them in CBC mode instead -- with a fixed IV, so we can decrypt them later -- I assume the attack is a little harder (maybe a lot harder? maybe not harder at all?), but the ciphertexts still end up very similar.

What we're currently doing to get around this is reverse the token (bytewise) before encrypting in CBC mode, so the highest-entropy bytes get encrypted first and feed into the rest of the chain, and there's no obvious similarity between ciphertexts, and at least we don't look stupid. But, as they say, anyone can design a cryptosystem they themselves can't break.

Questions, then:

Is this actually doing any good?
Is there a known best practice we should be following instead?
If there isn't a known best practice, are there any obvious improvements?

(Note: All of this is happening over SSL so we're not particularly worried about man-in-the-middle attacks etc. But we don't want to encourage any otherwise authorized users to try to forge tokens, either.)


texts: Library to find an addition chain for a large number?

texts:
I need a short addition chain for a number $n>2^{100}$ in order to implement a fast exponentiation. The memory footprint is not important.

Finding an optimal chain for a large number $n$ is difficult (and considered by some to be an NP-complete problem). However, many heuristics to find good but suboptimal chains have been proposed in literature.

Is there any library to search for short chains, or do I have to implement something by myself? (All the tools I found so far only seem to work for small numbers.)

Many thanks!

Update:

I implemented the binary approach, but the resulting chain was rather long.
I then implemented the algorithm based on continued fractions described on pages 161-162 in the "Handbook of Elliptic and Hyperelliptic Curve Cryptography" by Cohen et al., and the resulting chain was already 40% shorter. I will just use this chain for my implementation. Here is the corresponding source code:

from math import *

def add(v,j):
    return v+[v[len(v)-1]+j]

def cross(v,w):
    r=v
    vs=v[len(v)-1]
    for y in w[1:]:
        r=r+[y*vs]
    return r

def is2l(x):
    l=log2(x)
    if 2**l==x:
        return l
    return -1

def log2(x):
    l=0
    while 2**(l+1)<=x:
        l=l+1
    return l

def minchain(n):
    l=is2l(n)
    if l!=-1:
        a=[]
        for i in range(l+1):
            a+=[2**i]
        return a
    if n==3:
        return [1,2,3]
    return chain(n,n/int(2**ceil(log2(n)/2.0)))

def chain(n,k):
#    print "chain(",n,",",k,")"
    q=n/k
    r=n%k
    if r==0:
        return cross(minchain(k),minchain(q))
    else:
        return add(cross(chain(k,r),minchain(q)),r)

def sequence(c):
    for i in range(len(c)):
        a=c[i]
        if a==1:
            print "a["+str(i)+"]=x"
        else:
            for j in range(i*i):
                if (j%i)<(j/i) and c[j%i]+c[j/i]==a:
                    print "a["+str(i)+"]=a["+str(j%i)+"]*a["+str(j/i)+"]"
                if (j%i)==(j/i) and c[j%i]+c[j/i]==a:
                    print "a["+str(i)+"]=square(a["+str(j%i)+"])"

sequence(minchain(2**127-1))

Probably the more complex (e.g. backtracking or genetic) algorithms described in the literature will find even shorter chains. However, I will not implement these myself.


texts:
Assume we can prove the security of the digital signature scheme against key-only (no message) attacks.
Now we want to prove security against adaptive chosen message attack. We use the random oracle model. The standard proving technique seems to be to replace signer with a simulator and then we have an adversary that is capable of performing no message attack.
Assume $A^{\mathcal{O},\mathrm{Sig}}$ is an adversary which uses random oracle $\mathcal{O}$ and real signer $\mathrm{Sig}$. If we replace signer $\mathrm{Sig}$ with a simulator $S$, we get algorithm $A^{\mathcal{O},S}$.
The proof usually involves two steps:
Step 1. First we prove $P(A^{\mathcal{O},\mathrm{Sig}}\;\text{succeeds})= P(A^{\mathcal{O},\mathrm{S}}\;\text{succeeds})$.
Step 2. However, if $A^{\mathcal{O},\mathrm{S}}\;\text{succeeds}$ this doesn't necessarily mean its executing path equals to the execution path of some $A^{\mathcal{O}', \mathrm{Sig}}$ for some other oracle $\mathcal{O}'$. If we want to achieve this, we must find collisions of queries to the oracle.
An example of this technique is lemma 4 in the paper Security Arguments for Digital Signatures and Blind Signatures by Pointcheval and Stern.
My question is: how do we prove Step 1 in general? An adversary could always check if the signature from the signer (or from the simulator) is a valid signature using the oracle $\mathcal{O}$. Therefore we must prove equality in the form
$P(A^{\mathcal{O},\mathrm{Sig}}\;\text{succeeds})= P(A^{\mathcal{O}^*,\mathrm{S}}\;\text{succeeds})$
where $\mathcal{O}^*$ is some modified oracle. However, I still don't see how in general these two probabilities are the same because other papers seem to use the same proof technique but they somehow assume that
$P(A^{\mathcal{O},\mathrm{Sig}}\;\text{succeeds})= P(A^{\mathcal{O}^*,\mathrm{S}}\;\text{succeeds})$
holds without any explanation. This could be probably justified using the computational indistinguishability, but then we would need a sequence of algorithms that we don't have.


texts: In RSA, given $n=100$ and $e=13$ ,Encrypt and Decrypt the plain Text "SECRET"

texts: Is this question valid as $n=100$ is not a product of two primes, but can be expressed as $100=2^2 5^2$, if valid is there any criteria for choosing $d$  and other values?


texts: Assumptions underlying the soundness of STARKs

texts:
STARKs have recently received quite a lot of attention due to their small proof size and supposedly simple assumptions.
The paper introduction itself seems to mainly state that their construction is solely based on collision-resistant hash functions.
However, further down in the paper they seem to require some conjectures related to reed-solomon codes (see conjectures B.16 and B.17 as well as Appendix D.3).

Can somebody explain these conjectures in simple words?
Are these conjectures crucially required for the asymptotic proof size that STARKs achieve or are they only required for some practical performance improvements?


texts:
I am reading BGV12 about BGV homomorphic scheme right now.But I am being stuck to understand Batching technique in this paper.

In Pack function (page 32),this paper feeds ciphertext $c_i$ and sk $s_1$ into $\sigma_{1\rightarrow i}()$ function,so $s_1$ and $c_i$ must be in ideal $\mathfrak{p}_1$.But I cannot figure out why they are elements of ideal $\mathfrak{p}_1$.


texts:
Is it feasible to have data encrypted at different levels of hierarchy

I'd like to encrypt an xml database (such as used in www.keepass.info) whereby two or more keys can exist. For example:

Key #1 decrypts the entire database file
Key #2 decrypts a subset of the database file

Is this technically possible/recommended? The reason I'm looking is that I currently use keepass for myself and I repeatedly get family members saying that they've forgotten their password and do I know what it is...so I would like them all stored in a master database file that we can keep on our home network storage


texts: Known text attack on Hash function (SHA 256 or SHA512)

texts:
I was thinking the below attack scenario on hash function. Let's assume that three binary numbers A(1000 bits), B(16 bits) and C(283 bits) are concatenated together and H(A||B||C) is generated using SHA256 or SHA512. Here, the attacker knows C. Knowing C, is it possible for an attacker to find A or B or (A||B) from the output H(A||B||C)? If yes, what are the attacks and how to prevent them?
Thank You.


texts: Confused with 128-bits AES round numbers

texts:
The key size used for an AES cipher specifies the number of repetitions of transformation rounds that convert the input, called the plaintext, into the final output, called the ciphertext. The number of cycles of repetition are as follows:

10 cycles of repetition for 128-bit keys.
12 cycles of repetition for 192-bit keys.
14 cycles of repetition for 256-bit keys.

  Each round consists of several processing steps, each containing four
  similar but different stages, including one that depends on the
  encryption key itself. A set of reverse rounds are applied to
  transform ciphertext back into the original plaintext using the same
  encryption key.

So 10 cycles of repetition for 128-bits keys. This are the rounds:

KeyExpansions—round

keys are derived from the cipher key using Rijndael's key schedule. AES requires a separate 128-bit round key block for each round plus one more.

InitialRound

AddRoundKey—each byte of the state is combined with a block of the round key using bitwise xor.

Rounds

SubBytes—a non-linear substitution step where each byte is replaced with another according to a lookup table.
ShiftRows—a transposition step where the last three rows of the state are shifted cyclically a certain number of steps.
MixColumns—a mixing operation which operates on the columns of the state, combining the four bytes in each column.
AddRoundKey

Final Round (no MixColumns)

SubBytes
ShiftRows
AddRoundKey.

So my question is: it says 10 cycles, but does that mean that the initial round is performed once, the normal rounds 9 times, and the final round also once? Because the expanded key is 176-bytes, so the addroundkey function can be used 176/16 = 11 times.

Can someone give me help on the correct division of cycles on the 3 times of rounds (initial, normal, final)?


texts: What is perfect collision-resistence in probability terms?

texts:
update: removed lots of stupidity... sorry. I didn't know I can be this stupid but I achieved it.

1. Goal

Let $\mathcal{D}$ be the universal space of our plain data. Our goal is to find a function $h:\mathcal{D} \rightarrow \{1,0\}^n$ where $n$ is some positive constant, such that:

For any $d_1,d_2 \in \mathcal{D}$, the probability that $h(d_1) = h(d_2)$ is $1/2^n$. I.e. it's very unlikely to have collisions.

Note 1: the reason I require the probability to be $1/2^n$ is because I think this is the minimum possible collision probability. I would also appreciate if anyone could correct me on this.

2. Questions

Is $1/2^n$ the minimum achievable probability for collisions on any dataset?
Any of my methods are perfect for any dataset? I.e. not just best on average, best on specific datasets as well.
Can you propose one that is perfect on all dataset? (would be great if you can describe it in probability terms too).

3. My attempt

Let $z:\mathcal{D} \rightarrow \mathcal{Z}$ be a function such that for any $d\in\mathcal{D}$:

There is a function $u$ such that, for any $d\in\mathcal{D}$, $u(z(d)) = d$.
$\texttt{len}(z(d)) = H(d)$ where $\texttt{len}(z(d))$ is number of bits in $z(d)$ and $H(d)$ is Shannon's entropy of $d$.

I.e. $z$ is a perfect lossless compression function.

Ideally, we wish if $\texttt{len}(z(d)) \le n$ is always achievable. This way we can use $z$ as a perfectly collision-free implementation of $h$.

But in reality we can't do that as some input $d$ could contain too much information to be represented losslessly in $n$ many bits.

For simplicity, we will assume that, for any $d \in \mathcal{D}$, $\texttt{len}(z(d)) \ge n$.

This way, if the perfect compression function $z$ is known, then finding the perfect collision-free hashing function $h$ is a matter of choosing which of the bits in $z(d)$ to be kept in $h(d)$.

The process of deciding which bits to be kept in $h(d)$ needs to only satisfy:

For any $d_1,d_2\in\mathcal{D}$, probability of $h(d_1)=h(d_2)$ must be kept $1/2^n$.
The process must be producible. So computing $h(d)$ now should give us the same output if we compute $h(d)$ later on in the future.

3.1. Choosing $n$ bits method 1

For any $d\in\mathcal{D}$, assume that the early bits in $z(d)$ are more important than the latter bits in helping us set  $d$ apart from others in $\mathcal{D}\setminus\{d\}$.

Therefore, since early bits are most important, we just choose the first $n$ bits. I.e. $h(d) = z(d)[1:n]$, where $z(d)[1:n]$ denotes to the first $n$ bits in $z(d)$.

Note 4: I implemented this in Python here (in case one day someone [me included] wishes to evaluate these hashes against others to see how bad they are).

3.2. Choosing $n$ bits method 2

Unlike method 1, here we assume that any bit is equally important to any other bit. So instead of choosing the first $n$ bits in $z(d)$, we choose the $n$ bits randomly from $z(d)$. In order to make this reproducible, we seed the random selection by $z(d)$ itself.

In Python-inspired notation, it looks like this:

First we set the seed of the PRNG $\texttt{random.seed}(z(d))$.
Then we $z_{\texttt{shuffled}}(d) = \texttt{random.shuffle}\big(z(d)\big)$.
Finally $h(d) = z_{\texttt{shuffled}}(d)[1:n]$.

Note 5: in my view if $z$ and the PRNG used in the random shuffling are perfect, then this method is a perfect collision-resistant hashing function under this assumption which states that all bits in $z(d)$ are equally important.

Note 6: I have coded this in Python and it can be found here.


texts: Constructing an integer with specific totient without factorization

texts: Given $N(=pq)$, but not its factorization. Somehow you manage to know, that $k$ divides $\phi(N)$. Is it possible to come up with an integer $N^{*}$, for which $\phi(N^{*})=\phi(N)/k$, without factoring $N$?


texts: How to determine if a protocol is a Zero knowledge proof

texts:
If the given protocol is non interactive then how can one prove that the modified protocol is complete and determine whether it is zero-knowledge?
Let $N = p q$ as in an RSA algorithm, with $\text{gcd}(e, \phi(N)) = 1, e$ prime. $P$ wants to prove knowledge of $x \in \mathbb{Z}_N$, where $y = x^e$ is public. $P$ chooses $r \in \mathbb{Z}_N$, and calculates $a = r^e \bmod N$, and sends them to the verifier $V$. $V$ sends $0 \leq c \leq e - 1$ to $P$, and $P$ calculates and sends back $f = rx^c \bmod N$. $V$ accepts this proof if $f^e = ay^c = r^ex^{ec} = (rx^c)^e$.


texts: As far as I know there are two padding mechanisms, which are PKCS 5 and 7. Which one should be used for CBC?


texts: Does keeping a PGP crypted message private helps?

texts:
In other words, if I make a PGP crypted message publicly available, do i compromise its security?

In other words which encryption level would guarantee me, say, 20 years of security?

Additionnally, if i keep a bunch of PGP encrypted message with the same private key public, would it helps eventual hackers to decrypt them ?


texts: Why I can get a key from frequency in Caesar Cipher?

texts:
I took a cryptanalysis class in university and I learned Caesar Cipher. But I cannot understand why frequency gives me the "key".

In a meterial, the following sentences are explained:

  When Eve tabulates the frequency of letters in this ciphertext, she
  gets: I=14, V=13, S=12, and so on. The most common character is I with
  14 occurrences. This means key = 4.

What I cannot understand is the last sentence, "This means key = 4". Most frequency alphabet is "E" which has 12.7 frequency and the number of "E" is 4 I know. But how can I compute it from the frequency? I want to totally understand this mechanism.


texts: OpenSSL DES encryption for KCV calculation

texts:
I'm trying to implement a simple command-line tool to calculate the (Key Check Value) KCV of some encryption keys. The algorithm for the KCV is simply to encrypt a block of 8 zeros with DES and get the first three bytes of it (this is called VISA KCV, and there are a bunch of other KCV algorithms).
So, I wrote this code:
/*----------------------------------------------------------------------------*/
static void
str2DES_cblock_(const char *str, DES_cblock* out)
{
    // Make a char pointer and point it at the start of the array
    unsigned char *o;
    o = out[0];
    // Read the string
    int i;
    for (i = 0; i < 8; i++)
        sscanf(&(str[i*2]),"%2hhx", o++);
}

static int
getVisaKcv_( const char* key, const int keyStrLen, unsigned char* kcv )
{
    DES_cblock key1, key2;
    DES_key_schedule keySchedule1, keySchedule2;
    DES_cblock encryptedBlock;

    int rc = EXIT_SUCCESS;

    static const_DES_cblock blockToEncrypt_ = { 0x00, 0x00, 0x00, 0x00,
                                                0x00, 0x00, 0x00, 0x00 };

    memset( encryptedBlock, 0x00, sizeof(encryptedBlock) );

    if( 16 == keyStrLen )
    {
        str2DES_cblock_( key, &key1 );
        DES_set_key_unchecked( &key1, &keySchedule1 );
        DES_ecb_encrypt(
                            &blockToEncrypt_,
                            &encryptedBlock,
                            &keySchedule1,
                            DES_ENCRYPT
                        );

        kcv[0] = encryptedBlock[0];
        kcv[1] = encryptedBlock[1];
        kcv[2] = encryptedBlock[2];

    }
    else if( 32 == keyStrLen )
    {
        str2DES_cblock_( key,    &key1 );
        str2DES_cblock_( key+16, &key2 );

        DES_set_key_unchecked( &key1, &keySchedule1 );
        DES_set_key_unchecked( &key2, &keySchedule2 );

        DES_ecb2_encrypt(   &blockToEncrypt_,
                            &encryptedBlock,
                            &keySchedule1,
                            &keySchedule2,
                            DES_ENCRYPT );

        kcv[0] = encryptedBlock[0];
        kcv[1] = encryptedBlock[1];
        kcv[2] = encryptedBlock[2];
    }
    else
    {
        rc = ERROR_INVALID_PARAM;
    }

    return rc;
}

It uses OpenSSL's functions to perform encryption. The things is that it is giving me wrong results. For exemple, encrypting "19c7221b33c1b2b4c68bc48deb86234b" results in encryptedBlock = [ 33 4D 78 7E FB C0 ED E8 ]. Some high quality validation tools I have (it is called BP-Tools and works for all things payment-industry related) gives encryptedBlock = [ 90 D4 49 08 A7 9F 45 44 ] as result. I'm not sure where the problem is (it is a very simple encryption). Did I forget something in the sequence of OpenSSL API calls? It gives wrong results for 8-byte keys also.
Here are some test cases (they match both EFTLab's and BP-Tools results):
Enc( plaintext=[0000000000000000], key=[9be8ec942f9f7791]                   )   = [F4E94D2A2901D6C6]
Enc( plaintext=[0000000000000000], key=[6afbadf94fd06945d365856382898c25]   )   = [F65EC8B0B78F2C0A]
Enc( plaintext=[0000000000000000], key=[8f40053aae44e017]                   )   = [4A83D7F98644363E]
Enc( plaintext=[0000000000000000], key=[19c7221b33c1b2b4c68bc48deb86234b]   )   = [90D44908A79F4544]
Enc( plaintext=[0000000000000000], key=[b0e9c35e20171642]                   )   = [7FBA49A7CD6A8AEB]
Enc( plaintext=[0000000000000000], key=[a12815befca06412f357db3ab41d7cf9]   )   = [67F735CD1696E114]
Enc( plaintext=[0000000000000000], key=[e5c82dbe8c0b3c17]                   )   = [4CACBD023C95FD7C]
Enc( plaintext=[0000000000000000], key=[c74b48ebfa79f8ca46d06f8436597230]   )   = [7FD3FA9F5B338E13]


texts: Is there a straightforward way to employ NIST Statistical Test Suite for testing a biased generator (e.g. with 0.6 probability of 1)? By straightforward way I mean one not requiring nontrivial code modification.


texts: Show all the messages exchanged between Alice and Bob using the three-pass Diffie-Hellman protocol

texts:
PROBLEM STATEMENT:
"Suppose that users Alice and Bob carry out the 3-pass Diffie-Hellman protocol with p = 101. Suppose that Alice chooses a 1 = 19 and Bob chooses b 1 = 13. If Alice wants to send the secret message m=5 to Bob, show all the messages exchanged between Alice and Bob."
OFFICIAL SOLUTION:
"Ans.
a_2 = (a_1)^(-1) mod (p-1) = 79
b_2=77
Alice -> Bob m^(a_1) mod p =37
Bob -> Alice 80
Alice to Bob 56
Bob obtains m by evaluating 56^(b_2) mod p =5"
MY QUESTION:
I'm having a hard time finding information about the three-pass Diffie-Hellman protocol (not to be confused with the regular Diffie-Hellman algorithm or other three-pass algorithms, which is what keep showing up in my searches).
Could someone please point me to at least one good resource that could help me figure out how to do this type of problem, but ideally also explain to me what the (official) solution is doing for this problem?
Any input would be GREATLY appreciated!


texts: How to jusify {e,n} is a valid RSA public key?

texts:
I have a  two set of key {36,77} and {50,117},

How can validate if it is a valid RSA public keys?
Is there any simple method?


texts: Is it possible to carry out multiplication of BGW protocol without communication?

texts:
I read the following famous two papers related to multiparty computation and I have a question like title.

[AL17] Gilad Asharov, and Yehuda Lindell. "A full proof of the BGW
protocol for perfectly secure multiparty computation." Journal of
Cryptology 2017.
[CDI05] Cramer, Ronald, Ivan Damgård, and Yuval
Ishai. "Share conversion, pseudorandom secret-sharing and
applications to secure computation." Theory of Cryptography
Conference 2005.

In [AL17], authors constructed a protocol that privately computes multiplication given access to the randomization functionality and the degree-reduction functionality. While they also proposed a secure degree-reduction protocol (i.e. protocol to privately compute degree-reduction functionality) without communication, the proposed randomization protocol (i.e. protocol to privately compute randomization functionality) needs n^2 communications.

Authors of [CDI05] showed that a proposed protocol (PRZS) can create a pseudorandom zero-sharing with degree 2t (i.e. the randomization protocol) without communication.

Therefore, I’m wondering whether it is possible to carry out multiplication of BGW protocol without communication if the randomization protocol of [AL17] is replaced by PRZS protocol of [CDI05]. (Except for the communication of input sharing stage and output reconstruction stage)
Moreover, given an application consisting of addition and multiplication, is it possible to construct a multiparty computation protocol based on BGW without communication?


texts: How many bits to flip in an RSA public key to do signature forgery?

texts:
Scenario: Alice wants to verify a signature from Bob. Alice knows Bob's RSA public key (e, n). However, Alice is getting the data, the signature of the data and the public key from an attacker Eve. Assume the signature is compliant with PKCS# v1.5.

Now I know trivially Eve can generate an RSA key pair and signs the data herself and send the fake public key and fake signature to Alice. But I am going put a constraint on Eve. Eve cannot generate whatever key pairs she likes. Even has to flip the (e, n).

My question: What is the least number of bits she needs to flip in (e, n) such that she can forge the signature?

NOTE: she can either generate a signature from Bob's private key or she can generate a signature from some other private key she can compute from the corrupted public key or whatever attack she can come up with. As long as she can convince Alice the signature is from Bob.


texts: Private evaluation public quick verification VDF

texts: Does anyone know of any VDF, that can be calculated by someone holding some private key in t sequential steps and is quickly verifiable in exponentially reduced step by anyone using some public key and the proof that does not leak the key ? Like opposite of RSA timelock question. A link to some paper would help. can someone tag vdf, posw and blockchain in it? I don't yet have privileges.


texts: Best Asymmetric Encryption Standard for Communications?

texts: I'm new to the standards of encryption.  I understand the math behind RSA really well.  I'm wanting to design an application for private peer to peer communications using RSA and wanted to know what the best standard to use is.  I want the highest level of security, regardless of efficiency or wait times.


texts:
Some background:

I receive data in text files of over 16 million records (lines). I need to be able to encrypt the first column in that file so that it cannot be deciphered. This process will be carried out on two data sets with the same first column. The encryption on both these separate files will allow the two sets of data to be joined together on the encrypted column. One of these files is from our company and the other is a different company. When the join process is complete the column can be deleted. My boss wants a standalone application that can do this as it cannot be guaranteed that when we go offsite the company will have that software. He wants the encryption to be able to be carried out on the companies pc so that before we receive the data that column is encrypted.

Any help is appreciated.

EDIT

It's hard for me to describe this idea to you so bare with me.

Basically it will be one application that accepts a text file as input (this is because different sources will have different software and text files are the standard that everyone knows). The user then inputs a password and/or padding string for the encryption and then the application will encrypt the specified number of charters on each line of the text file and output that to another text file.

Example of input data:

|    ID    |    FName    |    SName    |    Number    |    Pcode    |
---------------------------------------------------------------------
|5364gfyue8|    Jason    |    Young    |   65782947   |   BT753HY   |
---------------------------------------------------------------------
|8472hgiek5|     Ben     |    Tops     |   87385942   |   BT439ES   |
---------------------------------------------------------------------
|0243hgqwl4|    Philip   |   Moore     |   73894769   |   BT641II   |

Example of output data:

|    ID          |    FName    |    SName    |    Number    |    Pcode    |
---------------------------------------------------------------------------
|85hftFHDYTE*=jcg|    Jason    |    Young    |   65782947   |   BT753HY   |
---------------------------------------------------------------------------
|5jgj59GUF55=hf4!|     Ben     |    Tops     |   87385942   |   BT439ES   |
---------------------------------------------------------------------------
|jhIOPfd5GF^83=3c|    Philip   |   Moore     |   73894769   |   BT641II   |


texts: RSA Digital Signature vs Elgamal Digital Signature

texts:
What are the advantages of RSA signatures against ElGamal signatures?
Is there a situation in which it would be better e.g. to use RSA signatures?


texts: Partial key reuse in hash for one time pad cipher

texts:
There are 2 computers who are going to exchange lots of small packets of data between each other. To generate a shared secret, an elliptic key exchange takes place. If this key is hashed with the current time, and the data is then encrypted with this key via a one time pad cipher algorithm, and then the time is sent with the encrypted data so the other computer can create the same key to decrypt the one time pad cipher, is their any security vulnerabilities??

The key and data would be like so (for encryption):

SharedSecret genreated from elliptic curve key exchange
Key = Hash(SharedSecret + Time)
Message = OneTimePadCipher(packet data, key) + Time

Are there any vulnerabilities with reusing the same elliptic curve shared secret with a different time in the hash algorithm to create a one time pad key??


texts: How to prove document ownership at a specific time

texts:
Problem
Given any piece of data, I could sign it with public key and made available online. This proves I am in possession of given data, but it doesn't tell I am the creator. The only possibility (I'm aware of) to prove this, is to prove, that I was chronologically first to have it.
Simple approach.
Lets assume, that I wrote piece of code, and I want to generate some proof, that I am legitimate author of it. I can simply sign it's hash with e.g. RSA and put the signature along source code to some trusted site, like github. Now my commit has timestamp generated with this trusted site, and even if some Alice would sign herself the same source code, her upload to any trusted site will have newer timestamp proving she's not the legitimate author. This works as long as we'd assume data on github has undetermined life span and will be always available which is hardly true about any server out there. When that commit would be lost, my rights to the source code are lost as well: I might still have my local signed copy, but I cannot prove I've created it at given time.
My understanding of the problem.
I believe there is no possibility to self-authenticate, that I were in possession of given data at specific time - I could just made up arbitrary timestamp and sign it. Moreover, anyone out there could get my publicly available data, replace personal data with their, made up older timestamp and call me thief. Thus, sign from trusted server is needed.
Trusted timestamp
My idea of the mechanism is as follow: sign source code, optionally append personal data, generate hash and send this hash to trusted server. Then this server would have to send me back signed information, that it received hash H at time T. This way I've got publicly accepted certificate, that I've got file with hash H at time T. Even if the server had go down, I would still have the certificate.
Question
So is the "trusted timestamp" good solution to the legitimate author problem? Do you know of any available open source tools to achieve this goal? Maybe other techniques? Assuming, I want to public code/publication/anything else licensed for non-commercial use only, should I be concerned with such issues?


texts: Is SHA1 secure with such many inputs Z that Z = constant secret X + variable public Y?

texts:
Let me ask whether SHA1 is designed to be secure for the following case.
You compute each SHA1 of many strings,for example 1 million, where each string is a concatenation of X+Y ,
where X is secret and constant and Y is public and variable.

Thank you in advance.


texts: What is the name of an attack where the compromise of one key compromises the whole system?

texts:
Consider the following: A whole system depends on the security of one private key and if this key is, for any reason, compromised, the whole system will be compromised.

What's a suitable name for such an attack?


texts: Semantic security IND-CPA of Affine Hill Cipher

texts:
The ciphertext $c$ corresponding to plaintext $m$ is given by
$c= mK + w$. $K$ is the invertible matrix and w is the uniformly distributed random vector.
If $w$ is changed during every encryption, will this affine Hill cipher satisfy IND-CPA?
If $w$ is generated using a PRNG and this type of encryption is used as homomorphic encryption keeping $K$ same, will it still provide IND-CPA?
During decryption, $w$ should be subtracted from ciphertext first and multiplied with the inverse of $K$. For decryption, the key for the PRNG (LFSR based) can be used.
$(m1 + m2) = [(c1 + c2) - (w1 + w2)]K^{-1}$


texts: implication of tweak on bruteforcing a block cipher

texts:
Consider a KPA attack, where the attacker gets known plain text and the corresponding cipher text. Since the encryption algorithm is known, he can brute force all possibilities of key bits. What is the implication of having additional tweak on brute forcing the algorithm?

Is this correct to say that now the attacker must try $2^k * 2^t$ possibilities, thus increasing the effort required to break the algorithm and so making it more secure?
(where k is number of bits in key and t is number of bits in tweak).

Edit: Assuming tweak is kept secret . And also that my application prepends the tweak string to the plain text while encrypting it , $AES_K(Tweak || plain ) $. Is my above assumption correct ?

Edit 2 : The AES in above is being used as a PRF in Luby Rackoff Construction like any other Format Preserving Encryption mode. So the AES is not exactly an encryption of the plain text but right half of the Feistel Network .(Honestly apologize for multiple edits)


texts: Smallest 256-bit security hash-based OTS?

texts: What is the smallest hash-based OTS in terms of the sum of the public key and signature which provides 256 bits of security?


texts: What are the capabilities of passive and active adversaries?

texts: I have trouble understanding what exactly the capabilities of passive and active adversaries are on paper and in the real world.


texts: Is differential calculus related to RSA?

texts: I'm writing a high school math paper on RSA and I'm wondering if it's possible to relate calculus to RSA. Is calculus used for any part of RSA? It can be for proving equations/theorems, for generating keys, for cracking RSA, etc.


texts: Is anyone using Half-Bit encryption? What is it used for now?

texts:
Long ago I learned about an encryption scheme which uses a random mask of bits which were "half on". I don't recall all the details, but basically, if a mask bit was a one, the input bit was passed through, if not the output bit was random. So, the decryption would lose information (it was nondeterministic) but for something like an image, which could still be recognized if degraded (or text read from a noisy image), it was "good enough".

Is this being used for anything these days? Does this technique have good qualities that other encryption methods do not? I was able to find only one paper online by searching on "half-bit encryption" and I am not certain it describes the method I am remembering. Perhaps I am using the wrong name?

One potential application is for monochrome images. For example, I store an image of myself passed through this filter: it looks like noise. I can use the mask to reveal a picture of myself to someone, but no one else can. Or, I carry the output file with me, and only someone with the mask can reveal the photo and see that it is me: a form of identification. It would have to be read by eye, of course, so this is not a way to send files across the internet or something. But not everything that can be digitized is digits, so to speak. ("Not everything that counts can be counted, and not everything that can be counted counts." - Einstein)


texts: "Fine grain Cross-VM Attacks on Xen and VMware are possible" and OpenSSL 0.9.7

texts:
Here's a paper that just made its way into Cryptology ePrint Archive: Fine grain Cross-VM Attacks on Xen and VMware are possible!.

Its a good survey of past attacks and presents a couple of new techniques for AES against OpenSSL, PolarSSL and Libgcrypt.

Why did the authors use OpenSSL 0.9.7? That's from 2007, and I don't believe its even supported any longer.


texts: Please help a complete noob with deniable encryption!

texts:
I am completely new to cryptography and am interested in encrypting two basic text strings into one encrypted text that can be accessed separately with two different keys (preferably using something easily accessible like 256bit AES). For example:

Text1= I like peanut butter

Key1= Password1

Text2= I'm allergic to peanut butter

Key2= Password2

Output: 5UniWN0MjkPvUbLImrQUP68W4tpwOBMp2nrDqV73xeY

This output is just Text1+Key1, but is there a way that I can get both to work simultaneously so if Key1 is used, Text1 is returned, but if Key2 is used, Text2 is returned?

From my understanding, this is called deniable encryption and I was wondering where I could find a generator.

Thanks so much in advance!


texts:
Is there a floating-point CSPRNG that operates, natively, using floating point operations?

Looking for a CSPRNG that's very fast on GPUs, and would be hard for a CPU to beat.

EDIT: Floating point doesn't matter too much.   Specifically, I'm looking for something for which GPUs or FPUs are, by far, the optimal hardware to use: as opposed to custom hardware, because the operations used are already heavily optimized on GPU.

My understanding is that floating-point-operations (FLOPS) are probably the best candidate here.    (It seems to me that most chaotic attractors can be trivially run using FLOPS.)


texts:
Homomorphic cryptography is a kind of cryptography that allows you to do special math operations on the ciphertext, and the maths performed are identical to the obvious ones. For example, one person can combine two cached numbers, and decode the result, the sum will be two numbers.

What is the purpose of Homomorphic encryption?


texts: Reductionist proofs of decisional problems to computational

texts:
Are they any reductionist proofs where an attacker $\mathcal{I}$ for a well established computationally "hard" problem $\mathsf{Π}$ is employing an attacker $\mathcal{A}$ who we assume is able to break a decisional problem $\mathsf{Γ}$ (i.e: semantic security->guess if $b=1$ or $b=0$) in order $\mathcal{I}$ to break $\mathsf{Π}$ and if so to conclude that $\mathsf{Γ}$ is as secure as $\mathsf{Π}$, meaning that if there exists $\mathcal{A}$, we can build $\mathcal{I}$?

Further explanation:

Typically when there is a reduction to a decisional hard problem then in your construction either you model your security with an adversary that  breaking the system means that the attacker should compute something or it has to distinguish something (indistinguishability games in order $\mathcal{A}$ to guess $b$ from an encryption of $x_b$). And this attacker is used as a subroutine by the well established problem attacker in order to break his scheme.

Let’s say that the attacker in our model is able to distinguish encryption $x_0$ from encryption $x_1$. This doesn't mean that the attacker is revealing the underlying key, nor that it has to compute something. It means that it can only distinguish. I have hard understandings how such attackers can be used as subroutines for well-established computational problems where an attacker $\mathcal{B}$ has to compute something instead of distinguish (or decide). And I would like to know if such reductions exist or if – from theory – you can never reduct from decisional to computational. I.e: CDH cannot use a DDH attacker to compute $g^{ab}$ but it is the other way around.


texts: Is 128-bit security still considered strong in 2020, within the context of both ECC Asym & Sym ciphers

texts:
Given that much of our ECC crypto primitives provide “only” 128-bit security when defined over a 256-bit curve due to pollard-rho, is it then still safe in 2020 to consider 128-bit security safe for the medium term (5-8 years).

I’m looking for an answer from an energy/thermodynamic POV given advances in current lithography and GPUs, rather than with regard to a specific cipher, however for discussion I consider AES-GCM or Salsa20 as example symmetric ciphers I use with 128-bit keys.

Bruce Schneier speaks of AES-128 in Cryptographic Engineering as if it’s already broken!


texts: How important is hardware based crypto in Quantum-safe TLS in mobile devices?

texts:
Microsoft Research  published an approach to Quantum-safe TLS here, namely RLWE-ECDSA-AES128-GCM-SHA256.

One highlight is that when it's used with ECC, there is only a slight performance hit.

Assuming this becomes a popular way to have quantum-safe TLS, how important is it that manufacturers optimize for this?... in other words, is a brand new CPU instruction needed, or will the existing cryptographic instructions be sufficient?

As a layman, I'm trying to get an idea how long it would take to get quantum safe TLS on a mobile device, where power and other constraints apply.

My assumption is if websites aggressively implement RLWE-ECDSA-AES128-GCM-SHA256, battery life and performance will suffer on most phones, until the hardware market catches up.


texts:
I am using a Python library called PyCryptodome, which offers the following API for AES-GCM ciphers:

https://pycryptodome.readthedocs.io/en/latest/src/cipher/aes.html

As you see, IV is not applicable for GCM ciphers.

There are some C++ libraries that expect the user to specify the IV rather than the nonce.

Let's say that I get a message encrypted with a C++ library that uses a 16 bit IV. Later on, I want to decode this message using a Python library. Given that I know the key and the IV that was used, will I be able to properly decipher the message when I specify the nonce to be the IV?


texts: Why is Byte-at-a-time ECB decryption a vulnerability?

texts:
I've been working on the Cryptopals Cryptography challenge problems, and I recently solved one where you recover a plaintext given a encryption oracle. The oracle produces a ciphertext in ECB mode AES.

You are given a base64 encoded piece of plaintext (encoded so that it isn't immediately human readable). The only thing you have control of is the plaintext you enter into the oracle. The key for AES is randomly generated each time, and you're not supposed to see it either.

More information on the problem here: Set 2, Challenge 12

What confuses me is that at the end of the problem a little box says

  This is the first challenge we've given you whose solution will break
  real crypto. Lots of people know that when you encrypt something in
  ECB mode, you can see penguins through it. Not so many of them can
  decrypt the contents of those ciphertexts, and now you can. If our
  experience is any guideline, this attack will get you code execution
  in security tests about once a year.

How can this vulnerability be used in real life? To crack the plaintext, you need access to it, as well as an encryption oracle (which contains the key). Is it ever possible to have this much control over a system? And if you did, why couldn't you just directly print out the plaintext or key?


texts: Randomizing output of HKDF for the same input key material

texts:
Given HKDF and a master input material key $k$, I would like to derive ephemeral keys that cannot be linked together. If I understand correctly, the specification of $HKDF$ adding a unique random $salt$ while generating each new ephemeral key should randomize the output. Is it the case?
An example: I have a master input key k (unknown to the adversary). I generate 10 ephemeral keys as $x_0 = HKDF(k, salt_0), x_1 = HKDF(k, salt_1), \ldots , x_9 = HKDF(k, salt_9)$. And $x_0 \neq x_1 \neq \ldots x_9$.


texts: One Time Password generation algorithm to ensure data/transaction integrity?

texts:
Here is my use case:

A user is trying to transfer money to his friend's account. He enters transaction details on banking website. Bank receives it and then
Bank sends transaction details (receiver name and amount) + One Time Password back to the user (may be through different channel : mobile) so that user can verify the transaction details (this is to ensure transaction integrity. ie., no man-in-the-middle attack) and enter the OTP to confirm the transaction.

What is the threat model?

Man-in-the-middle attack. If an attacker (in middle)  modifies the receiver's bank account details with attacker controlled bank account but shows fake transaction summary, the OTP that sent along with the transaction details should become invalid.

What OTP generation algorithm should I use?

   someOTPgenAlgo(transaction details) = OTP.

Now if the attacker changes the receiver bank account details, he also has to find the matching OTP for that modified transaction details Which should be impossible. How do I achieve this? Is following enough ?

someOTPgenALgo(transaction details + some random key ) = OTP

Thanks a lot. Sorry if the question is naive, I am pretty clueless about this


texts: Can this AES encryption operation be described as being Homomorphic operation?

texts:
Am doing some work on privacy preserving classification on encrypted dataset. Pls really need a clarification.
I encrypted a dataset (plaintext) with AES scheme and get a cypher text.
I was able to use a machine learning tool WEKA to do a data mining operation(train and classify) on the cypher text
I decrypt the cypher text and discovered that the decrypted result matches the one I obtained when the same operation was performed on plaintext.
Can this operation be termed Homomorphic?


texts: How would I make a secret notation alphabet more secure?

texts:
Disclaimer: I was looking for a place to ask this question on SE and this site seems to be the most fitting. If this question doesn't belong here, feel free to redirect me.

Just out of boredom and curiosity, I've started to develop my own secret notation alphabet (for manual use, no computers involved). It's based on Elian Script, although I scrambled the letters in a non-obvious way (no ROT13 or similar) and expanded on the form a bit. I still feel as if it wouldn't be that hard to "decode" my notations, though.

So my questions would be:

what further methods are there for making an alphabet 'safer', except using different letters and scramble them?
what methods are there for text-encryption that could be used for manual everyday use? (like leaving out punctuation, for example.)


texts:
I found terms like "forward secrecy", "future secrecy", "backwards secrecy" and "perfect forward secrecy" and I would like to know their definitions and to understand the differences among them.
I found several confusing definitions online, especially mixing up the meanings of forward secrecy with perfect forward secrecy, or the meanings of forward with backwards secrecy.
Thank you.


texts: Can I generate same random number given same entropy value?

texts: Given the hypothetical fact that I can predict the same entropy value used to generate a random number, can I generate the same random value, say in a Windows based python application?


texts: Would it possible to decode an intelligible but alien message?

texts:
I've been reading some sci-fi and there is a frequent mention of decoding alien signals.

From what i read historically in ww2  for decoding enemy message the allies would transmit fake information and then listen to the enemy communicating that fake messages in encrypted form , this enabled the allies to make sort of a known plaintext attack and in addition they had an idea of the ciphers being used which narrowed down area of effort even more

Now to make this question realistic let's say the message contained information which is intelligible to humans in plain text (say if the aliens were sending  encrypted English) then is there a way to decode a encoded signal when you do not know about its purpose or context or cipher?

Say you just received an out of ordinary signal from somewhere in cosmos , with definitely has a pattern indicating intelligent origin but nothing more.

Is it possible to decrypt such a message?


texts: How is pre-image resistance defined, formally?

texts:
Earlier today, forest asked in our chat, The Side Channel whether the definition of first pre-image security actually requires that an input that evaluates to the challenge hash result must be known to exist a-priori.

This got me thinking. How does one actually, formally define first pre-image security for hash functions?

This is also motivated by the fact that formal definitions are crucial in cryptography to actually understand what is needed to break security. For example, the RSA problem isn't "given $c$ that was constructed as $c=m^e\bmod n$, find $m$" but rather requires specific properties from $n$ (by requiring correct key generation) and requires correct choice (uniformly at random) of $m$ as well.


texts: Would XOR'ing two Argon2 keys add extra security?

texts:
When a user registers on the app, they need to provide a password they create and we provide them with a randomly generated passphrase (e.g. Apple Cat Ladder Fire). We then use Libsodium's crypto_pwhash() to generate a key for both the user's password and the generated passphrase.

Since most users will use a low entropy password, the goal was to combine it with a higher entropy source to derive a master key using the crypto_kdf_derive_from_key() function. This master key only exists to wrap/unwrap the user's private key.

I was wondering if XOR'ing these two keys actually has any benefit or am I chasing my own tail?

I also added the XOR function I wrote in Kotlin (There isn't a native implementation that I'm aware of) to see if I'm actually XOR'ing the keys properly.

fun xorKeys(keyOne:ByteArray, keyTwo:ByteArray): ByteArray {
    // Check to make sure both keys are the same size
    if (keyOne.size != keyTwo.size)
        throw Throwable("Key sizes don't match")

    // Create a new key handle
    var newKey = ByteArray(keyOne.size)

    // XOR individual bytes
    for (i in keyOne.indices) {
        newKey[i] = keyOne[i] xor keyTwo[i]
    }

    // Return the new key
    return newKey
}


texts: Same message space for different public exponents

texts:
What is the weakness, if there is any, of using the same message space for different public exponents (assuming e changes everytime)?

Imagine I have a message space [0,n] where n is a 1024 bit number and several public exponents of 1024 bit each as well, does that somehow have an impact on my RSA system?

Edit: assume I don't have access to n in this scenario (unless "message space" refers to n. However, in this case we assume that the given message space is a composite number with > 6 prime factors)


texts: How to clock a linear feedback shift register?

texts:
I have some trouble understanding what happens when a LFSR is clocked. I have tried many examples but I do not get the correct result. Can anyone point out my errors?

I have the following polynomial:

$$f(x)=1+x+x^5+x^6+x^8$$

I am working on this as a part of a known plaintext attack and I have the following keystream:

01010101000110101100

So, the first 8 bits of the keystream must be the IV for the LFSR, and the LFSR should do XOR on third ($x^2$), fourth ($x^3$), fifth ($x^4$) and seventh ($x^7$). In the next line the leftmost bit should go out and the rightmost the value from the XOR operation, the rest should be shifted one place from the line above, hence the structure:

$1 \times x^2 \cdots x^3 \cdots x^4 \cdots x^7$

0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 0
1 0 1 0 1 0 0 0
0 1 0 1 0 0 0 0

So, the rightmost bits in each line should be the continuing of the keystream after the 8th first bits, this seems to add up for the first three zeros, but after that it's not giving the keystream.

What am I doing wrong?


texts: Is there a proof for showing any cryptogram is crackable?

texts:
I commonly hear statements along the lines of "all cryptograms are crackable - it's only a matter of time".

Is there a proof to show that any cryptogram is "crackable"? The proof may be of a more philosophical form rather than relying on mathematical proofs. I really don't know what to expect, but would be fascinated by anything that could show empirically that all cryptograms are crackable (as opposed to a proof that all known strategies for encryption are crackable)

Related: Is it enough to say that given enough time and resources, all brute-force attacks will eventually succeed?


texts: Is SSH public key authentication weakened by 'none' cipher?

texts:
As far as I know, SSH2 first does a key exchange based on the server host key and brings up transport authentication and encryption derived from this kex. The real authentication (password or public key) is done over this secure transport.

If you set the cipher to 'none', you wouldn't want to allow password authentication because then the password would be sent in plaintext. But what about public key authentication?

I believe pubkey auth works by the server sending a nonce to the client, the client signing it with its private key, and the server verifying the signature. How is the overall system weakened if this exchange happens in the clear?

I can think of at least:

known-plaintext (passively capture (nonce, $D_k(nonce)$) and try to derive k)
chosen-ciphertext (intercept and replace the nonce, capture $D_k(chosen)$)

Is RSA (specifically, the way it's used by the raw SSH public key authentication) vulnerable to either of these?

Edit: my original formulation was incorrect: RSA signs by decryption, not encryption. Which points to an attack on textbook RSA: How does a chosen plaintext attack on RSA work? but NOT on the RSA used in practice in SSH and SSL. PKCS#1 padding protects against this attack.


texts: Is encrypt-and-MAC secure for AES-CTR + UMAC?

texts:
OpenSSH will (especially in older versions) use AES-CTR plus a MAC in encrypt-and-MAC.  This is not secure in general (meaning that there exist secure ciphers and secure MACs such that using them in encrypt-and-MAC is insecure).

However, as I understand it AES-CTR + MAC as used in SSH is secure, at least for the MAC choices actually in use, because:

The MACs used (HMAC and UMAC/VMAC + encrypt the MAC tag) are
privacy-preserving: the MAC tag does not leak any information about
the plaintext, at least for one who does not know the MAC key.  In the
case of HMAC, I believe that this follows from HMAC being a strong PRF;
in the case of UMAC/VMAC, the security of the MAC depends entirely on
encrypting the MAC before transmission, and the encryption of the MAC
also ensures that no information about the plaintext is leaked.
No encoding is done between encryption and authentication.  The data
that is encrypted and the data that is authenticated are one and the
same.
The cipher in question uses CTR mode – in other words, it is a stream
cipher.  Thus, any change to the ciphertext will cause a 1-to-1 change
in the plaintext – integrity of plaintext thus implies integrity of
ciphertexts.

My conclusion is that these cipher suites are actually secure, due to the specifics of the protocol.

Is my reasoning correct?  More importantly, is my conclusion correct?  I am not a cryptographer and have zero trust that I did not make a foolish error.


texts: Avoiding overflow when encrypting with RSA

texts:
When encrypting with RSA one calculates $ m^e \pmod n $ by doing the following:

m^e % n

Where $m$ is what we encrypt. Often $e$ is a very big number to make it more difficult to crack.

So how does one avoid overflow when encrypting?


texts: What is purpose of a simulator and extractor in zero knowledge proof protocols?

texts:
I am new to zero knowledge proofs. I read the paper Efficient Protocols for Set Membership and Range Proofs by Jan Camenisch, Rafik Chaabouni and Abhi Shelat.

The author proposed a zero knowledge set membership protocol in page 9. Then, he stated in theorem 1 that the the protocol is a zero-knowledge argument of set membership. Then, he explicitly said "to prove honest-verifier zero-knowledge, we construct a simulator Sim that will simulate all interactions with any honest verifier V. This is all detailed in Page 8 and 9.

What is simulator, and what is purpose of Sim? Is the Sim an adversary? What does "the extractor" mean? If you look at the paper, the simulator in Fig. 2 looks exactly to the proposed protocol in Fig. 1.


texts: Is it okay to include relative time for true random number generation?

texts:
Similar questions have been asked regarding use of time in true random number generation, but I'd like to consider using time as just one source of entropy, complementing others.

True random number generation relies on the mensuration of some physical stochastic process.  Electrons avalanche across depletion boundaries in essentially one dimension.  Polarised photons move in two dimensions, whilst rolled dice move in three.  All are potential sources of entropy whose measure in up to three dimensions is used to generate random numbers.

However space is four dimensional.  Rolling a 6 might be random, but isn't it even more precise to say it was a 6 at 7.49 am?  Some people say that as time is known it is unsafe to use as a source of entropy.  On my machine, Java can measure relative time to a precision of 350ns from boot time.  Allowing for a realistic boot duration variation of 10s, that allows for 7.5 decades of resolution.  Who can tell when my machine was booted? It might have been on for a year, so 7.5 decades of resolution is a conservative estimate.  And what if the numbers aren't consumed immediately, but cached somewhere ageing them? Bytes resulting from such a generator obviously have no associated time stamp.  This then adds at least another 7.5 zeros to the number of combinations of entropy, and consequently increases security.

When measuring a physical property, isn't it just as important to record when a voltage was measured as is the number of volts? The voltage is measured relative to a reference voltage, and surely it can be measured relative to boot time? After all, /dev/random uses timings for it's cryptographically secure output.

Supplemental:

After some testing, I found that the simple Java function

System.nanoTime() & 0xff

can generate entropy at a rate of 1.4mb/s surprisingly.  It varies in as still uncertain ways correlated with the system load.

Also, there seems to be a great effect when such entropy (call it Relativity) is mixed with another source.  So again based on experiments, the following was found (but I think requires further study - seems to exhibit behaviour reminiscent of superposition)...

H(weak source) = 0.039%

H(Relativity) = 2.2%

H(weak source XOR Relativity) = 32%

If Relativity is therefore combined with physical measurements, this seems to be low lying fruit, especially in an entropy deficient environment.


texts:
I was reading XMSS and I watched some of the presentations about it by Dr. Andreas Hülsing. But I cannot underdstand what is our motivation to use XMSS with 1 layer. Why is it better than MSS?
I know that in addition bitmasks are used and WOTS+ is used in stead of WOTS. But everything else seems identical. I cannot grasp what is the idea of such improvements.
Is it only, shorter signatures? As of here: Difference between XMSS and MSS-SPR.
Or maybe it is because condition are relaxed for the underlying hash.


texts: Is the commitment $g^u\cdot x$ with $x\in\langle g\rangle$ and $u \gets \mathbb{Z}_n$ hiding and binding?

texts:
Consider the following commitment scheme, where $x$ belongs to $\langle g\rangle$ and $u$ is uniformly chosen from $\mathbb{Z}_n$:

$$\mathsf{commit}(u,x) = g^u\cdot x$$

Is it binding and hiding?


texts: Are all homomorphic encryption schemes based on latticed-based schemes?

texts: PALISADE offers a pool of Homomorphic Encryption schemes and it is stated that "PALISADE is a general lattice cryptography library ...". My question is rather simple: are all homomorphic encryption schemes based on lattice-based cryptography?


texts: Generating ElGamal parameters in a mix net

texts:
I am reading this paper regarding re-encryption mix nets. I want to implement my own for educational purposes and I am stuck at the initial steps of how I should generate the keys and distribute them. The paper for this step says that

"Key generation: all decryption servers jointly generate
the parameters (q, g, x, y) of an ElGamal cryptosystem
in a group G of order q generated by g, using for
example the threshold key generation protocol of Pedersen
"

This whole step though seems to be more complex than I initially thought and I have failed to find any other implementations out there to study from. Can someone explain in simple steps the process of how the mix servers jointly generate the public and private parameters of an ElGamal cryptosystem?


texts: Is it feasible to break an encrypted and later encoded message?

texts:
A message is sent from a person to another. The plain message is first encrypted, even with a weak algorithm - say, DES. Then, the encrypted message is encoded with a simple substitution,  which is private and remains the same through all the conversation.

Is it feasible for an external attacker to decrypt the message, only knowing the encrypted message and the process (i.e. only that an unknown encryption and later an unknown substitution, both of which remain the same through all the conversation)?

The substitution algorithm, the encryption algorithm and any key the algorithms use are private and known to both the sender and the receiver. The substituted text may be longer than the non-substituted one.

My guess so far is that since frequency analysis can usually not be applied to encryption,  a simple substitution makes it infeasible to decrypt the text, provided that the map (knowing what is encoded to what) remains unknown


texts: Does anyone know why NISTs SHA3 256 output Hash for the 1600 bit file is different to other SHA3 256 output hashes?

texts: I have been trying to implement my own SHA3 256 function in python to try and learn and understand how it works. I have been comparing my hashes with an online sha3 tool found here https://emn178.github.io/online-tools/sha3_256.html and the test files on the NIST website found here https://csrc.nist.gov/projects/cryptographic-standards-and-guidelines/example-values. I realised that the output hash found in the 1600 bit file found on the NIST file is different from the one on the online tool. I have even used a python sha3 library and the result of the hash is the same as the one on the online tool. Does anyone know why the NIST output hash is different? I know NIST has made some changes to SHA3 padding but I am still unsure.


texts: Construction of a "simple", nothing-up-my-sleeves, provably KPA resistant symmetric cipher

texts:
Why is AES secure? Apparently there is no answer - Why is AES resistant to known-plaintext attacks?.
With this in mind, one would obviously want a cipher that is mathematically provable to be resistant to KPA. How would one go about constructing such a cipher? Has it been done? Can it be done? Is someone doing it? Why hasn't it been done? Can you blame mathematics atleast?
When I look at AES, I see a bunch of random up-the-sleeves operations, with, as aforementioned, mostly no explanation. Why can't there be a simple, efficient and secure algorithm to encrypt things?
Imagine a simple (e.g. xor) cipher with a 256-bit key that is applied to each 256 bit aligned block of the plaintext. Suppose it wasn't vulnerable to KPA and other attacks. Then it would be equally secure as AES-256, if not better, given the potential flaws of AES. Problem solved? Unfortunately not; contradiction.


texts: What's the advantage of using OFB/CFB/CTR modes over a stream cipher

texts:
As far as I understand:

The primary disadvantage associated with stream ciphers is the need for a random and unique key for each run in order to protect against reused-key attacks.
OFB/CFB/CTR block cipher modes turn the cipher into a stream cipher. Again, the IV/nonce should be random and unique.

What's the advantage of using the aforementioned block cipher modes over using a regular stream cipher (even though the latter would probably be faster)?


texts: Can I construct a zero-knowledge proof that I solved a Project Euler problem?

texts:
Is there a practical method, and if so what is the method, to reveal that I have the following type of answer but conceal the answer itself? The answer is, let's say, the solution to a Project Euler problem.

That is all. However, I'm new here. I'll try to explain why I hope this question will be considered appropriate. The explanation is a bit lengthy, maybe too defensive!

The question concerns implementing a specific information security system. To make that clear, I'll pose a birthday problem and the information to conceal will be the answer to that problem. Project Euler doesn't have any birthday problems, but it's not really so different from typical Project Euler problems. The Project Euler organizers believe that preventing widespread publication of their answers is vital to the goal of their project. Many Project Euler participants, including me, believe that it's valuable to convince people that we have solved the problems that we claim we have. (OK, I suppose we can also refer people to the Project Euler leaderboard, but how does anyone know that that is me?)

The specific problem is, what's the least number of people we must plan to select in order to have at least 95% confidence that five of our selected people will have their birthdate (day of the year) in common? Let the problem presuppose the usual sorts of silly assumptions: that birthdates are uniformly distributed throughout the year, no one is ever born on February 29, the world's population is effectively infinite, and we can do perfect random sampling from the world's population. The answer is just some number, possibly a big one.

Now, once I compute the number, can I publish information that proves that I have it without revealing its identity? I realize that there's no asymmetric computation involved. It's OK that others who know my birthday problem can solve it just as I did. It's not OK if others can get the answer from my information without even knowing my birthday problem. Crucially, I'm not sure what to say about people who do know my birthday problem but want to cheat by deriving the answer from my information instead of solving the birthday problem for themselves.


texts: Why ABAC access control model uses ABE not RSA or any other public key cryptography? Moreover what is the relation of ABAC with public key cryptography (ABE/RSA)?


texts:
We are trying to follow FIPS 186-2 for creating a  pseudo random number generator for EAP AKA AT_MAC Calculation in SIM Authentication:

Choose a new, secret value for the seed-key, XKEY
In hexadecimal notation let t = 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0. This is the initial value for H0|H1|H2|H3|H4 in the FIPS SHS [SHA-1]
Code:

For j = 0 to m - 1 do
    XSEED_j = 0 /* no optional user input */
    For i = 0 to 1 do
        XVAL = (XKEY + XSEED_j) mod 2^b
        w_i = G(t, XVAL)
        XKEY = (1 + XKEY + w_i) mod 2^b
        x_j = w_0|w_1

The algorithm requires the use of function G(t,c). We have gone through several SPECS but not found the correct definition of how to implement G(t,c).

At one place we have seen that G(t,c) is the same as SHA-1 except for some padding. But, it is not very clear. What is the G function in Implementation of FIPS-186-2 for EAP AKA AT_MAC Calculation in SIM Authentication?


texts:
Is there any advantage of using Tiger Tree Hash over any other hash function organized as the Merkle tree? Are there maybe any properties of TIGER that, say, SHA-2 or BLAKE in Merkle tree do not have?

And in general, is there any point of chosing Tiger Tree Hash over anything else in modern applications for file sharing purposes?


texts: What is batching in homomorphic encryption?

texts: I have been reading journals about FHE schemes and I keep encountering the term "batching". What does it mean to batch in homomorphic encryption in a simple way?


texts:
Alice uses an ElGamal signature in group $(Z/pZ)^{*}$ without using hash function. To sign the message $m \in (Z/pZ)^*$ calculates the signature $(r,s)$ as follows: choose random $k \in \{0, 1, \dots, q-1\}$ where $q/p-1$ is prime number and the order of the base $g$ and then calculates $r\equiv g^{k}\pmod p$  and $s\equiv k^{-1}(m+ar)\pmod q$ where $a$ is the private key of Alice.For $p=23$, $g=2$, $q=11$ you are given the signature $(18,3)$ in the message $m=2$. Construct a signature in the message $m'=3$ (without using the private key). The public key of Alice is $y=13$

Could someone give some hints on how to construct this signature in message $m'=3$?


texts:
Here is the post that explains the failure for doing h(k||m) and I understand it.

But I don't understand how h(m||k) is subjected to collison attack, or birthday attack. Please explain?


texts:
I am new to cryptography. I have question regarding the size of the set of random functions. I found the text from "Introduction to modern cryptography" by Katz and Lindell, in another thread which also relates to my question: Difference between Pseudorandom Function vs randomly chosen function

The text from "Introduction to modern cryptography" by Katz and Lindell (chapter 3.5.1) from the thread:

  Since the notion of choosing a function at random is less familiar
  than the notion of choosing a string at random, it is worth spending a
  bit more time on this idea. From a mathematical point of view, we can
  consider the set $\text{Func}_n$  of all functions mapping $n$ -bit strings to $n$
  -bit strings; this set is finite (as we will see in a moment), and so randomly selecting a function mapping $n$ -bit strings to $n$ -bit strings
  corresponds exactly to choosing an element uniformly at random from
  this set.

  How large is the set $\text{Func}_n$ ? A function $f$  is exactly specified by
  its value on each point in its domain; in fact, we can view any
  function (over a finite domain) as a large look-up table that stores
  $f(x)$  in the row of the table labeled by $x$ . For $f \in\text{Func}_n$ , the
  look-up table for $f$   has $2^n$   rows (one for each point of the
  domain $\{0,1\}^n$  ) and each row contains an $n$ -bit string (since the
  range of $f$   is ${0,1}^n$  ). Any such table can thus be represented
  using exactly $n\cdot 2^n$   bits.

  Moreover, the functions in $\text{Func}_n$  are in one-to-one correspondence
  with look-up tables of this form; meaning that they are in one-to-one
  correspondence with all strings of length $n\cdot 2^n$.

  We conclude that the size of $\text{Func}_n$  is $2^{(n\cdot 2^n)}$. ...

Assume $n = 2$

Than we have following mapping

00 00
01 01
10 10
11 11

00 11
01 00
10 01
11 10

00 10
01 11
10 00
11 01

00 01
01 10
10 11
11 00

if we rearrange so that each each row of $f(x)$ corresponds to each $x$. i.e. concatenating we will have following rows.

00 01 10 11
11 00 01 10
10 11 00 01
01 10 11 00

Each row will contain $n\cdot2^n$ bits. i.e. our case $2\cdot2^2 = 8$.
And according to my estimate(perhaps incorrect) total number of bits will be $2^n\cdot n\cdot2^n = n\cdot2^{2\cdot n} = 32$.

While text states the size is $2^{n\cdot2^n}$ i.e. $256$?
Could you please help me to find what I missed in my assumptions and where is my mistake?


texts: Counter Mode: static IV but different keys

texts:
Given we are using AES counter mode, suppose we randomly generate several keys, all of them are using same IV (say, zeros). Does this lead to any security issue?

I know that in CTR mode, same key-iv pairs would lead to two-time-pad. But the above construction will not have the same keys.

In application:

Let's say Alice and Bob communicate through TCP. They agreed on using AES-CTR. For each connection, they randomly generate a key but always use a static IV.

(BTW, all encrypted data will be HMACed)


texts: Associative standard cryptographic hash function

texts:
I am looking for a standard hash function which satisfies the following property:

A hash function $H(a,b) = F(h(a),h(b))$ with $h$ (within $F$) any standard cryptographic hash function and $F$ an associative function.

Is there any standard hash function(e.g. RIPEMD-160, SHA1) for which I can easily implement the associative function (like xor-ing or something similar)?


texts: Creating a small number from a random octet string

texts:
I'm trying to figure out the best way to generate a cryptographically secure random number between 0 and 200 (inclusive) from a cryptographically secure random string of bytes (ie. read from /dev/urandom or some such).

I could do random[0] % 201 but then numbers 0-54 would be more likely than 55-200 which would make the resulting number more predictable than it should be.

How can I use the random octet string to create a number in a range 0...k-1 (where k is 201)?