PUCE Virtual · Semana 5 · TIC Ciberseguridad
Compresión de
Datos sin Pérdida
Por qué importa guardar más en menos espacio
sin perder ni un bit de información crítica
EL PROBLEMA
¿Qué pasa cuando un
firewall genera 1 TB de logs al día?
Un SIEM empresarial real captura y almacena millones de eventos por hora. Sin compresión, los costos de almacenamiento y transmisión son inmanejables.
💸
Costo de almacenamiento
1 TB/día × 365 días = 365 TB/año solo en logs de red. Con compresión: puede reducirse hasta 10× menos.
📡
Ancho de banda
Transferir logs no comprimidos entre sedes satura enlaces. Cada bit ahorrado reduce latencia y costo de red.
🔬
Análisis forense
En una investigación de incidente, revisar TBs de logs lleva días. Comprimidos y sin pérdida: el analista ve cada evento exacto.
📌
¿Por qué sin pérdida? En ciberseguridad, una sola línea de log eliminada o alterada puede ser la diferencia entre detectar un ataque y no detectarlo. La compresión con pérdida (como JPEG) es inaceptable aquí.
CONCEPTO FUNDAMENTAL
La compresión explota la redundancia
Si los datos fueran completamente aleatorios, no se podrían comprimir. La redundancia es la "repetición predecible" — y hay tres tipos:
📊
Redundancia estadística
Algunos símbolos ocurren más frecuentemente que otros. En un log de red, ALLOW aparece 10× más que DENY. → Explotada por Huffman
🔁
Redundancia estructural
Ciertas secuencias o patrones se repiten en el texto. Una IP de origen aparece cientos de veces en el mismo log. → Explotada por Lempel-Ziv
🔗
Redundancia contextual
El valor de un símbolo depende del contexto anterior. Después de SYN casi siempre viene SYN-ACK. → Explotada por bloques
2024-03-15 08:41:22 ALLOW 192.168.1.5 → 10.0.0.1 TCP:443
2024-03-15 08:41:23 ALLOW 192.168.1.5 → 10.0.0.1 TCP:443
2024-03-15 08:41:24 ALLOW 192.168.1.5 → 10.0.0.1 TCP:443
TEORÍA — LÍMITE TEÓRICO
La entropía es el
límite que ningún algoritmo puede cruzar
Shannon demostró que existe un mínimo absoluto de bits por símbolo para representar una fuente. Ningún algoritmo puede comprimir por debajo de ese límite.
Primer Teorema de Shannon
H(X) ≤ ℓ̄ < H(X) + 1
ℓ̄ = longitud promedio del código | H(X) = entropía de la fuente
¿Qué significa para nosotros?
- H(X) = 0 bits: el resultado es siempre el mismo. No hay nada que transmitir.
- H(X) alto: los eventos son impredecibles. Poco compresible.
- H(X) bajo: muchos eventos predecibles. Alta compresión posible.
Ejemplo en un SIEM
- Log con 95% ALLOW y 5% DENY → H(X) ≈ 0.29 bits → muy compresible
- Log con 50% / 50% → H(X) = 1.0 bit → menos compresible
- Huffman siempre queda dentro de 1 bit sobre H(X)
ALGORITMO 1 · HUFFMAN CLÁSICO
Símbolo frecuente = código corto
Símbolo raro = código largo
Huffman construye un árbol binario desde las hojas hacia la raíz, fusionando siempre los dos nodos con menor probabilidad. El resultado es un código prefijo óptimo.
Ejemplo: Log de VaultSec Bank
| EVENTO | P | CÓDIGO | BITS |
| LOGIN_OK | 0.40 | 0 | 1 |
| CONSULTA | 0.25 | 10 | 2 |
| TRANSFER | 0.20 | 110 | 3 |
| SESION_EXP | 0.10 | 1110 | 4 |
| LOGIN_FAIL | 0.05 | 11110 | 5 |
| Longitud promedio | ℓ̄ = 2.15 bits |
ÁRBOL DE HUFFMAN
Raíz [1.00]
├─ 0 → LOGIN_OK [0.40]
└─ 1 → N₃ [0.60]
├─ 10 → CONSULTA [0.25]
└─ 11 → N₂ [0.35]
├─ 110 → TRANSFER [0.20]
└─ 111 → N₁ [0.15]
├─ 1110 → SESION_EXP
└─ 11110 → LOGIN_FAIL
ALGORITMO 1 · HUFFMAN CLÁSICO
Huffman ahorra 28% de almacenamiento
con eficiencia del 95%
3bits
Código actual (fijo)
Todos los eventos usan el mismo espacio, sin importar qué tan frecuentes son
2.15bits
Código Huffman
Los eventos frecuentes usan 1 bit; los raros usan hasta 5 bits
2.04bits
Entropía H(X)
Límite de Shannon — el mínimo absoluto posible para esta fuente
💡
¿Cuándo usar Huffman en ciberseguridad?
Cuando conoces de antemano la distribución de tus eventos: sistemas SIEM con distribuciones estables de alertas, compresión de cabeceras de protocolo (Huffman está en HTTP/2 via HPACK), y cualquier flujo con estadísticas conocidas. Para flujos dinámicos sin estadísticas previas → Huffman Adaptativo.
ALGORITMO 2 · HUFFMAN ADAPTATIVO
El árbol aprende mientras
el flujo llega en tiempo real
No necesitas conocer las probabilidades de antemano. El algoritmo actualiza el árbol tras cada símbolo recibido. Clave en IDS/IPS que analizan tráfico en vivo.
INIT
Árbol vacío
Solo existe el nodo NYT (Not Yet Transmitted)
NUEVO
Símbolo nuevo
Emite código NYT + símbolo crudo. Crea hoja en el árbol
EXIST
Símbolo conocido
Emite código Huffman actual del símbolo
UPDATE
Actualizar árbol
Incrementa frecuencia y reorganiza para mantener propiedad Huffman
A → f=5, p=0.50, código=0 (1 bit)
B → f=3, p=0.30, código=10 (2 bits)
C → f=2, p=0.20, código=11 (2 bits)
→ Ahorro del 25% sin conocer las probabilidades de antemano
ALGORITMO 3 · HUFFMAN POR BLOQUES
Agrupar en pares captura
dependencia entre eventos
En ciberseguridad, los eventos no son independientes: un SYN siempre viene antes de SYN-ACK. Al codificar pares en vez de símbolos sueltos, se captura esa dependencia y se comprime más.
Sin bloques — símbolo a símbolo
Cadena: A B A C A B A C A B
Códigos: 0 10 0 11 0 10 0 11 0 10
Total: 15 bits
Con bloques de 2 — bigramas
Bigramas: [AB] [AC] [AB] [AC] [AB]
AB → p=0.60 → código=0
AC → p=0.40 → código=1
Resultado: 0 1 0 1 0
Total: 5 bits ← ahorro 66.7%
⚡
¿Por qué la diferencia tan grande?
Sin bloques, el algoritmo trata A y B como independientes y gasta bits en ambos. Con bloques, detecta que AB siempre aparece junto: la A se vuelve predecible y desaparece de la cuenta. Solo necesitamos 1 bit para distinguir si el segundo símbolo es B o C.
ALGORITMO 4 · LZ77
"Este patrón ya apareció antes —
te doy una referencia"
LZ77 no analiza probabilidades. Escanea una ventana de datos pasados buscando la subsecuencia más larga que coincida con lo que está a punto de escribir. Si la encuentra, emite una referencia.
Formato de cada token LZ77
( offset, longitud, símbolo )
- offset: cuántas posiciones mirar hacia atrás en la ventana
- longitud: cuántos caracteres copiar desde allí
- símbolo: el siguiente carácter que no formaba parte de la copia
Ejemplo: A B C A B C A B C
1Aventana vacía — nuevo(0, 0, 'A')
2Bventana vacía — nuevo(0, 0, 'B')
3Cventana vacía — nuevo(0, 0, 'C')
4ABCcoincidencia de 3 en pos −3(3, 3, 'A')
8BCcoincidencia de 2 en pos −5(5, 2, '')
9 chars originales → 5 tokens · ahorro 44%
ALGORITMO 5 · LZ78
Construye un diccionario
que crece con los datos
LZ78 no tiene ventana de tamaño fijo. En cambio, construye un diccionario explícito de patrones que crece con la cadena. Cada token dice: "toma el patrón del diccionario en esta posición y añade este símbolo".
Formato de cada token LZ78
( índice_diccionario, símbolo_nuevo )
- índice=0: no hay prefijo previo — símbolo completamente nuevo
- índice>0: referencia a un patrón ya aprendido en el diccionario
- Cada token crea una nueva entrada en el diccionario
Ejemplo: A B A A B A B A
1A1→A [nueva](0, A)
2B2→B [nueva](0, B)
3AA3→AA [nueva](1, A)
5BA4→BA [nueva](2, A)
7BAusa entrada 4 existente(4, ε)
8 chars originales → 5 tokens
LZ77 vs LZ78
Misma familia, estrategias distintas
| Criterio | LZ77 | LZ78 / LZW |
|---|
| Memoria usada |
Ventana de tamaño fijo W — acotada |
Diccionario que crece — puede ser grande |
| Alcance hacia atrás |
Solo dentro de la ventana |
Toda la cadena procesada |
| Formato de token |
(offset, longitud, símbolo) |
(índice, símbolo_nuevo) |
| Variantes conocidas |
DEFLATE, gzip, zlib, PNG, ZIP |
LZW (GIF, TIFF), LZC, LZ4 |
| Uso en ciberseguridad |
Capturas pcap, tráfico TLS, logs de red |
Bases de firmas, registros estructurados |
| Ideal cuando... |
Datos en flujo continuo, memoria limitada |
Patrones complejos que se repiten globalmente |
APLICACIÓN REAL
Estas herramientas usan
compresión sin pérdida ahora mismo
🦈
Wireshark / tcpdump
Los archivos .pcap.gz usan DEFLATE (LZ77 + Huffman). Una captura de 100 MB sin comprimir → ~15 MB comprimida. El tráfico de red tiene altísima redundancia estructural.
🔐
HTTP/2 y TLS
HPACK (HTTP/2) usa Huffman estático para comprimir cabeceras HTTP. Reduce el tamaño de headers en un 30–60%. Está en cada petición HTTPS que tu navegador hace.
🛡️
SIEM / Splunk / ELK
Los índices de eventos de seguridad usan LZ4 o ZSTD (variantes LZ) internamente. Sin compresión, un SIEM empresarial consumiría 10–50× más disco.
$ tcpdump -w captura.pcap -i eth0 port 443
$ gzip captura.pcap
captura.pcap: 87.3 MB → captura.pcap.gz: 11.2 MB (87% reducción)
LADO OSCURO · CRIME & BREACH
La compresión puede ser
un vector de ataque
Si un atacante puede observar el tamaño del tráfico cifrado e inyectar texto conocido, puede inferir secretos. Así funcionan los ataques CRIME (2012) y BREACH (2013).
1
El servidor comprime + cifra las respuestas HTTP con gzip
Incluye cookies de sesión secretas junto al contenido visible
2
Atacante puede inyectar texto en la petición
Prueba distintos valores de cookie: token=AAAA..., token=AABA..., etc.
3
Observa el tamaño del paquete cifrado
Si el texto inyectado coincide con el secreto → LZ77 crea una referencia → el paquete es más pequeño
4
Recuperación del token carácter a carácter
Repitiendo el proceso ~50 peticiones por carácter → token de 32 chars recuperado en ~1600 peticiones
🛡️
Mitigación aplicada: Desde 2012, los navegadores modernos deshabilitaron la compresión TLS a nivel de registro. HTTP/2 usa HPACK con un modelo de seguridad distinto. Pero la compresión a nivel de aplicación (BREACH) sigue siendo un riesgo activo en sitios sin mitigaciones.
RESUMEN TÉCNICO
¿Cuándo usar cada algoritmo?
| Algoritmo | Redundancia | Dist. previa | Eficiencia | Caso de uso cyber |
|---|
| Huffman clásico |
Estadística |
Sí |
H(X) ≤ ℓ̄ < H(X)+1 |
HPACK (HTTP/2), logs estables |
| Huffman adaptativo |
Estadística |
No |
Converge con el tiempo |
Streams de alertas en vivo |
| Huffman por bloques |
Estadística + contextual |
Parcial |
Mejor que símbolo solo |
Secuencias de eventos correlacionados |
| LZ77 / DEFLATE |
Estructural (ventana) |
No |
Óptimo asintótico |
pcap, gzip, ZIP, PNG, TLS |
| LZ78 / LZW |
Estructural (dict.) |
No |
Óptimo asintótico |
GIF, bases de firmas, TIFF |
⚡
Combinación ganadora — DEFLATE: LZ77 elimina primero la redundancia estructural (patrones repetidos). Huffman elimina después la redundancia estadística de los tokens resultantes. Resultado: mejor compresión que cualquiera de los dos por separado. Lo usan gzip, ZIP, PNG, zlib y HTTP/2.
RETO 2 — SecureData Corp
¿Cómo aplica todo esto
en el Reto 2?
1️⃣
Analizar la fuente
Calcular H(X) y la redundancia R = (H_max − H(X)) / H_max de los datos de SecureData Corp. ¿Qué porcentaje es compresible en teoría?
2️⃣
Elegir el esquema
¿Los datos tienen distribución desigual? → Huffman. ¿Tienen secuencias repetidas? → LZ77/LZ78. ¿Tienen patrones contextuales? → Bloques.
3️⃣
Medir eficiencia
Comparar la longitud promedio obtenida con la entropía H(X). Calcular η = H(X)/ℓ̄ × 100%. Justificar la elección.
🎯
Pregunta guía para el Reto 2:
"Dado el perfil de datos de SecureData Corp, ¿qué tipo de redundancia domina — estadística o estructural? ¿Qué algoritmo se acerca más al límite de Shannon, y cuánto ahorro real se logra en bits por símbolo?"
SEMANA 5 · SÍNTESIS
La compresión sin pérdida
es infraestructura de seguridad
No es solo un truco para ahorrar espacio. Es lo que hace posible que existan logs completos, capturas forenses, transmisión eficiente y análisis en tiempo real — sin sacrificar ni un bit de evidencia.
Huffman
Redundancia estadística
LZ77
Redundancia estructural
ventana deslizante
LZ78
Redundancia estructural
diccionario dinámico