Are the functions S0, S1, E0, E1 from the SHA-256 algorithm reversible?

Question

Cryptography

Good afternoon everyone. Or evening. Or early morning.
In general, the topic is the question.
That is, is it possible to find for these functions such a function that for any
y=f(x) , it would be possible to find x through it , with known y ?
For example, to find a function F that will satisfy the condition X=F(S0(X)) It is
desirable to justify the answers.
Thanks in advance.

Answer 1

As an example, S0
rol is reversible, xor is reversible, right shift is not reversible. those. << (left shift) will give a number with zero low bits. So the expression itself is not reversible

Answer 2

A 16-bit function analogous to S0 (in terms of the parity of shifts) turned out to be bijective.
In this case, a change in parity leads to a violation of the bijection (as described by jcmvbkbc above)
Update:
1) to check the reversibility - you need to build a 32x32 binary matrix corresponding to the given transformation (in GF(2)), and calculate its rank; if the operation is reversible, then the rank should be equal to 32;
2) to construct an inverse function - invert the matrix obtained in paragraph 1.

Answer 3

Are the functions S0, S1, E0, E1 from the SHA-256 algorithm reversible?

Σ0 ( A ) = ( A ⋙ 2 ) ⊕ ( A ⋙ 13 ) ⊕ ( A ⋙ 22 ) is invertible.
Σ1 ( E ) = ( E ⋙ 6 ) ⊕ ( E ⋙ 11 ) ⊕ ( E ⋙ 25 ) is also invertible.
What is E0 and E1 I did not find.
A table of all the values ​​of S0 and S1 can be built in a few minutes if there are 16G of free memory. All of them are different, i.e. the reverse transformation is unambiguous.
Whether it is possible to find a simple inverse function is not clear.

Answer 4

I managed to reverse Σ0 (I didn't check all the values, but it processes the first 100000 as it should), I think that the rest can be reversed in a similar way. Call the DeSigma0 function.
Here is the C# code:

The code itself

class Sigma0
    {
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static UInt32 ROTL(UInt32 x, byte n)
        {
            return (x << n) | (x >> (32 - n));
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static UInt32 ROTR(UInt32 x, byte n)
        {

            return (x >> n) | (x << (32 - n));
        }

        private class Column
        {
            public Variable[] Cells { get; set; }
            public int Position { get; set; }

            public Column()
            {
                Cells = new Variable[3];
            }

            public void Solve(uint searchFor)
            {
                //if (ValuesCount() != 2)
                //    return;

                var withValues = Cells.Where(x => x.Value.HasValue).ToList();
                var withoutValue = Cells.First(x => !x.Value.HasValue);
                var searchBit = (int)(searchFor >> (31 - Position)) & 1;
                withoutValue.Value = withValues[0].Value ^ withValues[1].Value ^
                                     searchBit;

            }

            public bool Check(uint searchFor)
            {
                //if (ValuesCount() != 3)
                //    return false;
                var searchBit = (int)(searchFor >> (31 - Position)) & 1;
                return (Cells[0].Value
                        ^ Cells[1].Value
                        ^ Cells[2].Value) == searchBit;
            }

            public int ValuesCount()
            {
                int result = 0;

                if (Cells[0].Value.HasValue)
                    result++;
                if (Cells[1].Value.HasValue)
                    result++;
                if (Cells[2].Value.HasValue)
                    result++;

                /*
                foreach (var variable in Cells)
                {
                    if (variable.Value.HasValue)
                        result++;
                }
                */

                return result;
            }

            public override string ToString()
            {
                return $"{Cells[0]} {Cells[1]} {Cells[2]}";
            }
        }

        private class Variable
        {
            public int InputPosition { get; set; }
            public int? Value { get; set; }

            public override string ToString()
            {
                return (Value ?? -1).ToString();
            }
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static UInt32 ComputeSigma0(UInt32 x)
        {
            return ROTR(x, 2) ^ ROTR(x, 13) ^ ROTR(x, 22);
        }

        private static uint? TryWith(List<Column> table, uint searchFor, int a1, int a2, int a3, int a4, int a5, int a6)
        {
            table[0].Cells[1].Value = a1;
            table[0].Cells[2].Value = a2;

            table[1].Cells[1].Value = a3;
            table[1].Cells[2].Value = a4;

            table[2].Cells[1].Value = a5;
            table[2].Cells[2].Value = a6;

            List<Column> newTable = new List<Column>(32);

            while (true)
            {
                for (int i = 0; i < table.Count; i++)
                {
                    Column column = table[i];
                    if (column.ValuesCount() == 2)
                    {
                        column.Solve(searchFor);
                        if (column.ValuesCount() == 3)
                        {
                            if (!column.Check(searchFor))
                                return null;
                            newTable.Add(column);
                            table.RemoveAt(i);
                            i--;
                        }
                    }
                    else
                    if (column.ValuesCount() == 3)
                    {
                        if (!column.Check(searchFor))
                            return null;
                        newTable.Add(column);
                        table.RemoveAt(i);
                        i--;
                    }
                }
                if (table.Count == 0)
                    break;
            }

            uint result = 0;

            for (int i = 0; i < newTable.Count; i++)
            {
                Column column = newTable[i];
                var key = column.Cells[0].InputPosition;
                var value = column.Cells[0].Value;
                result |= (uint)(value.Value << (31 - key));
            }

            return result;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static int ApplyWithDepth(int x, int y)
        {
            var temp = x + y;
            while (temp >= 32)
                temp -= 32;
            while (temp < 0)
                temp += 32;
            return temp;
        }

        private static List<Column> CreateTable(List<Variable> variables)
        {
            List<Column> columns = new List<Column>(32);
            for (int i = 0; i < variables.Count; i++)
            {
                Column column = new Column();
                column.Cells[0] = variables[ApplyWithDepth(i, -GetFirstOffset())];
                column.Cells[1] = variables[ApplyWithDepth(i, -GetSecondOffset())];
                column.Cells[2] = variables[ApplyWithDepth(i, -GetThirdOffset())];
                column.Position = i;
                columns.Add(column);
            }

            return columns;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static int GetThirdOffset()
        {
            return 22;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static int GetSecondOffset()
        {
            return 13;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static int GetFirstOffset()
        {
            return 2;
        }

        public static uint DeSigma0(uint searchFor)
        {
            List<Variable> variables = new List<Variable>(32);
            for (int j = 0; j < 32; j++)
            {
                variables.Add(new Variable()
                {
                    InputPosition = j
                });
            }

            uint? result = null;

            for (int i = 0; i < 64; i++)
            {
                var a1 = (i >> 0) & 1;
                var a2 = (i >> 1) & 1;
                var a3 = (i >> 2) & 1;
                var a4 = (i >> 3) & 1;
                var a5 = (i >> 4) & 1;
                var a6 = (i >> 5) & 1;

                var table = CreateTable(variables);
                for (int j = 0; j < 32; j++)
                {
                    variables[j].Value = null;
                }

                result = TryWith(table, searchFor, a1, a2, a3, a4, a5, a6);
                if (result != null)
                    break;
            }

            return result.Value;
        }

        static void Main(string[] args)
        {
            var amount = 100000;
            var s = Stopwatch.StartNew();
            for (int i = 0; i < amount; i += 10)
            {
                uint input = (uint)i;
                if (DeSigma0(ComputeSigma0(input)) != input)
                {
                    Console.Write(input);
                    Console.Write(" -> ");
                    Console.Write(ComputeSigma0(input));
                    Console.Write(" -> ");
                    Console.WriteLine(DeSigma0(ComputeSigma0(input)));
                }
            }

            s.Stop();
            Console.WriteLine(s.ElapsedMilliseconds + " ms");
            Console.WriteLine(s.ElapsedMilliseconds / (double)amount + " ms/sigma0");
        }
    }