d10b954719aa7fc23a2d293ce0622df3c910d98a-PR-2221

pending completion

Build # d10b954719aa7fc23a2d293ce0622df3c910d98a-PR-2221

Build Type

Pull #2221

github-actions

Committed by

web-flow

Commit Message

Merge b6d25b636 into 9c83fa109

Pull Request Pull Request #2221: Add shellcraft.sleep template wrapping SYS_nanosleep

Run Details

3639 of 6419 branches covered (56.69%)

11701 of 16706 relevant lines covered (70.04%)

0.7 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

86.38

/pwnlib/util/crc/__init__.py

"""Module for calculating CRC-sums.

Contains all crc implementations know on the interwebz. For most implementations
it contains only the core crc algorithm and not e.g. padding schemes.

It is horribly slow, as implements a naive algorithm working direclty on
bit polynomials. This class is exposed as `BitPolynom`.

The current algorithm is super-linear and takes about 4 seconds to calculate
the crc32-sum of ``'A'*40000``.

An obvious optimization would be to actually generate some lookup-tables.

This doctest is to ensure that the known data are accurate:
    >>> known = sys.modules['pwnlib.util.crc.known']
    >>> known.all_crcs == known.generate()
    True
"""
from __future__ import absolute_import
from __future__ import division

import six
import sys
import types

from pwnlib.util import fiddling
from pwnlib.util import packing
from pwnlib.util import safeeval
from pwnlib.util.crc import known


class BitPolynom(object):
    """Class for representing GF(2)[X], i.e. the field of polynomials over
    GF(2).

    In practice the polynomials are represented as numbers such that `x**n`
    corresponds to `1 << n`. In this representation calculations are easy: Just
    do everything as normal, but forget about everything the carries.

    Addition becomes xor and multiplication becomes carry-less multiplication.

    Examples:

        >>> p1 = BitPolynom("x**3 + x + 1")
        >>> p1
        BitPolynom('x**3 + x + 1')
        >>> int(p1)
        11
        >>> p1 == BitPolynom(11)
        True
        >>> p2 = BitPolynom("x**2 + x + 1")
        >>> p1 + p2
        BitPolynom('x**3 + x**2')
        >>> p1 * p2
        BitPolynom('x**5 + x**4 + 1')
        >>> p1 // p2
        BitPolynom('x + 1')
        >>> p1 % p2
        BitPolynom('x')
        >>> d, r = divmod(p1, p2)
        >>> d * p2 + r == p1
        True
        >>> BitPolynom(-1)
        Traceback (most recent call last):
            ...
        ValueError: Polynomials cannot be negative: -1
        >>> BitPolynom('y')
        Traceback (most recent call last):
            ...
        ValueError: Not a valid polynomial: y
    """


    def __init__(self, n):
        if isinstance(n, (bytes, six.text_type)):
            self.n = 0
            x = BitPolynom(2)
            try:
                for p in n.split('+'):
                    k = safeeval.values(p.strip(), {'x': x, 'X': x})
                    assert isinstance(k, (BitPolynom,)+six.integer_types)
                    k = int(k)
                    assert k >= 0
                    self.n ^= k
            except (ValueError, NameError, AssertionError):
                raise ValueError("Not a valid polynomial: %s" % n)
        elif isinstance(n, six.integer_types):
            if n >= 0:
                self.n = n
            else:
                raise ValueError("Polynomials cannot be negative: %d" % n)
        else:
            raise TypeError("Polynomial must be called with a string or integer")

    def __int__(self):
        return self.n

    def __add__(self, other):
        return BitPolynom(int(self) ^ int(other))

    def __radd__(self, other):
        return BitPolynom(int(self) ^ int(other))

    def __sub__(self, other):
        return BitPolynom(int(self) ^ int(other))

    def __rsub__(self, other):
        return BitPolynom(int(self) ^ int(other))

    def __xor__(self, other):
        return BitPolynom(int(self) ^ int(other))

    def __rxor__(self, other):
        return BitPolynom(int(self) ^ int(other))

    def __or__(self, other):
        return BitPolynom(int(self) | int(other))

    def __ror__(self, other):
        return BitPolynom(int(self) | int(other))

    def __and__(self, other):
        return BitPolynom(int(self) & int(other))

    def __rand__(self, other):
        return BitPolynom(int(self) & int(other))

    def __mul__(self, other):
        a, b = int(self), int(other)
        if a > b:
            a, b = b, a

        res = 0
        for n in range(a.bit_length()):
            if a & (1 << n):
                res ^= b << n
        return BitPolynom(res)

    def __rmul__(self, other):
        return self * other

    def __divmod__(self, other):
        other = BitPolynom(int(other))

        if other == 0:
            raise ZeroDivisionError

        resd = 0
        resm = int(self)

        for n in range(self.degree() - other.degree(), -1, -1):
            if resm & (1 << (n + other.degree())):
                resm ^= int(other) << n
                resd ^= 1 << n
        return (BitPolynom(resd), BitPolynom(resm))

    def __rdivmod__(self, other):
        return divmod(BitPolynom(int(other)), self)

    def __div__(self, other):
        return divmod(self, other)[0]
    __floordiv__ = __div__

    def __rdiv__(self, other):
        return divmod(other, self)[0]
    __rfloordiv__ = __rdiv__

    __floordiv__ = __div__
    __rfloordiv__ = __rdiv__

    def __mod__(self, other):
        return divmod(self, other)[1]

    def __rmod__(self, other):
        return divmod(other, self)[1]

    def __eq__(self, other):
        return int(self) == int(other)

    def __hash__(self):
        return int(self).__hash__()

    def __cmp__(self, other):
        return int(self).__cmp__(int(other))

    def __lshift__(self, other):
        return BitPolynom(int(self) << int(other))

    def __rlshift__(self, other):
        return BitPolynom(int(other) << int(self))

    def __rshift__(self, other):
        return BitPolynom(int(self) >> int(other))

    def __rrshift__(self, other):
        return BitPolynom(int(other) >> int(self))

    def __pow__(self, other):
        r = BitPolynom(1)
        for _ in range(other):
            r *= self
        return r

    def degree(self):
        """Returns the degree of the polynomial.

        Examples:

            >>> BitPolynom(0).degree()
            0
            >>> BitPolynom(1).degree()
            0
            >>> BitPolynom(2).degree()
            1
            >>> BitPolynom(7).degree()
            2
            >>> BitPolynom((1 << 10) - 1).degree()
            9
            >>> BitPolynom(1 << 10).degree()
            10
        """
        return max(0, int(self).bit_length()-1)

    def __repr__(self):
        if int(self) == 0:
            return '0'

        out = []
        for n in range(self.degree(), 1, -1):
            if int(self) & (1 << n):
                out.append("x**%d" % n)
        if int(self) & 2:
            out.append("x")
        if int(self) & 1:
            out.append("1")
        return 'BitPolynom(%r)' % ' + '.join(out)

class Module(types.ModuleType):
    def __init__(self):
        super(Module, self).__init__(__name__)
        self._cached_crcs = None
        self.BitPolynom = BitPolynom
        self.__dict__.update({
            '__file__'    : __file__,
            '__package__' : __package__,
        })

    def __getattr__(self, attr):
        crcs = known.all_crcs

        if attr == '__all__':
            return ['BitPolynom', 'generic_crc', 'cksum', 'find_crc_function'] + sorted(crcs.keys())

        info = crcs.get(attr, None)
        if not info:
            raise AttributeError("'module' object has no attribute %r" % attr)

        func = self._make_crc(info['name'], info['poly'], info['width'], info['init'], info['refin'], info['refout'], info['xorout'], info['check'], 'See also: ' + info['link'])

        setattr(self, attr, func)

        return func

    def __dir__(self):
        return self.__all__

    @staticmethod
    def generic_crc(data, polynom, width, init, refin, refout, xorout):
        """A generic CRC-sum function.

        This is suitable to use with:
        https://reveng.sourceforge.io/crc-catalogue/all.htm

        The "check" value in the document is the CRC-sum of the string "123456789".

        Arguments:
            data(str):    The data to calculate the CRC-sum of. This should either be a string or a list of bits.
            polynom(int): The polynomial to use.
            init(int):    If the CRC-sum was calculated in hardware, then this would b
                        the initial value of the checksum register.
            refin(bool):  Should the input bytes be reflected?
            refout(bool): Should the checksum be reflected?
            xorout(int):  The value to xor the checksum with before outputting
        """

        polynom = BitPolynom(int(polynom)) | (1 << width)
        if polynom.degree() != width:
            raise ValueError("Polynomial is too large for that width")

        init   &= (1 << width)-1
        xorout &= (1 << width)-1

        if isinstance(data, list):
            # refin is not meaningful in this case
            inlen = len(data)
            p = BitPolynom(int(''.join('1' if v else '0' for v in data), 2))
        elif isinstance(data, six.binary_type):
            inlen = len(data)*8
            if refin:
                data = fiddling.bitswap(data)
            p = BitPolynom(packing.unpack(data, 'all', endian='big', sign=False))
        else:
            raise ValueError("Don't know how to crc %s()" % type(data).__name__)
        p = p << width
        p ^= init << inlen
        p  = p % polynom
        res = p.n
        if refout:
            res = fiddling.bitswap_int(res, width)
        res ^= xorout

        return res

    @staticmethod
    def _make_crc(name, polynom, width, init, refin, refout, xorout, check, extra_doc = ''):
        def inner(data):
            return crc.generic_crc(data, polynom, width, init, refin, refout, xorout)
        inner.func_name = 'crc_' + name
        inner.__name__  = 'crc_' + name
        inner.__qualname__  = 'crc_' + name

        inner.__doc__   = """%s(data) -> int

        Calculates the %s checksum.

        This is simply the :func:`generic_crc` with these frozen arguments:

        * polynom = 0x%x
        * width   = %d
        * init    = 0x%x
        * refin   = %s
        * refout  = %s
        * xorout  = 0x%x

        %s

        Arguments:
            data(str): The data to checksum.

        Example:
            >>> print(%s(b'123456789'))
            %d
    """ % (name, name, polynom, width, init, refin, refout, xorout, extra_doc, name, check)

        return inner

    @staticmethod
    def cksum(data):
        """cksum(data) -> int

        Calculates the same checksum as returned by the UNIX-tool ``cksum``.

        Arguments:
            data(str): The data to checksum.

        Example:
            >>> print(cksum(b'123456789'))
            930766865
        """

        l = len(data)
        data += packing.pack(l, 'all', endian='little', sign=False)
        return crc.crc_32_cksum(data)

    @staticmethod
    def find_crc_function(data, checksum):
        """Finds all known CRC functions that hashes a piece of data into a specific
        checksum. It does this by trying all known CRC functions one after the other.

        Arguments:
            data(str): Data for which the checksum is known.

        Example:
            >>> find_crc_function(b'test', 46197)
            [<function crc_crc_16_dnp at ...>]
        """
        candidates = []
        for v in known.all_crcs.keys():
            func = getattr(crc, v)
            if func(data) == checksum:
                candidates.append(func)
        return candidates


tether = sys.modules[__name__]
crc = sys.modules[__name__] = Module()
crc.__doc__ = tether.__doc__

1	"""Module for calculating CRC-sums.
2
3	Contains all crc implementations know on the interwebz. For most implementations
4	it contains only the core crc algorithm and not e.g. padding schemes.
5
6	It is horribly slow, as implements a naive algorithm working direclty on
7	bit polynomials. This class is exposed as `BitPolynom`.
8
9	The current algorithm is super-linear and takes about 4 seconds to calculate
10	the crc32-sum of ``'A'*40000``.
11
12	An obvious optimization would be to actually generate some lookup-tables.
13
14	This doctest is to ensure that the known data are accurate:
15	>>> known = sys.modules['pwnlib.util.crc.known']
16	>>> known.all_crcs == known.generate()
17	True
18	"""
19	from __future__ import absolute_import	1✔
20	from __future__ import division	1✔
21
22	import six	1✔
23	import sys	1✔
24	import types	1✔
25
26	from pwnlib.util import fiddling	1✔
27	from pwnlib.util import packing	1✔
28	from pwnlib.util import safeeval	1✔
29	from pwnlib.util.crc import known	1✔
30
31
32	class BitPolynom(object):	1✔
33	"""Class for representing GF(2)[X], i.e. the field of polynomials over
34	GF(2).
35
36	In practice the polynomials are represented as numbers such that `x**n`
37	corresponds to `1 << n`. In this representation calculations are easy: Just
38	do everything as normal, but forget about everything the carries.
39
40	Addition becomes xor and multiplication becomes carry-less multiplication.
41
42	Examples:
43
44	>>> p1 = BitPolynom("x**3 + x + 1")
45	>>> p1
46	BitPolynom('x**3 + x + 1')
47	>>> int(p1)
48	11
49	>>> p1 == BitPolynom(11)
50	True
51	>>> p2 = BitPolynom("x**2 + x + 1")
52	>>> p1 + p2
53	BitPolynom('x3 + x2')
54	>>> p1 * p2
55	BitPolynom('x5 + x4 + 1')
56	>>> p1 // p2
57	BitPolynom('x + 1')
58	>>> p1 % p2
59	BitPolynom('x')
60	>>> d, r = divmod(p1, p2)
61	>>> d * p2 + r == p1
62	True
63	>>> BitPolynom(-1)
64	Traceback (most recent call last):
65	...
66	ValueError: Polynomials cannot be negative: -1
67	>>> BitPolynom('y')
68	Traceback (most recent call last):
69	...
70	ValueError: Not a valid polynomial: y
71	"""
72
73
74	def __init__(self, n):	1✔
75	if isinstance(n, (bytes, six.text_type)):	1✔
76	self.n = 0	1✔
77	x = BitPolynom(2)	1✔
78	try:	1✔
79	for p in n.split('+'):	1✔
80	k = safeeval.values(p.strip(), {'x': x, 'X': x})	1✔
81	assert isinstance(k, (BitPolynom,)+six.integer_types)	1✔
82	k = int(k)	1✔
83	assert k >= 0	1✔
84	self.n ^= k	1✔
85	except (ValueError, NameError, AssertionError):	1✔
86	raise ValueError("Not a valid polynomial: %s" % n)	1✔
87	elif isinstance(n, six.integer_types):	1!
88	if n >= 0:	1✔
89	self.n = n	1✔
90	else:
91	raise ValueError("Polynomials cannot be negative: %d" % n)	1✔
92	else:
93	raise TypeError("Polynomial must be called with a string or integer")	×
94
95	def __int__(self):	1✔
96	return self.n	1✔
97
98	def __add__(self, other):	1✔
99	return BitPolynom(int(self) ^ int(other))	1✔
100
101	def __radd__(self, other):	1✔
102	return BitPolynom(int(self) ^ int(other))	×
103
104	def __sub__(self, other):	1✔
105	return BitPolynom(int(self) ^ int(other))	×
106
107	def __rsub__(self, other):	1✔
108	return BitPolynom(int(self) ^ int(other))	×
109
110	def __xor__(self, other):	1✔
111	return BitPolynom(int(self) ^ int(other))	1✔
112
113	def __rxor__(self, other):	1✔
114	return BitPolynom(int(self) ^ int(other))	×
115
116	def __or__(self, other):	1✔
117	return BitPolynom(int(self) \| int(other))	1✔
118
119	def __ror__(self, other):	1✔
120	return BitPolynom(int(self) \| int(other))	×
121
122	def __and__(self, other):	1✔
123	return BitPolynom(int(self) & int(other))	×
124
125	def __rand__(self, other):	1✔
126	return BitPolynom(int(self) & int(other))	×
127
128	def __mul__(self, other):	1✔
129	a, b = int(self), int(other)	1✔
130	if a > b:	1✔
131	a, b = b, a	1✔
132
133	res = 0	1✔
134	for n in range(a.bit_length()):	1✔
135	if a & (1 << n):	1✔
136	res ^= b << n	1✔
137	return BitPolynom(res)	1✔
138
139	def __rmul__(self, other):	1✔
140	return self * other	×
141
142	def __divmod__(self, other):	1✔
143	other = BitPolynom(int(other))	1✔
144
145	if other == 0:	1!
146	raise ZeroDivisionError	×
147
148	resd = 0	1✔
149	resm = int(self)	1✔
150
151	for n in range(self.degree() - other.degree(), -1, -1):	1✔
152	if resm & (1 << (n + other.degree())):	1✔
153	resm ^= int(other) << n	1✔
154	resd ^= 1 << n	1✔
155	return (BitPolynom(resd), BitPolynom(resm))	1✔
156
157	def __rdivmod__(self, other):	1✔
158	return divmod(BitPolynom(int(other)), self)	×
159
160	def __div__(self, other):	1✔
161	return divmod(self, other)[0]	1✔
162	__floordiv__ = __div__	1✔
163
164	def __rdiv__(self, other):	1✔
165	return divmod(other, self)[0]	×
166	__rfloordiv__ = __rdiv__	1✔
167
168	__floordiv__ = __div__	1✔
169	__rfloordiv__ = __rdiv__	1✔
170
171	def __mod__(self, other):	1✔
172	return divmod(self, other)[1]	1✔
173
174	def __rmod__(self, other):	1✔
175	return divmod(other, self)[1]	×
176
177	def __eq__(self, other):	1✔
178	return int(self) == int(other)	1✔
179
180	def __hash__(self):	1✔
181	return int(self).__hash__()	×
182
183	def __cmp__(self, other):	1✔
184	return int(self).__cmp__(int(other))	×
185
186	def __lshift__(self, other):	1✔
187	return BitPolynom(int(self) << int(other))	1✔
188
189	def __rlshift__(self, other):	1✔
190	return BitPolynom(int(other) << int(self))	×
191
192	def __rshift__(self, other):	1✔
193	return BitPolynom(int(self) >> int(other))	×
194
195	def __rrshift__(self, other):	1✔
196	return BitPolynom(int(other) >> int(self))	×
197
198	def __pow__(self, other):	1✔
199	r = BitPolynom(1)	1✔
200	for _ in range(other):	1✔
201	r *= self	1✔
202	return r	1✔
203
204	def degree(self):	1✔
205	"""Returns the degree of the polynomial.
206
207	Examples:
208
209	>>> BitPolynom(0).degree()
210	0
211	>>> BitPolynom(1).degree()
212	0
213	>>> BitPolynom(2).degree()
214	1
215	>>> BitPolynom(7).degree()
216	2
217	>>> BitPolynom((1 << 10) - 1).degree()
218	9
219	>>> BitPolynom(1 << 10).degree()
220	10
221	"""
222	return max(0, int(self).bit_length()-1)	1✔
223
224	def __repr__(self):	1✔
225	if int(self) == 0:	1!
226	return '0'	×
227
228	out = []	1✔
229	for n in range(self.degree(), 1, -1):	1✔
230	if int(self) & (1 << n):	1✔
231	out.append("x**%d" % n)	1✔
232	if int(self) & 2:	1✔
233	out.append("x")	1✔
234	if int(self) & 1:	1✔
235	out.append("1")	1✔
236	return 'BitPolynom(%r)' % ' + '.join(out)	1✔
237
238	class Module(types.ModuleType):	1✔
239	def __init__(self):	1✔
240	super(Module, self).__init__(__name__)	1✔
241	self._cached_crcs = None	1✔
242	self.BitPolynom = BitPolynom	1✔
243	self.__dict__.update({	1✔
244	'__file__' : __file__,
245	'__package__' : __package__,
246	})
247
248	def __getattr__(self, attr):	1✔
249	crcs = known.all_crcs	1✔
250
251	if attr == '__all__':	1✔
252	return ['BitPolynom', 'generic_crc', 'cksum', 'find_crc_function'] + sorted(crcs.keys())	1✔
253
254	info = crcs.get(attr, None)	1✔
255	if not info:	1✔
256	raise AttributeError("'module' object has no attribute %r" % attr)	1✔
257
258	func = self._make_crc(info['name'], info['poly'], info['width'], info['init'], info['refin'], info['refout'], info['xorout'], info['check'], 'See also: ' + info['link'])	1✔
259
260	setattr(self, attr, func)	1✔
261
262	return func	1✔
263
264	def __dir__(self):	1✔
265	return self.__all__	×
266
267	@staticmethod	1✔
268	def generic_crc(data, polynom, width, init, refin, refout, xorout):
269	"""A generic CRC-sum function.
270
271	This is suitable to use with:
272	https://reveng.sourceforge.io/crc-catalogue/all.htm
273
274	The "check" value in the document is the CRC-sum of the string "123456789".
275
276	Arguments:
277	data(str): The data to calculate the CRC-sum of. This should either be a string or a list of bits.
278	polynom(int): The polynomial to use.
279	init(int): If the CRC-sum was calculated in hardware, then this would b
280	the initial value of the checksum register.
281	refin(bool): Should the input bytes be reflected?
282	refout(bool): Should the checksum be reflected?
283	xorout(int): The value to xor the checksum with before outputting
284	"""
285
286	polynom = BitPolynom(int(polynom)) \| (1 << width)	1✔
287	if polynom.degree() != width:	1!
288	raise ValueError("Polynomial is too large for that width")	×
289
290	init &= (1 << width)-1	1✔
291	xorout &= (1 << width)-1	1✔
292
293	if isinstance(data, list):	1!
294	# refin is not meaningful in this case
295	inlen = len(data)	×
296	p = BitPolynom(int(''.join('1' if v else '0' for v in data), 2))	×
297	elif isinstance(data, six.binary_type):	1!
298	inlen = len(data)*8	1✔
299	if refin:	1✔
300	data = fiddling.bitswap(data)	1✔
301	p = BitPolynom(packing.unpack(data, 'all', endian='big', sign=False))	1✔
302	else:
303	raise ValueError("Don't know how to crc %s()" % type(data).__name__)	×
304	p = p << width	1✔
305	p ^= init << inlen	1✔
306	p = p % polynom	1✔
307	res = p.n	1✔
308	if refout:	1✔
309	res = fiddling.bitswap_int(res, width)	1✔
310	res ^= xorout	1✔
311
312	return res	1✔
313
314	@staticmethod	1✔
315	def _make_crc(name, polynom, width, init, refin, refout, xorout, check, extra_doc = ''):	1✔
316	def inner(data):	1✔
317	return crc.generic_crc(data, polynom, width, init, refin, refout, xorout)	1✔
318	inner.func_name = 'crc_' + name	1✔
319	inner.__name__ = 'crc_' + name	1✔
320	inner.__qualname__ = 'crc_' + name	1✔
321
322	inner.__doc__ = """%s(data) -> int	1✔
323
324	Calculates the %s checksum.
325
326	This is simply the :func:`generic_crc` with these frozen arguments:
327
328	* polynom = 0x%x
329	* width = %d
330	* init = 0x%x
331	* refin = %s
332	* refout = %s
333	* xorout = 0x%x
334
335	%s
336
337	Arguments:
338	data(str): The data to checksum.
339
340	Example:
341	>>> print(%s(b'123456789'))
342	%d
343	""" % (name, name, polynom, width, init, refin, refout, xorout, extra_doc, name, check)
344
345	return inner	1✔
346
347	@staticmethod	1✔
348	def cksum(data):
349	"""cksum(data) -> int
350
351	Calculates the same checksum as returned by the UNIX-tool ``cksum``.
352
353	Arguments:
354	data(str): The data to checksum.
355
356	Example:
357	>>> print(cksum(b'123456789'))
358	930766865
359	"""
360
361	l = len(data)	1✔
362	data += packing.pack(l, 'all', endian='little', sign=False)	1✔
363	return crc.crc_32_cksum(data)	1✔
364
365	@staticmethod	1✔
366	def find_crc_function(data, checksum):
367	"""Finds all known CRC functions that hashes a piece of data into a specific
368	checksum. It does this by trying all known CRC functions one after the other.
369
370	Arguments:
371	data(str): Data for which the checksum is known.
372
373	Example:
374	>>> find_crc_function(b'test', 46197)
375	[<function crc_crc_16_dnp at ...>]
376	"""
377	candidates = []	1✔
378	for v in known.all_crcs.keys():	1✔
379	func = getattr(crc, v)	1✔
380	if func(data) == checksum:	1✔
381	candidates.append(func)	1✔
382	return candidates	1✔
383
384
385	tether = sys.modules[__name__]	1✔
386	crc = sys.modules[__name__] = Module()	1✔
387	crc.__doc__ = tether.__doc__	1✔

Gallopsled / pwntools / d10b954719aa7fc23a2d293ce0622df3c910d98a-PR-2221

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous