How to become an author
Search
Write a publication
Pull to refresh
4
Karma
0
Rating
@gchebanov

User

Send message
Profile Publications Comments 120Bookmarks 15
Пришли домой из-за Element

а с чего это вы взяли

Все так говорят (на один символ отправка 8 байт если между ними меньше ~20ms), пробежал по коду и не вижу ничего противоречащего этому. Тестить правда лень, если хотите оспорить — wireshark/tcpdump вам в помощь.

подмешивается немного мусора

Действительно в прошлом году появился патч и опция в конфиге, мне интересно, а в вашем дистрибутиве есть эта опция? (проще всего проверить man ssh_config; /Obf)

Презентация про ssh, тут статья. Текст об этом на хабре, но я не рекомендую ни комментарии ни статью: там какая-то отсебятина про visual feedback.

Но в таком случае происходит утечка данных не только о тайминге нажатий, но и о количестве клавиш, что соответствует длине пароля

Вместе с таймингом утекает и длина пароля, ответных пакетов со стороны сервера не нужно.

В комментариях тоже какая-то дичь, например: (проблема не в комментарии или в комментаторе, а в том что его никто не поправил, так и висит).

в SSH автоматически включается Nagel's и передаваемые символы начинают группироваться и объединяться, что портит хакерам весь праздник

/* Informs that the current session is interactive.  Sets IP flags for that. */

void
ssh_packet_set_interactive(struct ssh *ssh, int interactive, int qos_interactive, int qos_bulk)
{
    ...
	set_nodelay(state->connection_in);
    ...
}

/* disable nagle on socket */
void
set_nodelay(int fd)
{
    ...
    if (setsockopt(fd, IPPROTO_TCP, TCP_NODELAY, &opt, sizeof opt) == -1)
		error("setsockopt TCP_NODELAY: %.100s", strerror(errno));
}

Статья про анализ серверного "пинга" со стороны собеседника в IM.

Total votes 4: ↑4 and ↓0+4
Look
Пришли домой из-за Element

Напишу на тот случай если кто-то не понимает какую конкретно безопасность обеспечивает ‎E2EE и для/от кого. Для любого мессенджера с моментальной доставкой сообщений и без серьёзного "замусоривания" траффика легко понять кто с кем общается используя глобальное наблюдение (без MitM) и элементарные корреляции.

Пусть пользователь A, B живут в стране, где некие вредоносные агенты Е установили специальное оборудование сохраняющее метаданные всего оконечного трафика на всех провайдерах связи. Пусть агенты E знают A, но не знают B, про B известно что он один из множества U.

Теперь каждый раз когда A пишет сообщение B, он инициирует обмен сетевым трафиком с серверами напрямую (Telegram), через peer-to-peer сеть(Tor), либо даже с использованием туннеля с дополнительным шифрованием ( Wireguard или OpenVPN). Но во всех популярных любительских сценариях использования (за редким исключением вроде i2p) размеры пакетов меняются крайне предсказуемо, а то и не меняются вовсе. Теперь E, зная паттерны трафика нового сообщения (а в случае push уведомлений можно опираться и на ip-подсеть как на показатель пуша), запоминает текущее время.

Затем это сообщение должно прийти B, где ситуации повторится. Так как множество людей из U могут получить подобный трафик случайно, E может лишь ограничить размер множества U - даже для довольно таки большого окна доставки в минуты (типично для пуш-уведомлений) с каждым сообщением размер U будет сокращаться в разы, если не в десятки. Для однозначного установления B потребуется около 27 бит информации (|U|~=1.4e8), что вполне себе достижимо при регулярном общении. Даже если утекать будут малые доли бита (т.е. агенты E очень не уверены в том что произошло общение), из того что нам их нужно собрать буквально десятки, при достаточном количестве сообщений легко вычислить весь граф общения.

Эту картину не меняет даже вменяемый false-positive (пусть например фоном запущенный ютуб раз в 15 секунд даёт картину похожую на сообщение, тогда мы должны учесть шанс того что A ничего не отправлял). В таком случае мы не выкидываем кандидатов из U, а честно обновляем ожидания по Байесу. Если проделать подобное в итоге получатся что граф общения оказывается (ребро между вершинами если они общаются) равен попарной временной корреляции "интересного" трафика относительно U.

Подправив параметры можно узнать например на какие каналы в youtube вы подписаны не залезая в шифрованный трафик, достаточно посмотреть корреляцию жирного потока на сервера гугла с расписанием публикации новых видео, (если вы конечно открываете их сразу по уведомлению).

Да, это вычислительно сложная задача, но явно не сложнее подсчета условного PageRank-a для поискового индекса с MapReduce, естественно считать в лоб (O(|U|^2)) нельзя.

Слайды про утечку пользователя по паролю при наборе его используя SSH (не совсем в тему, но идея похожая)

Определение местоположения пользователя популярных "защищенных" мессенджеров

Тут исследователи не пользуются глобальным мониторингом траффика, смотрят только на раундтрипы оповещения о доставке.

P.S.
Задумался над тем что бы комментарий до статьи добить, но об подобном на хабре уже писали еще в 2011 (в контексте Tor, Tarzan и Morphmix).

Total votes 30: ↑30 and ↓0+30
Look
Переворачивающиеся при умножении числа

Еще я сомнительным способом генерировал случайное целое, uniform_uint64() % (HI-LO) + LO В районе 10^18 там уже значительный перекос в пользу меньших чисел.

This comment wasn’t rated yet0
Look
Переворачивающиеся при умножении числа

Было бы любопытно узнать, как график ведёт себя на бесконечности

Прогнал Монте-Карло на равномерных неупорядоченных парах, (это не точно учтёт пары где x=y, но так как их немного, погрешность должна быть небольшой).

Просто взял p:=cnt_good/cnt_iters; estimate:=81*10^{d-2}*p/2;

Скорость симуляции получилась около 5 миллиардов итераций в секунду, что не впечатляет. Пришлось немного попотеть что бы правильно работать с 36-значными числами.

Monte-Carlo
# [x y]
# d=d elapsed_time p_good estimate_pairs
# [269 581]
# d=3 129.385 3.851820e-04 1.559987e+02
# [4395 8691]
# d=4 154.701 8.392064e-05 3.398786e+03
# [87365 79139]
# d=5 155.051 2.766043e-05 1.120248e+05
# [775100 162389]
# d=6 154.746 1.113085e-05 4.507995e+06
# [2530020 4761510]
# d=7 207.304 5.262449e-06 2.131292e+08
# [85693413 36003975]
# d=8 233.018 2.778503e-06 1.125294e+10
# [345731723 932322371]
# d=9 234.242 1.595132e-06 6.460286e+11
# [8388016499 5721446594]
# d=10 237.009 9.736462e-07 3.943267e+13
# [40264350366 98521508913]
# d=11 237.098 6.248657e-07 2.530706e+15
# [919177426937 734068423163]
# d=12 237.305 4.179230e-07 1.692588e+17
# [8616586083842 7797719745830]
# d=13 267.747 2.884882e-07 1.168377e+19
# [45126923716086 53984469270216]
# d=14 270.713 2.058496e-07 8.336909e+20
# [204357829294211 514926408573260]
# d=15 269.294 1.502094e-07 6.083479e+22
# [6896406641595237 8139155118610023]
# d=16 319.639 1.116254e-07 4.520827e+24
# [62459283066899325 52619943312077259]
# d=17 343.897 8.466919e-08 3.429102e+26
# [409783614423487398 781679240519529663]
# d=18 344.870 6.535767e-08 2.646985e+28

Относительная точность падает при уменьшении p, поэтому оценку для d=18 получилось посчитать с точностью ±0.3%

Monte-Carlo
Monte-Carlo

Total votes 2: ↑2 and ↓0+2
Look
Переворачивающиеся при умножении числа
Hidden text
@cuda.jit
def cuda_pairs_core(A, B, C, C1, C2, d, base):
    # ...
    if p_i + 1 < A.size and p_j + 1 < A.size:
        i0, i1 = A[p_i], A[p_i + 1]
        j0, j1 = A[p_j], A[p_j + 1]
        cnt = uint64(0)
        for i in range(i0, i1):
            k = uint64(i * max(j0, i))
            k_hi = uint64(k // b_lim)
            k_lo = uint64(k % b_lim)
            for j in range(max(j0, i), j1):
                if k >= low_lim:
                    if C[k_hi] + C1[k_lo // c2_lim] + C2[k_lo % c2_lim] == C[i] + C[j]:
                        cnt += uint64(1)
                k += i
                k_lo += i
                if k_lo >= b_lim:
                    k_lo -= b_lim
                    k_hi += uint64(1)
        cuda.atomic.add(B, (t_i, t_j), cnt)

@njit
def init_c(C, d, BASE):
    p = 1
    for i in range(d):
        for j in range(p - 1, -1, -1):
            for z in range(BASE - 1, -1, -1):
                C[j * BASE + z] = C[j] + (uint64(1) << (z * 4))
        p *= BASE

Total votes 2: ↑2 and ↓0+2
Look
Переворачивающиеся при умножении числа

Попробовал ваш алгоритм на видяшке, работает 4.5 секунды для n=6.

Заодно и осилил n=7 

7
2 -> 0.871
156
3 -> 0.002
3399
4 -> 0.002
112025
5 -> 0.018
4505706
6 -> 4.435
213002162
7 -> 974.439

Total votes 2: ↑2 and ↓0+2
Look
Переворачивающиеся при умножении числа

Переписав на С++, на вычисление ушло 25 минут

Лобовой подсчет без каких-либо алгоритмов на видяшке работает 4 секунды! (задача с парами). Если не лень ждать 16 часов сможете узнать ответ для n=7.

7
2 -> 0.675
156
3 -> 0.001
3399
4 -> 0.044
112025
5 -> 4.365
4505706
6 -> 537.973
Hidden text
@cuda.jit(device=True)
def cuda_pair_check(i, j, k, d, base):
    a = cuda.local.array(base, np.uint8)
    for z in range(base):
        a[z] = 0
    for z in range(d):
        a[int(i % base)] += 1
        i = i // base
        a[int(j % base)] += 1
        j = j // base
    for z in range(2*d):
        a[int(k % base)] -= 1
        k = k // base
    nz = 0
    for z in range(base):
        if a[z] == 0:
            nz += 1
    return nz == base


@cuda.jit
def cuda_pairs_core(A, B, d, base):
    assert base == 10
    p_i, p_j = cuda.grid(2)
    t_i, t_j = cuda.threadIdx.x, cuda.threadIdx.y
    low_lim = 1
    for k in range(2*d - 1):
        low_lim *= base
    if p_i + 1 < A.size and p_j + 1 < A.size:
        i0, i1 = A[p_i], A[p_i + 1]
        j0, j1 = A[p_j], A[p_j + 1]
        cnt = uint64(0)
        for i in range(i0, i1):
            i = uint64(i)
            for j in range(j0, j1):
                j = uint64(j)
                if i <= j:
                    k = uint64(i * j)
                    if k < low_lim: continue
                    if cuda_pair_check(i, j, k, d, 10):
                        cnt += 1
        cuda.atomic.add(B, (t_i, t_j), cnt)

def run_cuda_pairs(d):
    num = 2**10
    A = np.linspace(pow(BASE, d - 1), pow(BASE, d), num).astype(np.uint64)
    threads = (2**5, 2**4)
    B = np.zeros(threads, dtype=np.int32)
    blocks = (
            (A.size - 1 + (threads[0] - 1)) // threads[0],
            (A.size - 1 + (threads[1] - 1)) // threads[1],
    )
    A, B = cuda.to_device(A), cuda.to_device(B)
    cuda_pairs_core[blocks, threads](A, B, d, BASE)
    B = B.copy_to_host()
    return np.sum(B)

def main_pairs():
    print(f'start {datetime.datetime.now()}')
    for d in range(2, 8):
        t0 = time.perf_counter()
        cnt = run_cuda_pairs(d)
        t1 = time.perf_counter()
        print(cnt)
        print(f'{d} -> {t1-t0:.3f}')

Total votes 2: ↑2 and ↓0+2
Look
Переворачивающиеся при умножении числа

Ничего не нашлось, а пятнадцать нужно 16 часов ждать. Расширил пространство на несколько порядков, вдруг пригодится потомкам.

Другие основания, из не указанного выше
M=2
(40) 1100111001101110111101000000000100000011 * 1010110100001000010111011110000111010001 = 1000101110000111101110100001000010110101 1100000010000000001011110111011001110011
(42) 111010101010110001000001000101111001101011 * 101100101100110011100110011110011111000101 = 101000111110011110011001110011001101001101 110101100111101000100000100011010101010111

M=3
(18-26) None

M=4
(11) 20221122201 * 33313301202 = 20210331333 10222112202
(12) 220032112122 * 220231112121 = 121211132022 221211230022
(13) 3033122211023 * 2021000003321 = 1233000001202 3201122213303
(19) 3123010113323033123 * 1223000330230123211 = 1123210320330003221 3213303233110103213
(20) 21123300031031323121 * 33203011213013222012 = 21022231031211030233 12132313013000332112
(21) 231122200023011022212 * 200211130021013310311 = 113013310120031112002 212220110320002221132
(21) 131012330133313121331 * 220013120002032330201 = 102033230200021310022 133121313331033210131

M=5
(10) 4402131124 * 1403420431 = 1340243041 4211312044
(10) 4424311302 * 2243042322 = 2232403422 2031134244
(13) 1322024130211 * 4242031404321 = 1234041302424 1120314202231
(15) 204304333140412 * 314110410304121 = 121403014011413 214041333403402
(16-18) None

M=6
(10) 2344420112 * 2433414111 = 1114143342 2110244432
(10) 2230332102 * 3120354411 = 1144530213 2012330322
(10) 1440535111 * 5043054031 = 1304503405 1115350441
(14) 21240011132212 * 42005450351431 = 13415305450024 21223111004212

M=7
(13) 5054030524163 * 5540446553414 = 4143556440455 3614250304505
(14) 26623462035461 * 52046210055512 = 21555001264025 16453026432662

M=8
(10) 6774770256 * 1540253631 = 1363520451 6520774776
(10) 6003775002 * 4000002003 = 3002000004 2005773006
(10) 5470206021 * 7431456225 = 5226541347 1206020745
(13) 6000377750002 * 4000000020003 = 3000200000004 2000577730006

M=9
(7-13) None

M=10
(11-14) None

M=11
(12) 534338726a98 * 598050086292 = 292680050895 89a627833435

M=12
(11) a0a40435495 * 3067a602862 = 268206a7603 59453404a0a
(11) 96124b45043 * 4a8b05766a3 = 3a66750b8a4 34054b42169

M=13
(11) 628ba56c626 * 22a0bc87901 = 10978cb0a22 626c65ab826

M=14
(8-11) None

M=15
(10) 59bcc30787 * e5a4923465 = 5643294a5e 78703ccb95

M=16
(3) 269 * e12 = 21e 962
(6) ab5af2 * 848b85 = 58b848 2fa5ba
(9) 6ebade3a2 * 82b559883 = 388955b28 2a3edabe6

M=17
(2) 6a * c4 = 4c a6
(5) 473d7 * ceg53 = 35gec 7d374
(8) 88b918f2 * 8g554484 = 484455g8 2f819b88
(9) gad3cc3g9 * f8701ac2f = f2ca1078f 9g3cc3dag
(10) None

M=18
(2) 4b * a2 = 2a b4
(5) c060c * 19001 = 10091 c060c
(9) ahb305ahe * 35c8a6702 = 2076a8c53 eha503bha
(9) ad95ea864 * c531fe167 = 761ef135c 468ae59da
(9) a3h94a05h * eh2g90f88 = 88f09g2he h50a49h3a

M=19
(2) 62 * b3 = 3b 26
(3-10) None

M=20
(3) ac5 * j2a = a2j 5ca
(4) ce24 * 4j23 = 32j4 42ec
(5) g040g * 15001 = 10051 g040g
(8) 44ch32i2 * ac2jgh42 = 24hgj2ca 2i23hc44
(9) 4f55610hc * 8bb1h2h02 = 20h2h1bb8 ch01655f4

M=21
(3) 7g7 * ce4 = 4ec 7g7
(7) h41830j * 306fh92 = 29hf603 j03814h

M=22
(6) g5ldhf * 5d5334 = 4335d5 fhdl5g

M=23
(2-8) None

M=24
(5) i060i * 18001 = 10081 i060i
(5) g080g * 1c001 = 100c1 g080g
(5) m823h * ff4de = ed4ff h328m
(5) l7ch3 * h305f = f503h 3hc7l
(5) 6in21 * m4h66 = 66h4m 12ni6
(7) 68kcfj3 * 9jbkbe2 = 2ebkbj9 3jfck86
(8) 62c9lnci * c6f1gm23 = 32mg1f6c icnl9c26
(9) None

Total votes 3: ↑3 and ↓0+3
Look
Переворачивающиеся при умножении числа
@cuda.jit
def cuda_run_core(A, oA, oB, B):
    B0 = B // BASE
    pos = cuda.grid(1)
    if pos + 1 < A.size:
        b_lo = A[pos]
        b_hi = A[pos + 1]
        for b in range(b_lo, b_hi):
            if b % BASE == 0:
                continue
            rb = rev(b)
            a0 = uint64(math.ceil(rb * 1.0 * B / b))
            for a in range(a0, a0 + BASE):
                if not (B0 <= a < B):
                    continue
                ra = rev(a)
                err = uint64(a * b - rb * B)
                if err == ra:
                    oA[pos] = a
                    oB[pos] = b
                if err > B:
                    break

Проверяет все до m=12 за минуту на видюшке. Посмотрим что будет с m=14 через пару часов.

Hidden text
@cuda.jit(device=True)
def cuda_rev(x):
    r = uint64(0)
    while x > 0:
        r = r * BASE + x % BASE
        x = x // BASE
    return uint64(r)


def run_cuda(d):
    # 10 -> 0.638
    # 11 -> 6.601
    # 12 -> 68.787
    # 13 -> 775.907
    num = 2**18
    A = np.linspace(pow(BASE, d - 1), pow(BASE, d), num).astype(np.uint64)
    oA, oB = np.zeros_like(A), np.zeros_like(A)
    threadsperblock = 2**9
    blockspergrid = (A.size - 1 + (threadsperblock - 1)) // threadsperblock
    A, oA, oB = cuda.to_device(A), cuda.to_device(oA), cuda.to_device(oB)
    cuda_run_core[blockspergrid, threadsperblock](A, oA, oB, uint64(pow(BASE, d)))
    A, oA, oB = A.copy_to_host(), oA.copy_to_host(), oB.copy_to_host()
    for x, y in zip(oA, oB):
        if x:
            print(x, '*', y, '=', rev(y), rev(x))


def main():
    for d in range(8, 16):
        t0 = time.perf_counter()
        run_cuda(d)
        t1 = time.perf_counter()
        print(f'{d} -> {t1-t0:.3f}')

Total votes 15: ↑15 and ↓0+15
Look
Переворачивающиеся при умножении числа

вычисления длились 5 часов на 11-ядрах процессора

Чет медленно. Сейчас сделаю побыстрее.

This comment wasn’t rated yet0
Look
Каскадное шифрование редуцированным алгоритмом RSA

https://github.com/hayguen/mlpolygen Вот тут есть реализация для двоичного случая, там довольно просто написано. Готового рецепта действительно нет, просто берёшь и каждый проверяешь, но не в тупую, а используя бинарное возведение по делителям размера группы.

This comment wasn’t rated yet0
Look
Каскадное шифрование редуцированным алгоритмом RSA

Алгоритм аналогичный поиску первообразного корня (для доказательства придется вспомнить теорему Лагранжа). В соседней вашей статье увидел параметры p=251 m=4.

Вот вам генератор максимального периода для p=251 m=8 (период 250**8 ~= 1.5*10^19), найден быстрее секунды.

185*x^0+67*x^1+248*x^2+128*x^3+195*x^4+45*x^5+129*x^6+233*x^7+1*x^8

За минуту нашлось такое (p=251, m=14, период 3.7*10^33)

145*x^0+200*x^1+10*x^2+88*x^3+136*x^4+109*x^5+169*x^6+94*x^7+17*x^8+129*x^9+165*x^{10}+87*x^{11}+3*x^{12}+217*x^{13}+1*x^{14}

Хотя там и твориться непотребство аналогичное этой статье надеюсь вам эти полиномы как-то помогут. Вот ещё сотня аналогичных первому.

На практике, поиск генераторной пары для m=6 и p=251 может занимать 2...3 суток на одном ядре процессора, что, в принципе, осуществимо. Для m=7 среднее время поиска прогнозируется примерно в 250 раз больше -- вероятно, это недостижимый случай...

Предложенная архитектура требует экспертизы со стороны криптографического сообщества и проверки временем.

Считайте что она её не прошла.

Алгоритм генерации общего секрета

Взламывается одним умножением и одним сложением в поле Галуа🤦

Почитайте хоть Algebraic Shift Register Sequences(Goresky, Klapper) Прям с основ всё разъясняют.

This comment wasn’t rated yet0
Look
Каскадное шифрование редуцированным алгоритмом RSA

Вот тут аж до 2^168 полиномчики.

This comment wasn’t rated yet0
Look
Каскадное шифрование редуцированным алгоритмом RSA

https://docs.python.org/3/library/functions.html#pow

def pow(base, exp, mod=None):
  "Return base to the power exp; if mod is present, return base to the power exp, modulo mod"

This comment wasn’t rated yet0
Look
Каскадное шифрование редуцированным алгоритмом RSA

Тут никаких экспертов не нужно, настолько всё плохо.

В случае из примера автор называет открытым ключом

ke=[3,61,12656101,606059], m=32067095497


а закрытым

kd=[17,7974709,47,94153], m=32067095497


В действительности можно брать одно число, выполнять цепочку умножений по модулю нет смысла, его можно заменить на одно умножение.

ke = (3*61*12656101*606059) \mod m = 32032525813

Можно убедится в эквивалентности, в случае из примера:

x*ke \mod m = (123456789*32032525813) \mod m = 11690502048 = y

Давайте же проведём атаку, попытаемся найти закрытый ключ по открытому:

kd=pow(ke,m-2,m)=12155847247

Проверим:

(y*kd) \mod m = (11690502048*12155847247) \mod m = 123456789

Ева довольна. Эта атака будет прекрасно работать и с числами из тысяч цифр так же хорошо как и с 64-х битными, никаких факторизаций не нужно.

Честно говоря вообще не понял задумку автора, какую либо идею. Может вы перепутали умножение и возведение в степень, или перепутали малую теорему Ферма с теоремой Эйлера.

P.S. В этой статье нет ничего общего ни с RSA, ни с шифрованием, ни с криптографией, ни с ускорением. Поддерживаю комментатора выше, вы опасно некомпетентны в криптографии.

Total votes 2: ↑2 and ↓0+2
Look
Youtube-канал ones and zeros опубликовал визуализации...

Алгоритм A* — это рекурсивный алгоритм поиска

WTF! В каком это месте он рекурсивный? В целом почти все алгоритмы поиска кратчайшего пути нерекурсивные.

This comment wasn’t rated yet0
Look
Глава «Роскосмоса» Юрий Борисов пояснил нештатные ситуации на МКС возрастом станции и наличием на орбите мусора

Эксперты компании по отслеживанию космического мусора LeoLabs говорят, что обломки будут находиться на орбите еще долго, и возникнет «потенциальный риск столкновения с большинством спутников на низкой околоземной орбите в течение следующих нескольких лет или десятилетий».

Визуализация показала обширное облако обломков после уничтожения советского спутника

Total votes 5: ↑5 and ↓0+5
Look
Самый быстрый поиск пути на Go без аллокаций и СМС

Очень сомнительное ограничение в 56 на путь, так-то змейка на карте в 60x60 что-то порядка 1700 дает. В мире плюсов аллокацию из библиотеки можно избежать output iterator-ом, там такое на шаблонах бесплатно, в го так не выйдет.

This comment wasn’t rated yet0
Look
Существование треугольника Шарыгина — это настоящее математическое чудо

А где про это можно почитать на русском?

This comment wasn’t rated yet0
Look
Разработчик ОС «Альт» растит новое поколение российских программистов

Ого. Ходил еще школьником на его курс по питону 14-15 лет назад, жалко не имел подходящий mindset для этих занятий в то время. Вроде бы делали рисовалку на pygame. Действительно многому научил.

Помню через несколько лет уже в МФТИ сокурсники удивлялись этому факту когда мы учили курс по ОСям по его учебнику.

Total votes 1: ↑1 and ↓0+1
Look
BackHere
1
23 ...
67

Information

Rating
Does not participate
Registered
Activity

Your account

Sections

Information

Services

Support
© 2006–2024, Habr