# Speech Separation based on Contrastive Learning and Deep Modularization

Peter Ochieng
Department of Computer Science.
University of Cambridge.
<EMAIL_ADDRESS>

###### Abstract

The current monaural state of the art tools for speech separation relies on
supervised learning. This means that they must deal with permutation problem,
they are impacted by the mismatch on the number of speakers used in training
and inference. Moreover, their performance heavily relies on the presence of
high-quality labelled data. These problems can be effectively addressed by
employing a fully unsupervised technique for speech separation. In this paper,
we use contrastive learning to establish the representations of frames then
use the learned representations in the downstream deep modularization task.
Concretely, we demonstrate experimentally that in speech separation, different
frames of a speaker can be viewed as augmentations of a given hidden standard
frame of that speaker. The frames of a speaker contain enough prosodic
information overlap which is key in speech separation. Based on this, we
implement a self-supervised learning to learn to minimize the distance between
frames belonging to a given speaker. The learned representations are used in a
downstream deep modularization task to cluster frames based on speaker
identity. Evaluation of the developed technique on WSJ0-2mix and WSJ0-3mix
shows that the technique attains SI-SNRi and SDRi of 20.8 and 21.0
respectively in WSJ0-2mix. In WSJ0-3mix, it attains SI-SNRi and SDRi of 20.7
and 20.7 respectively in WSJ0-2mix. Its greatest strength being that as the
number of speakers increase, its performance does not degrade significantly.

##  1 Introduction

Monaural speech enhancement involves isolating target speech from a mixture
obtained from a single microphone [1]. It has applications in multiple domains
such as automatic speech recognition, mobile speech communication and
designing of hearing aids [2]. Initial research on speech enhancement
exploited techniques such as non-negative matrix factorization [3] [4] [5]
probabilistic models [6] and computational auditory scene analysis (CASA)[7].
However, these techniques are tailored to closed-set speakers (i.e., do not
work well with mixtures with unknown speakers) which significantly restricts
their application in real environments. Due to the recent success of deep
learning models in different domains such natural language processing and
computer vision, these data driven techniques have been introduced to process
audio dataset. In particular, DNN models have become popular in speech
enhancement and have achieved great performance in terms of boosting speech
intelligibility and its ability to enhance speech with unknown speakers [8]
[9]. Speech enhancement DNN models must extract important features of speech,
maintain order of audio frames, exploit both local and global contextual
information inorder to achieve coherent separation of speech data. One of the
most challenging types of speech enhancement is multi-speaker speech
separation (i.e., identifying multiple target speech in each mixture and
separating them). The goal of speech separation is to estimate each target
speech $x_{c}$ composed in a mixture $y(n)$ (see equation 1). The mixture
$y(n)$ is composed of $C$ independent $x_{c}(n)$ speech signals with
$c=1,\cdots,C$.

$y(n)=\sum_{c=1}^{C}x_{c}(n)$ (1)

Here, $n$ indexes time. Separating speech from another speech is a daunting
task by the virtue that all speakers belong to the same class and share
similar characteristics[10]. Some models such as [11] and [12] lessen this
task by performing speech separation on a mixed speech signal based on gender
voices present. They exploit the fact that there is large discrepancy between
male and female voices in terms of vocal track, fundamental frequency contour,
timing, rhythm, dynamic range etc. This results in a large spectral distance
between male and female speakers in most cases to facilitate a good gender
segregation. For speech separation that the mixture involves speakers of the
same gender, the separation task is much difficult since the pitch of the
voice is in the same range[10]. Models such as [13] [14] [15] [16] [10] and
[8] cast the problem of multi-speaker recognition as as a multi-class
regression. In that case, training a DNN model involves comparing its output
to a source speaker. These DNN models always output a dimension for each
target class and when multiple sources of the same type exist, the system
needs to select arbitrarily which output dimension to map to each output and
this raises a permutation problem [10]. Therefore, systems that perform multi-
speaker separation have an extra burden of designing mechanisms that are
geared towards handling the permutation problem. There are several strategies
that are being implemented by speech separation tools to tackle permutation
problem. Work in [17] and [18] introduce permutation invariant training (PIT)
technique of computing permutation loss such that permutations of reference
labels are presented as a set to be compared with the output of the system.
The permutation with the lowest loss is adopted as the correct order. For a
system that performs $S$ speaker separation where, $S$ is high (e.g. 10),
implementation of PIT which has a computation complexity of $O(S!)$ is
computationally expensive [19] [20]. Due to this, [20] casts the permutation
problem as a linear sum problem where Hungarian algorithm is exploited to find
the permutation which minimizes the loss at computation complexity of
$O(S^{3})$. Work in [19] proposes SinkPIT loss which is based on Sinkhorn’s
matrix balancing algorithm. They utilize the loss to reduce the complexity of
PIT loss from $O(C!)$ to $O(kC^{2})$. Another prominent technique of handling
permutation problem is to employ a DNN clustering technique [21] [22] [16]
[23] [24] to identify the multiple speakers present in a mixed speech signal.
The DNN $f_{\theta}$ accepts as its input the whole spectrogram $X$ and
generates a $D$ dimension embedding vector V i.e. $V=f_{\theta}(X)\in
R^{N\times D}$. Here, the embedding $V$ learns the features of the spectrogram
$X$ and is considered a permutation- and cardinality-independent encoding of
the network’s estimate of the signal partition. For the network $f_{\theta}$
to be learn how to generate an embedding vector $V$ given the input $X$, it is
trained to minimize the cost function.

$C_{Y}(V)=||VV^{T}-YY^{T}||_{F}^{2}=\sum_{ij}(<v_{i},v_{j}>-<y_{i},y_{j}>)^{2}$
(2)

Here, $Y=\\{y_{i,c}\\}$ represents the target partition that maps the
spectrogram $S_{i}$ to each of the $C$ clusters such that $y_{i,c=1}$ if
element $i$ is in cluster $c$ . $YY^{T}$ is taken here as a binary affinity
matrix that represents the cluster assignment in a partition-independent way.
The goal in equation 2 is to minimise the distance between the network
estimated affinity matrix $VV^{T}$ and the true affinity matrix $YY^{T}$. The
minimization is done over the training examples. $||A||_{F}^{2}$ is the
squared Frobenius norm. Once $V$ has been established, its rows are clustered
into partitions that will represent the binary masks. To cluster the rows
$v_{i}$ of $V$, $k$-means clustering algorithm is used. The resulting clusters
of $V$ are then used as binary masks to separate the sources by applying the
masks on mixed spectrogram $X$. The separated sources are then reconstructed
separated by using inverse STFT.

Another major challenge faced by DNN models performing multi-speaker
separation is the mismatch on the number of speakers between training and
inference [25]. This arises when a speech separation model was trained on $n$
speaker mixtures but is being tested on $t\neq n$ speaker mixtures. The PIT-
based methods cannot directly deal with this problem due to their fixed output
dimension. Most speech separation models such as [26] [18] [27] [28] deal with
the problem by setting a maximum number of sources $C$ that the model should
output from any given mixture. If an inference mixture has $K$ sources, where
$C>K$, $C-K$ outputs are invalid, and the model needs to have techniques to
handle the invalid sources. In case of invalid sources, some models such as
[27], [26], [18] design the model to output silences for invalid sources while
[28] outputs the mixture itself which are then discarded by comparing the
energy level of the outputs relative to the mixture. The challenge with models
that output silences for invalid sources is that they rely on a pre-defined
energy threshold, which may be problematic if the mixture also has a very low
energy [28]. Some models handle the output dimension mismatch problem by
generating a single speech in each iteration and subtracting it from the
mixture until no speech is left [29], [30], [31][32], [33]. The iterative
technique despite being trained with a mixture with low number of sources can
generalize to mixtures with a higher number of sources [31]. It however faces
criticism that setting iteration termination criteria is difficult and the
separation performance decreases in later iterations due degradations
introduced in prior iterations[31]. While DNN clustering techniques in [21]
[22] [16] [23] and [24] solve the permutation problem, they unable to
effectively deal the mismatch on the number of speakers problem since they
rely on supervised learning to train the models. Further, the existing DNN
clustering technique require that the number of clusters $k$ be known
beforehand which may not be practical in all cases.

In summary, though the existing multi-speaker-speech separation models have
been able to achieve significant success in improving speech intelligibility,
majority of them rely on supervised training which introduces the permutation
problem and are unable to effectively deal with mixture mismatch problem.
Moreover, supervised training is always reliant on the availability of quality
labelled data that can be costly to curate. In this work, we seek address fore
mentioned challenges by introducing a fully unsupervised technique for multi-
speaker speech separation that can perform speech separation without priori
knowledge of the number of speakers in the mixture. The proposed method is
based on joint-embedding self-supervised learning and deep learning based
modularization. The key hypothesis that we investigate is if the different
frames extracted from speech of a speaker can be viewed as augmentations of a
given standard hidden frame of that speaker. Based on this hypothesis, we
train a model using self-supervised learning model such that it generates
similar representations for frames from a given speaker. we then exploit the
representations in a downstream model that performs clustering of the learned
features using deep neural network. Formally this work seeks to answer the
following questions:

  1. 1.

Do the frames belonging to a speech of a given speaker contain enough
information overlap to be considered augmentations of each other or they are
disjoint ?

  2. 2.

Does contrastive learning produce better node features as compared to graph
convolutional neural network such that its features result in better clusters
in downstream clustering task?

  3. 3.

How does the reconstructed speech from established clusters compare with other
existing state of the art speech separation techniques?

##  2 Related work

DNN speech separation models that are trained via supervised learning using
time-frequency features employ a number of strategies to learn how to generate
estimated clean signal from a noisy (mixed) signal. These strategies can be
classified into two categories based on the target of the model: 1) direct
estimate of clean speech features and 2) indirect estimation of clean signal
features. Techniques that adopt direct estimate of clean speech features fit a
nonlinear function to learn a mapping from a mixed signal feature to an
estimated clean signal feature. The training datasets of these models consist
of a noisy speech signal (source) and clean speech (target) features. This
technique is used in [34] [35] [36] [37] [38] [39] [40] [41] [42] and [43].
Models that adopt indirect estimation of clean signal features estimate clean
speech features by predicting real-valued or complex-valued masks [44]. The
mask function is usually constrained to be in range the [0,1] even though
different types of soft masks have been proposed ( see [18] [45] [46]). The
masks are always established by computing the signal-to-noise (SNR) within
each TF bin against a threshold or a local criterion [47]. It has been
demonstrated experimentally that the use of masks significantly improves
speech intelligibility when an original speech is composed of noise or a
masker speech signal [48] [49]. For deep learning models working on the time-
frequency domain, a model $g_{\theta}$ is designed such that given a noisy
spectrogram $Y[t,n]$ at time frame $t$, it estimates the mask $m_{t}$ at that
time frame. The established mask $m_{t}$ is then applied to the input
spectrogram to estimate clean speech spectrogram i.e.
$\hat{S}_{t}=m_{t}\otimes Y[t,n]$. Here, $\hat{S}_{t}$ is the spectrogram
estimate of the clean speech at time frame $t$ and $\otimes$ denotes element
wise multiplication. To train the model $g_{\theta}$, there are two key
objective variants. The first type minimizes an objective function $D$ such as
mean squared error (MSE) between the model estimated mask $\hat{m}_{m}$ and
the target mask ($tm$).

$\mathcal{L}=\sum_{u,t,f}D\mid tm_{u,t,f},\hat{m}_{u,t,f}\mid$

This approach however cannot effectively handle silences where $\mid
Y[t,n]\mid=0$ and $\mid X[t,n]\mid=0,$ because the target masks $tm$ will be
undefined at the silences bins. Note that target masks such ideal amplitude
mask involves division of $\mid X[t,n]\mid$ and $\mid Y[t,n]\mid$ hence
silence regions will make the target mask undefined [18]. This cost function
also focuses on minimizing the disparity between the masks instead of the
features of estimated signal and the target clean signal [18]. The second type
of cost function seeks to minimize the features of estimated signal
$\hat{S}_{t}=m_{t}\otimes Y[t,n]$ and those of target clean signal $S$.

$\mathcal{L}=\sum_{u,t,f}D\mid\hat{m}_{u,t}Y_{u,t,f},S_{u,t,f}\mid$

The sum is over all the speech $u$ and time-frequency bin $(t,f)$. Here, $Y$
and $S$ represents noisy and clean speech respectively. So, for DNN tools
using indirect estimation of clean signal features, instead of them estimating
the clean features directly from the noisy features input, the models first
estimate binary masks. The binary masks are then applied to the noisy features
to separate the sources (see figure 5, here, the features are the TF
spectrogram). This technique has been applied in [1] [16] [41] [42] [45] [50]
[51] [21] [52] [53] [54] [55] [14] [53] [27]. Due to the challenge of phase
estimation when working in time-frequency domain, different models such as
[56] [57] [8] [58] [59] [9] [60] [61][62] [63] [64] [65] explore the idea of
designing a deep learning model for speech separation that accepts speech
signal in the time-domain. The fundamental concept for these models is to
replace the DFT based input with a data-driven representation that is jointly
learned during model training. The models therefore accept as their input the
mixed raw waveform sound and then generates either the estimated clean sources
or masks that are applied on the noisy waveform to generate clean sources. By
working on the raw waveform, these models address two key limitations of DFT
based models. First, the models are designed to fully learn the magnitude and
phase information of the input signal during training [57]. Secondly, they
avoid reconstruction challenges faced when working with DFT features.

##  3 Contrastive deep modularization model (ConDeepMod)

Figure 1: The proposed framework for speech separation combining contrastive
learning and deep modularizing Network

The goal of contrastive self-supervised learning is to establish a
representation function $f:x\mapsto R^{d}$ that maps augmentations to a
$d-$dimensional vectors by ensuring that ’similar view’ of augmentations are
closer to each other as compared to those of random ones. The practise is to
pick augmentations $(x,x^{+})$ that are obtained by passing a given input
through two different augmentations functions. Essentially contrastive
learning tries to make representations of a given input invariant to
augmentations transformations [66]. Ideal augmentations of inputs are those
that retain features of the inputs that are crucial in the intended task( e.g
classification) but modify the features that are less important for that task.
In our case we intend to use the different frames of a speech from given
speaker to train a model to generate representations that can be used to
identify that speaker in a downstream clustering model. We hypothesize that
the different frames of a speech belonging to a given speaker qualify to be
viewed as augmentations of a standard hidden frame of that speaker in the
speech separation domain. For frames of a given speaker to qualify as
augmented versions of each other, they must retain important features for
speaker’s speech identity and modify the less important ones. Voice pitch i.e
the auditory perception of the rate of vocal fold vibration (the fundamental
frequency or F0), is perhaps the most important acoustic cue of talker
identity [67]. Other features that are exploited for speech separation include
vocal timbre, speaking rate that reveal indexical characteristics can be used
for talker identification. The question therefore is: do the different frames
of speech from a given speaker contain enough amount of overlap on prosodic
information (such as pitch and intensity) that are important to segregate the
frames of that speaker when the frames are mixed with those from other
speakers ?

To investigate this, we design a function $f:X\mapsto R^{d}$ that maps frames
to $d$-dimension vectors by encouraging representations of pairs of frames
from a given speaker to be closer to each other as compared to representations
of frames of another random speaker. Given, $n$ speeches from $n$ speakers, we
chunk each speech into equally sized frames. Let $\bar{X}$ denote the set of
all frames generated from speeches from different speakers. Let the function
$\mathcal{S}(.,.\mid\bar{X})$ be viewed as augmentation pair generator such
that it picks two pairs of frames from $\bar{X}$ belonging to the same speaker
i.e

$(x_{i},x_{i}^{+})\sim\mathcal{D}_{pos}\equiv(x_{i},x_{i}^{+})\sim\text{i.i.d
}\mathcal{S}(.,.\mid\bar{X})$ (3)

Here the pair $(x_{i},x_{i}^{+})$ is the positive pair with distribution
$\mathcal{D}_{pos}$. Given a batch size of $n$, for a positive pair
$(x_{i},x_{i}^{+})$, we consider all the other $n-2$ to be the negative
examples with a distribution of $\mathcal{D}_{neg}$. To train the model to fit
the function $f$, we use adopt simCLR contrastive loss [68].

$L(f)=\mathbb{E}_{x,x^{+}\sim D_{pos},x_{i:n-2}^{-}\sim
D_{neg}}[-\log(\frac{e^{f(x)^{T}f(x^{+})}}{e^{f(x)^{T}f(x^{+})}+\sum_{i=1}^{n-2}e^{f(x)^{T}f(x_{i}^{-})}})]$
(4)

The loss function seeks to make the similarity $f(x)f(x^{+})$ larger as
compared to $f(x)f(x^{-})$. Once the model is trained to establish frame level
features, we exploit the trained model in the downstream task.
Downstream task: We define a graph $G(V,E)$ where
$V=(v_{1},v_{2},\cdots,v_{n})$, $\mid V\mid=n$ is the set of all nodes
(frames) and $E\subset V\times V$, $\mid E\mid=m$ is the set of all edges. We
denote adjacency matrix of $G$ by $A$ where $A_{ij}=1$ iff
$\\{v_{i},v_{j}\\}\in E$ and 0 otherwise. The degree of $v_{i}$ is defined as
$d_{i}=\sum_{j}^{n}A_{ij}$, we are interested in generating graph partition
function $\mathcal{F}:V\rightarrow\\{1,\cdots,k\\}$ that splits the set of
nodes $V$ into $k$ partition $v_{i}=\\{v_{j}:\mathcal{F}(v_{j})=i\\}$ given
the nodes attributes $\bar{F}\in R^{n\times d}$ generated by contrastive
learning. To construct the adjacency matrix $A$, for each node $i$ we compute
its similarity with all other nodes using inner product i.e

$e_{ij}=\bar{f}_{i}^{T}\bar{f}_{j}$ (5)

where $j=1,2,\cdots,n$ and $\bar{f_{i}}$ and $\bar{f_{j}}\in\bar{F}$. We then
select a threshold $\theta$ such that if $e_{ij}<\theta$, we remove an edge
between $i$ and $j$ then the adjacency matrix is defined as

$A_{ij}=\begin{cases}1,&\text{if there is an edge between $i$ and {j}}\\\
0,&\text{otherwise}\end{cases}$ (6)

###  3.1 Deep modularity network

The downstream task seeks to cluster the frames of a mixed speech into $k$
different clusters. Given the feature representations $\bar{F}$ generated by
contrastive learning, we need to partition the frame features into $k$
partitions. We explore the idea of modularizing the learned features via deep
neural network graph partition technique proposed in [69],[70]. They propose
to partition nodes of a graph by the following formulation.

$\bar{F}=\text{GNN}(\tilde{A},X,\theta_{GNN})$ (7) $S=\text{softmax}(\bar{F})$
(8)

Where $\tilde{A}=D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$, $X$ are the input
features and $D$ is the diagonal matrix with the degrees $d_{1},\cdots,d_{n}$
on the diagonal. Node features $\bar{F}$ are learned via graph neural network
(GNN) and the assignment matrix S is established via softmax activation
function. In [70], the assignment matrix $S$ is established via multi-layer
perceptron (MLP) with softmax on the output layer. In our case, we formulate
the problem of clustering as

$\bar{F}=\text{Con}(X,\theta_{con})$ (9) $S=\text{MLP}(\bar{F},\theta_{mlp})$
(10)

The key difference being that our features are learned via contrastive
learning(Con) then we establish assignment matrix $S$ via MLP with softmax on
the output layer.

###  3.2 Modularity background

Modularity (Q) is defined according to equation 11 [71]

$Q=\text{Number of edges within a community - expected number of such edges}$
(11)

The expected number of edges involves choosing a null model against which to
compare the performance of clustering. This is formulated in [71] as

$Q=\frac{1}{2m}\sum_{ij}(A_{ij}-P_{ij})\delta(g_{i},g_{j})$ (12)

where $\delta(g_{i},g_{j})$ is 1 if vertex $i$ and $j$ belong to the same
group and $0$ otherwise. $P_{ij}$ is the expected number of edges between $i$
and $j$ while $A_{ij}$ is the actual number of edges between $i$ and $j$. If
vertex $i$ and $j$ have degrees $d_{i}$ and $d_{j}$ respectively then the
expected degree of vertex $i$ can be defined as $\sum_{j}P_{ij}=d_{i}$. Based
on this, vertex $i$ and $j$ are connected with probability
$P_{ij}=\frac{d_{i}d_{j}}{2m}$ (see [71]). Hence equation 12 is modified to

$Q=\frac{1}{2m}\sum_{ij}(A_{ij}-\frac{d_{i}d_{j}}{2m})\delta(g_{i},g_{j})$
(13)

Modularity therefore entails maximizing $Q$. The problem of maximizing $Q$ is
NP-Hard [72], however by recasting the problem as spectral relaxation, $Q$ can
be solved efficiently. Let $S\in(0,1)^{N\times K}$ be a cluster assignment
matrix such that $S_{ij}=1$ if node $i$ belong to cluster $j$ and 0 otherwise.
The modularity matrix $B$ is defined as $A-\frac{dd^{T}}{2m}$, hence
modularity $Q$ can now be defined as

$Q=\frac{1}{2m}Tr(S^{T}BS)$ (14)

By relaxing $S\in R^{N\times K}$ the optimal $S$ that maximizes $Q$ is the top
$k$ eigenvectors of matrix $B$. A number of algorithms working on graph
structure have been proposed to solve equation 14 efficiently(see [71]). Our
approach however is to exploit the node features $\bar{F}\in R^{n\times d}$
learned by contrastive learning and deep learning technique to establish
optimal $S$ that maximizes equation 14. Given $\bar{F}$ the matrix of node
(frames) established by contrastive learning, we compute cluster assignment of
node using MLP with softmax on the output layers. This maps each node feature
$\bar{f}_{i}\in\bar{F}$ into the $i$ row of the cluster assignment matrix $S$.
To optimize the assignment $S$ we use the loss function in equation 15 [69].
The right side of equation 15 is composed of two factors i.e., the modularity
and the collapse regularization. Collapse regularization is crucial to avoid
$S$ generating trivial clusters. Further, it has been demonstrated in [69]
that the loss function in equation 15 maintains consistency of community
detection as the number of nodes grows.

$L(S)=-\frac{1}{2m}Tr(S^{T}BS)+\frac{\sqrt{k}}{n}\mid\mid\sum_{i}S_{i}^{T}\mid\mid_{F}-1$
(15)

The complexity of $Tr(S^{T}BS)$ is $\mathcal{O}(n^{2})$ per update of $L(S)$
which is computationally costly. Therefore to efficiently update $L(S)$,
$Tr(S^{T}BS)$ is decomposed into sum of sparse matrix-matrix multiplication
and rank one degree normalization $Tr(SAS-Sdd^{T}S)$. This reduces complexity
to $\mathcal{(}O)(d^{2}n)$ for every update of the loss function.

###  3.3 Clean signal estimation

From the established $k$ clusters established through modularization, we
generate $k$ masks in the range $[0,1]$, where 0 signifies that a given frame
in the input mixed signal is missing in that cluster while 1 signifies
presence of a given frame. The mask based separation of sources is predicated
on the assumption of sparsity and orthogonality of the sources in the mixed
signal in the domain in which masks are being computed. Based on this
assumption, the dominant signal at a given range is taken to be only signal at
that range. Therefore, generation of clusters through modularization is to
estimate dominant signals at a given range. Once the masks have been
established, they are applied on the input mixed signal to generate $k$
estimated clean signals.

###  3.4 Model(f)

The model (encoder) $f$ which is used to establish frame representations is
made up of a stack of 6 identical layers. One such layer is shown in figure 2.
The layers are composed of layer normalization, 1D convolution and 1D
maxpooling.

Figure 2: The proposed Encoder, where Conv1D(x,y,z) represents a 1D
convolution with $filters=x$, kernel size$=y$ and $strides=z$. MaxPool(x,y) is
a 1D maxpooling with $poolsize=x$ and $strides=y$

.

##  4 Experiments

###  4.1 Dataset

To pre-train the model to generate frame level embeddings, we use the popular
Wall Street Journal (WSJ0) corpus and the AudioMNIST dataset [73]. For WSJO
dataset, we use training set while for AudioMNIST we use the whole dataset.
AudioMNIST dataset consists of 30,000 audio recordings of spoken digits (0-9).
Each digit is repeated 50 times for 60 different speakers. Given an audio we
generate frames of size 256 i.e. for an audio sampled at 8kHz, a frame of 32ms
is generated with a stride size of 8ms. We use Adam optimizer and use cyclical
learning rate [74] with a minimum learning rate of $1e-4$ and a maximum of
$1e-1$. For downstream task, we use wsj0-2mix and wsj0-3mix [10]. These
datasets are made of two-speaker and three-speaker mixtures respectively
created from the Wall Street Journal (WSJ0) corpus. The datasets are created
by exploiting randomly selected gains in order to achieve relative levels
between 0 and 5 dB between the two and three speech signals. The datasets are
composed of 30 h training, 10 h validation, and 5 h test sets. The training,
validation and test sets are composed of 20,000, 5,000 and 3,000 instantaneous
two-speaker mixtures respectively. The training and validation sets share
common speakers, which is not the case for test set. The speeches are sampled
at 8 kHz. In our case, we use the training and validation dataset to fine-tune
the pre-trained model and test dataset is exploited to evaluate the ability of
the model to generate clean speeches.

###  4.2 Quality of clusters

To begin our experiments, we first evaluate if the established frames (nodes)
features via contrastive learning technique can generate quality clusters when
MLP is exploited downstream to generate clusters. The loss used to train MLP
to generate clusters is shown in equation 15. To evaluate the quality of
clusters, after fine tuning the pre-trained model using the training and
validation set of wsj0-2mix, we use its test set for cluster generation.
Graph-based clustering metrics [75] is adopted for measuring cluster quality

  1. 1.

Cluster conductance (C)

$f(S)=\frac{c_{s}}{2m_{s}+c_{s}}$ (16)

where $S$ is a set of nodes, the function $f(S)$ measures the quality of
clusters in the nodes of $S$, $m_{s}$ is the number of edges in $S$ i.e
$m_{s}=\\{(u,v)\in E,u\in S,v\in S\\}$ and $c_{s}$ is the number of edges in
the boundary of $S$ i.e. $c_{s}=\\{(u,v)\in E:u\in S,v\notin S\\}$

  2. 2.

Graph modularity ($\mathcal{Q}$)

$f(S)=\frac{1}{4}(m_{s}-E(m_{s}))$ (17)

where $E(m_{s})$ is the expected $m_{s}$.

We compare the results with those produced by technique proposed in [69],
where graph convolution neural network (GCN) is used to generate node features
and MLP is used to derive clusters see equation 7 and 8. We replace the
softmax with MLP to enable direct comparison. Basically, we are comparing the
quality of node features generated via GCN and contrastive learning in
generating quality clusters. For GCN, we use one hidden layer with 512 neurons
the same parameters are used in [69]. When training both models using the loss
function in equation 15, the maximum number of clusters is set to 16. The
results in presented in table 1. We multiply the $f(S)$ of the two metrics by
100 for easy readability. The proposed technique establishes clusters with C
of 5.4 and $\mathcal{Q}$ of 86.2 as compared to those of GCN+MLP of 11.2 and
76.8 respectively. This is an indication that for these settings, the proposed
model for contrastive learning produces superior quality features as opposed
to GCN.

Table 1: Results of the two technique based on graph conductance C and modularity Q. Technique | C | $\mathcal{Q}$
---|---|---
Contrastive learning +MLP | 5.4 | 86.2
GCN+MLP | 11.2 | 76.8

##  5  Are the different frames of a given speaker augmented versions of a
hidden standard frame of that speaker ?

Here, we evaluate if any two augmentations of the same speech have enough
overlap i.e they are not disjoint.
Definition 1: Frames are said to be disjoint if for all distinct augmentation
selections $(x_{i},x_{i}^{+})$ and $(x_{j},x_{j}^{+})$ generated by
augmentation selection function $S(.,.\mid\bar{X})$, $(x_{i},x_{i}^{+})$ and
$(x_{j},x_{j}^{+})$ have a disjoint support.
A typical way to demonstrate that frames are disjoint is when there exist a
global minimizer of contrastive loss with a vacuous transfer on a downstream
task for representation dimension that is small compared to the size of the
input space [66]. To check if the frames of a given speaker are disjoint, we
evaluate the performance of representations generated with different
contrastive losses on quality of clusters produced. The results in shown in
table 2. From the results in table 2, contrastive loss has monotonic effect on
both graph conductance and modularity metrics signalling that the
augmentations have some overlap hence do not generate spurious
representations.

Table 2: Results of the two technique based on graph conductance C and modularity Q. Contrastive loss | C | $\mathcal{Q}$
---|---|---
5.62 | 57.3 | 18.2
5.32 | 57.2 | 17.3
5.0 | 62.4 | 15.3
4.9 | 64.9 | 11.4
4.6 | 64.9 | 11.4
4.3 | 76.7 | 8.4
3.7 | 86.5 | 5.4

##  6  Sources separation results

We evaluated the performance of the proposed technique based on contrastive
learning and deep modularization(ConDeepMod) on source separation on both
wsj0-2mix and wsj0-3mix test dataset. Table 3 reports the results based on the
evaluation metrics of SI-SNR improvement (SISNRi) and Signal-to-Distortion
Ratio improvement (SDRi). Further, we compare the results of ConDeepMod with
other state of the art techniques on speech separation. On WSJ0-2mix test-
dataset, ConDeepMod attains an SI-SNRi of 20.8 and SDRi of 21.0. It performs
slightly lower that the two versions of wavesplit and SepFormer. The strength
of the proposed technique is demonstrated as number of sources is increased.In
WSJ0-3mix test-dataset, it outperforms all the tools in both metrics. While
other tools register lower performance as compared to wsj0-2mix, ConDeepMod
even registers a slight improvement in performance. This shows that the
proposed technique using modularation is able to scale well with increased
number of sources in the mixed signal.

Table 3: Evaluation results of speech separation tools. Results on the
WSJ0-2mix test-dataset
---
Model | SI-SNRi | SDRi | parameters
SepFormer | 20.4 | 20.5 | 26
SepFormer+DM | 22.3 | 22.4 | 26
Wavesplit | 21.0 | 21.2 | 29
Wavesplit+DM | 22.2 | 22.3 | 29
DeepCASA | 17.7 | 18.0 | 12.8
ConvTasnet | 15.3 | 15.6 | 5.1
ConDeepMod | 20.8 | 21.0 | 2.1
Results on the WSJ0-3mix test-dataset
SepFormer | 17.6 | 17.9 | 26
SepFormer+DM | 19.5 | 19.7 | 26
Wavesplit | 17.3 | 17.6 | 29
Wavesplit+DM | 17.8 | 18.1 | 29
ConvTasnet | 12.7 | 13.1 | 5.1
ConDeepMod | 20.6 | 20.7 | 2.1

##  7 Limitations

This work has not investigated the performance of the proposed technique when
a mixed speech has noisy and reverberation. Further we did not evaluate the
impact of varying frame size on the performance of the proposed tool.

##  8 Conclusion

In this work we demonstrate that for speech separation task, the different
frames of a given speech belonging to a given individual can be vieewed as
augmentations of each other. The different frames contain enough overlap on
prosodic information which is key in speech separation. We exploit this fact
to implement a fully supervised technique which can achieve high quality
estimated clean speech from a mixed one. Moreover, the proposed technique is
competitive with the supervised based state of the art techniques.

## References

  * [1] Y. Wang and D. L. Wang, “Towards scaling up classification-based speech separation,” _IEEE Transactions on Audio, Speech and Language Processing_ , vol. 21, no. 7, pp. 1381–1390, 2013.
  * [2] Y. Wang, A. Narayanan, and D. L. Wang, “On training targets for supervised speech separation,” _IEEE/ACM Transactions on Audio Speech and Language Processing_ , vol. 22, no. 12, pp. 1849–1858, 2014.
  * [3] M. N. Schmidt and R. K. Olsson, “Single-channel speech separation using sparse non-negative matrix factorization,” _INTERSPEECH 2006 and 9th International Conference on Spoken Language Processing, INTERSPEECH 2006 - ICSLP_ , vol. 5, pp. 2614–2617, 2006.
  * [4] Z. Wang and F. Sha, “DISCRIMINATIVE NON-NEGATIVE MATRIX FACTORIZATION FOR SINGLE-CHANNEL SPEECH SEPARATION Zi Wang Department of Computer Science and Technology Tsinghua University Department of Computer Science University of Southern California Los Angeles , CA 90089,” _2014 IEEE International Conference on Acoustic, Speech and Signal Processing (ICASSP)_ , pp. 3777–3781, 2014. [Online]. Available: https://pdfs.semanticscholar.org/854a/454106bd42a8bca158426d8b12b48ba0cae8.pdf
  * [5] T. Virtanen and A. T. Cemgil, “Mixtures of gamma priors for non-negative matrix factorization based speech separation,” _Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)_ , vol. 5441, no. 3, pp. 646–653, 2009.
  * [6] T. Virtanen, “Speech recognition using factorial hidden Markov models for separation in the feature space,” _Proceedings of the Annual Conference of the International Speech Communication Association, INTERSPEECH_ , vol. 1, pp. 89–92, 2006.
  * [7] Y. Shao and D. Wang, “Model-based sequential organization in cochannel speech,” _IEEE Transactions on Audio, Speech and Language Processing_ , vol. 14, no. 1, pp. 289–298, 2006.
  * [8] Y. Luo and N. Mesgarani, “Conv-TasNet: Surpassing Ideal Time-Frequency Magnitude Masking for Speech Separation,” _IEEE/ACM Transactions on Audio Speech and Language Processing_ , vol. 27, no. 8, pp. 1256–1266, 2019.
  * [9] C. Subakan, M. Ravanelli, S. Cornell, M. Bronzi, and J. Zhong, “Attention is all you need in speech separation,” _ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings_ , vol. 2021-June, pp. 21–25, 2021.
  * [10] J. R. Hershey, Z. Chen, J. Le Roux, and S. Watanabe, “Deep clustering: Discriminative embeddings for segmentation and separation,” _ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings_ , vol. 2016-May, pp. 31–35, 2016.
  * [11] Y. Wang, J. Du, L. R. Dai, and C. H. Lee, “A gender mixture detection approach to unsupervised single-channel speech separation based on deep neural networks,” _IEEE/ACM Transactions on Audio Speech and Language Processing_ , vol. 25, no. 7, pp. 1535–1546, 2017.
  * [12] ——, “Unsupervised single-channel speech separation via deep neural network for different gender mixtures,” _2016 Asia-Pacific Signal and Information Processing Association Annual Summit and Conference, APSIPA 2016_ , 2017.
  * [13] N. Zeghidour and D. Grangier, “Wavesplit: End-to-End Speech Separation by Speaker Clustering,” _IEEE/ACM Transactions on Audio Speech and Language Processing_ , vol. 29, no. iv, pp. 2840–2849, 2021.
  * [14] P.-S. Huang, M. Kim, M. Hasegawa-Johnson, and P. Smaragdis, “DEEP LEARNING FOR MONAURAL SPEECH SEPARATION,” _Acta Physica Polonica B_ , vol. 42, no. 1, pp. 33–44, 2011.
  * [15] C. Weng, D. Yu, M. L. Seltzer, and J. Droppo, “Deep neural networks for single-channel multi-talker speech recognition,” _IEEE/ACM Transactions on Audio Speech and Language Processing_ , vol. 23, no. 10, pp. 1670–1679, 2015.
  * [16] Y. Isik, J. Le Roux, Z. Chen, S. Watanabe, and J. R. Hershey, “Single-channel multi-speaker separation using deep clustering,” _Proceedings of the Annual Conference of the International Speech Communication Association, INTERSPEECH_ , vol. 08-12-Sept, pp. 545–549, 2016.
  * [17] D. Yu, M. Kolbaek, Z. H. Tan, and J. Jensen, “Permutation invariant training of deep models for speaker-independent multi-talker speech separation,” _ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings_ , pp. 241–245, 2017.
  * [18] M. Kolbæk, D. Yu, Z. H. Tan, and J. Jensen, “Multitalker Speech Separation With Utterance-Level Permutation Invariant Training of Deep Recurrent Neural Networks,” _IEEE/ACM Transactions on Audio Speech and Language Processing_ , vol. 25, no. 10, pp. 1901–1913, 2017.
  * [19] H. Tachibana, “Towards listening to 10 people simultaneously: An efficient permutation invariant training of audio source separation using Sinkhorn’s algorithm,” _ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings_ , vol. 2021-June, pp. 491–495, 2021\.
  * [20] S. Dovrat, E. Nachmani, and L. Wolf, “Many-speakers single channel speech separation with optimal permutation training,” _Proceedings of the Annual Conference of the International Speech Communication Association, INTERSPEECH_ , vol. 4, pp. 2408–2412, 2021.
  * [21] J. R. Hershey, Z. Chen, J. L. Roux, and S. Watanabe, “DEEP CLUSTERING : DISCRIMINATIVE EMBEDDINGS FOR SEGMENTATION AND SEPARATION Mitsubishi Electric Research Laboratories ( MERL ), Cambridge , MA 02139 , USA,” _ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings_ , pp. 31–35, 2016.
  * [22] J. Byun and J. W. Shin, “Monaural speech separation using speaker embedding from preliminary separation,” _IEEE/ACM Transactions on Audio Speech and Language Processing_ , vol. 29, pp. 2753–2763, 2021.
  * [23] S. Qin, T. Jiang, S. Wu, N. Wang, and X. Zhao, “Graph convolution-based deep clustering for speech separation,” _IEEE Access_ , vol. 8, pp. 82 571–82 580, 2020.
  * [24] J. H. Lee, J. H. Chang, J. M. Yang, and H. G. Moon, “NAS-TasNet: Neural Architecture Search for Time-Domain Speech Separation,” _IEEE Access_ , vol. 10, pp. 56 031–56 043, 2022.
  * [25] F. Jiang and Z. Duan, “Speaker attractor network: Generalizing speech separation to unseen numbers of sources,” _IEEE Signal Processing Letters_ , vol. 27, pp. 1859–1863, 2020.
  * [26] E. Nachmani, Y. Adi, and L. Wolf, “Voice separation with an unknown number of multiple speakers,” _37th International Conference on Machine Learning, ICML 2020_ , vol. PartF16814, pp. 7121–7132, 2020.
  * [27] Y. Liu and D. Wang, “Divide and Conquer: A Deep CASA Approach to Talker-Independent Monaural Speaker Separation,” _IEEE/ACM Transactions on Audio Speech and Language Processing_ , vol. 27, no. 12, pp. 2092–2102, 2019.
  * [28] Y. Luo and N. Mesgarani, “Separating varying numbers of sources with auxiliary autoencoding loss,” _Proceedings of the Annual Conference of the International Speech Communication Association, INTERSPEECH_ , vol. 2020-October, pp. 2622–2626, 2020.
  * [29] J. Shi, J. Xu, G. Liu, and B. Xu, “Listen, think and listen again: Capturing top-down auditory attention for speaker-independent speech separation,” _IJCAI International Joint Conference on Artificial Intelligence_ , vol. 2018-July, pp. 4353–4360, 2018.
  * [30] K. Kinoshita, L. Drude, M. Delcroix, and T. Nakatani, “Listening to each speaker one by one with recurrent selective hearing networks,” _ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings_ , vol. 2018-April, pp. 5064–5068, 2018.
  * [31] N. Takahashi, S. Parthasaarathy, N. Goswami, and Y. Mitsufuji, “Recursive speech separation for unknown number of speakers,” _Proceedings of the Annual Conference of the International Speech Communication Association, INTERSPEECH_ , vol. 2019-September, pp. 1348–1352, 2019.
  * [32] T. V. Neumann, K. Kinoshita, M. Delcroix, S. Araki, T. Nakatani, and R. Haeb-Umbach, “All-neural Online Source Separation, Counting, and Diarization for Meeting Analysis,” _ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings_ , vol. 2019-May, pp. 91–95, 2019.
  * [33] T. von Neumann, C. Boeddeker, L. Drude, K. Kinoshita, M. Delcroix, T. Nakatani, and R. Haeb-Umbach, “Multi-talker ASR for an unknown number of sources: Joint training of source counting, separation and ASR,” _Proceedings of the Annual Conference of the International Speech Communication Association, INTERSPEECH_ , vol. 2020-October, pp. 3097–3101, 2020.
  * [34] S. W. Fu, T. W. Wang, Y. Tsao, X. Lu, H. Kawai, D. Stoller, S. Ewert, S. Dixon, X. Lu, Y. Tsao, S. Matsuda, C. Hori, Y. Xu, J. Du, L. R. Dai, C. H. Lee, T. Gao, J. Du, L. R. Dai, C. H. Lee, S. W. Fu, Y. Tsao, X. Lu, F. Weninger, J. R. Hershey, J. Le Roux, B. Schuller, Y. Xu, J. Du, L. R. Dai, C. H. Lee, F. Lluís, J. Pons, and X. Serra, “Speech enhancement based on deep denoising autoencoder,” _Proceedings of the Annual Conference of the International Speech Communication Association, INTERSPEECH_ , vol. 08-12-Sept, no. 1, pp. 7–19, 2018.
  * [35] E. M. Grais and M. D. Plumbley, “Single channel audio source separation using convolutional denoising autoencoders,” _2017 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2017 - Proceedings_ , vol. 2018-Janua, pp. 1265–1269, 2018.
  * [36] A. Jansson, E. Humphrey, N. Montecchio, R. Bittner, A. Kumar, and T. Weyde, “Singing voice separation with deep U-Net convolutional networks,” _Proceedings of the 18th International Society for Music Information Retrieval Conference, ISMIR 2017_ , pp. 745–751, 2017.
  * [37] M. Kim and P. Smaragdis, “Adaptive denoising autoencoders: A fine-tuning scheme to learn from test mixtures,” _Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)_ , vol. 9237, pp. 100–107, 2015.
  * [38] Y. Xu, J. Du, L. R. Dai, and C. H. Lee, “A regression approach to speech enhancement based on deep neural networks,” _IEEE/ACM Transactions on Audio Speech and Language Processing_ , vol. 23, no. 1, pp. 7–19, 2015.
  * [39] X. Lu, Y. Tsao, S. Matsuda, and C. Hori, “Speech enhancement based on deep denoising autoencoder,” _Proceedings of the Annual Conference of the International Speech Communication Association, INTERSPEECH_ , no. August, pp. 436–440, 2013.
  * [40] Y. Xu, J. Du, L. R. Dai, and C. H. Lee, “An experimental study on speech enhancement based on deep neural networks,” _IEEE Signal Processing Letters_ , vol. 21, no. 1, pp. 65–68, 2014.
  * [41] F. Weninger, J. R. Hershey, J. Le Roux, and B. Schuller, “Discriminatively trained recurrent neural networks for single-channel speech separation,” _2014 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2014_ , pp. 577–581, 2014.
  * [42] S. W. Fu, Y. Tsao, and X. Lu, “SNR-aware convolutional neural network modeling for speech enhancement,” _Proceedings of the Annual Conference of the International Speech Communication Association, INTERSPEECH_ , vol. 08-12-Sept, pp. 3768–3772, 2016.
  * [43] T. Gao, J. Du, L. R. Dai, and C. H. Lee, “SNR-based progressive learning of deep neural network for speech enhancement,” _Proceedings of the Annual Conference of the International Speech Communication Association, INTERSPEECH_ , vol. 08-12-Sept, pp. 3713–3717, 2016.
  * [44] D. S. Williamson and D. L. Wang, “Time-frequency masking in the complex domain for speech dereverberation and denoising,” _IEEE/ACM Transactions on Audio Speech and Language Processing_ , vol. 25, no. 7, pp. 1492–1501, 2017.
  * [45] A. Narayanan and D. Wang, “IDEAL RATIO MASK ESTIMATION USING DEEP NEURAL NETWORKS FOR ROBUST SPEECH RECOGNITION Arun Narayanan and DeLiang Wang Department of Computer Science and Engineering Center for Cognitive Science The Ohio State University,” _2013 IEEE International Conference on Acoustics, Speech and Signal Processing_ , pp. 7092–7096, 2013.
  * [46] H. Erdogan, J. R. Hershey, S. Watanabe, and J. Le Roux, “Phase-sensitive and recognition-boosted speech separation using deep recurrent neural networks,” _ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings_ , vol. 2015-Augus, pp. 708–712, 2015.
  * [47] U. Kjems, J. B. Boldt, M. S. Pedersen, T. Lunner, and D. Wang, “Role of mask pattern in intelligibility of ideal binary-masked noisy speech,” _The Journal of the Acoustical Society of America_ , vol. 126, no. 3, pp. 1415–1426, 2009.
  * [48] D. S. Brungart, P. S. Chang, B. D. Simpson, and D. Wang, “Isolating the energetic component of speech-on-speech masking with ideal time-frequency segregation,” pp. 4007–4018, 2006.
  * [49] S. A. Nossier, J. Wall, M. Moniri, C. Glackin, and N. Cannings, “A Comparative Study of Time and Frequency Domain Approaches to Deep Learning based Speech Enhancement,” _Proceedings of the International Joint Conference on Neural Networks_ , 2020.
  * [50] Z. Chen, S. Watanabe, H. Erdogan, and J. R. Hershey, “Speech enhancement and recognition using multi-task learning of long short-term memory recurrent neural networks,” in _Proceedings of the Annual Conference of the International Speech Communication Association, INTERSPEECH_ , vol. 2015-Janua, 2015, pp. 3274–3278.
  * [51] P. S. Huang, M. Kim, M. Hasegawa-Johnson, and P. Smaragdis, “Joint Optimization of Masks and Deep Recurrent Neural Networks for Monaural Source Separation,” _IEEE/ACM Transactions on Audio Speech and Language Processing_ , vol. 23, no. 12, pp. 2136–2147, 2015.
  * [52] E. M. Grais, M. U. Sen, and H. Erdogan, “Deep neural networks for single channel source separation,” _ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings_ , pp. 3734–3738, 2014.
  * [53] X. L. Zhang and D. Wang, “A deep ensemble learning method for monaural speech separation,” _IEEE/ACM Transactions on Audio Speech and Language Processing_ , vol. 24, no. 5, pp. 967–977, 2016.
  * [54] A. Narayanan and D. Wang, “Improving robustness of deep neural network acoustic models via speech separation and joint adaptive training,” _IEEE/ACM Transactions on Audio Speech and Language Processing_ , vol. 23, no. 1, pp. 92–101, 2015.
  * [55] F. Weninger, H. Erdogan, S. Watanabe, E. Vincent, J. Le Roux, J. R. Hershey, and B. Schuller, “Speech enhancement with LSTM recurrent neural networks and its application to noise-robust ASR,” _Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)_ , vol. 9237, pp. 91–99, 2015.
  * [56] Y. Luo and N. Mesgarani, “TaSNet: Time-Domain Audio Separation Network for Real-Time, Single-Channel Speech Separation,” _ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings_ , vol. 2018-April, pp. 696–700, 2018.
  * [57] Y. Luo, Z. Chen, and T. Yoshioka, “Dual-Path RNN: Efficient Long Sequence Modeling for Time-Domain Single-Channel Speech Separation,” _ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings_ , vol. 2020-May, pp. 46–50, 2020.
  * [58] S. Venkataramani, J. Casebeer, and P. Smaragdis, “END-TO-END SOURCE SEPARATION WITH ADAPTIVE FRONT-ENDS University of Illinois at Urbana Champaign University of Illinois at Urbana Champaign Adobe Research,” _2018 52nd Asilomar Conference on Signals, Systems, and Computers_ , no. 1, pp. 684–688, 2018.
  * [59] L. Zhang, Z. Shi, J. Han, A. Shi, and D. Ma, “FurcaNeXt: End-to-end monaural speech separation with dynamic gated dilated temporal convolutional networks,” _Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)_ , vol. 11961 LNCS, pp. 653–665, 2020.
  * [60] E. Tzinis, S. Venkataramani, Z. Wang, C. Subakan, and P. Smaragdis, “Two-Step Sound Source Separation: Training on Learned Latent Targets,” _ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings_ , vol. 2020-May, pp. 31–35, 2020.
  * [61] E. Tzinis, Z. Wang, and P. Smaragdis, “Sudo RM -RF: Efficient networks for universal audio source separation,” _IEEE International Workshop on Machine Learning for Signal Processing, MLSP_ , vol. 2020-Septe, 2020.
  * [62] Z. Kong, W. Ping, A. Dantrey, and B. Catanzaro, “Speech Denoising in the Waveform Domain With Self-Attention,” _ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings_ , vol. 2022-May, pp. 7867–7871, 2022.
  * [63] J. Su, Z. Jin, and A. Finkelstein, “HiFi-GAN: High-fidelity denoising and dereverberation based on speech deep features in adversarial networks,” _Proceedings of the Annual Conference of the International Speech Communication Association, INTERSPEECH_ , vol. 2020-October, no. 3, pp. 4506–4510, 2020.
  * [64] M. W. Lam, J. Wang, D. Su, and D. Yuy, “Sandglasset: A Light Multi-Granularity Self-Attentive Network for Time-Domain Speech Separation,” _ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings_ , vol. 2021-June, pp. 5759–5763, 2021\.
  * [65] M. W. Lam, J. Wang, D. Su, and D. Yu, “Effective Low-Cost Time-Domain Audio Separation Using Globally Attentive Locally Recurrent Networks,” _2021 IEEE Spoken Language Technology Workshop, SLT 2021 - Proceedings_ , pp. 801–808, 2021.
  * [66] N. Saunshi, J. Ash, S. Goel, D. Misra, C. Zhang, S. Arora, S. Kakade, and A. Krishnamurthy, “Understanding contrastive learning requires incorporating inductive biases,” 2 2022. [Online]. Available: http://arxiv.org/abs/2202.14037
  * [67] X. Xie and E. Myers, “The impact of musical training and tone language experience on talker identification,” _The Journal of the Acoustical Society of America_ , vol. 137, pp. 419–432, 1 2015.
  * [68] T. Chen, S. Kornblith, M. Norouzi, and G. Hinton, “A simple framework for contrastive learning of visual representations,” 2 2020. [Online]. Available: http://arxiv.org/abs/2002.05709
  * [69] A. Tsitsulin, J. Palowitch, B. Perozzi, and E. Müller, “Graph clustering with graph neural networks,” 6 2020. [Online]. Available: http://arxiv.org/abs/2006.16904
  * [70] F. M. Bianchi, D. Grattarola, and C. Alippi, “Spectral clustering with graph neural networks for graph pooling,” 2020.
  * [71] M. E. Newman, “Finding community structure in networks using the eigenvectors of matrices,” _Physical Review E - Statistical, Nonlinear, and Soft Matter Physics_ , vol. 74, 2006.
  * [72] U. Brandes, D. Delling, M. Gaertler, R. Görke, M. Hoefer, Z. Nikoloski, and D. Wagner, “Maximizing modularity is hard,” 2006.
  * [73] S. Becker, M. Ackermann, S. Lapuschkin, K.-R. Müller, and W. Samek, “Interpreting and explaining deep neural networks for classification of audio signals,” 7 2018. [Online]. Available: http://arxiv.org/abs/1807.03418
  * [74] L. N. Smith, “Cyclical learning rates for training neural networks,” 6 2015. [Online]. Available: http://arxiv.org/abs/1506.01186
  * [75] J. Yang and J. Leskovec, “Defining and evaluating network communities based on ground-truth,” 5 2012. [Online]. Available: http://arxiv.org/abs/1205.6233


# A Method for Decrypting Data Infected with Rhysida Ransomware

Giyoon Kim<EMAIL_ADDRESS>Soojin Kang<EMAIL_ADDRESS>Seungjun
Baek<EMAIL_ADDRESS>Kimoon Kim<EMAIL_ADDRESS>Jongsung Kim
<EMAIL_ADDRESS>[

###### Abstract

Ransomware is malicious software that is a prominent global cybersecurity
threat. Typically, ransomware encrypts data on a system, rendering the victim
unable to decrypt it without the attacker’s private key. Subsequently, victims
often pay a substantial ransom to recover their data, yet some may still incur
damage or loss. This study examines Rhysida ransomware, which caused
significant damage in the second half of 2023, and proposes a decryption
method. Rhysida ransomware employed a secure random number generator to
generate the encryption key and subsequently encrypt the data. However, an
implementation vulnerability existed that enabled us to regenerate the
internal state of the random number generator at the time of infection. We
successfully decrypted the data using the regenerated random number generator.
To the best of our knowledge, this is the first successful decryption of
Rhysida ransomware. We aspire for our work to contribute to mitigating the
damage inflicted by the Rhysida ransomware.

###### keywords:

Rhysida , Ransomware , Malware analysis , Data recovery , Reverse engineering
, Cybersecurity

url]https://dfnc.kookmin.ac.kr

fn1fn1footnotetext: These authors contributed equally to this work.

[label1]organization=Dept. of Financial Information Security,
addressline=Kookmin University,77 Jeongneung-Ro, Seongbuk-Gu, city=Seoul,
postcode=02707, country=Republic of Korea

[label2]organization=Dept. of Information Security, Cryptology, and
Mathematics, addressline=Kookmin University,77 Jeongneung-Ro, Seongbuk-Gu,
city=Seoul, postcode=02707, country=Republic of Korea

[label3] addressline=Korea Internet & Security Agency (KISA), 9, Wolgok-gil,
Dasi-myeon, city=Naju, postcode=58324, country=Republic of Korea

##  1 Introduction

The world is undergoing rapid digitalization, with digital technology services
gaining unprecedented popularity. Concurrently, the rise in cybersecurity
threats is noteworthy. Ransomware is a prominent threat that infiltrates
systems to encrypt user data and demand payment for decryption. Ransomware,
through data encryption, not only leads to data loss but also disrupts the
organization’s services. When ransomware infects an infrastructure that serves
a large user base, both the infrastructure and its users suffer damage. As a
result, for the victim, paying the ransom emerges as a practical choice.

Advanced ransomware not only encrypts data but also carries out data
exfiltration, frequently using double extortion tactics that threaten to
delete the exfiltrated data. Furthermore, there has been a rise in triple
extortion schemes, offering analysis of victims’ vulnerabilities and advice on
prevention [1], As the scale of ransomware damage grows, global
recommendations for proactive responses are actively disseminated and
formulated into policies. Implementing proactive measures such as installing
anti-virus software, regular software updates, and creating backups can
effectively minimize the damage caused by ransomware. Despite these efforts,
ransomware-induced damage persists, underscoring the significance of post-
counteraction studies for data after ransomware infection.

When analyzing ransomware, the most desirable thing is to find the key used to
encrypt the data, but this is not an easy task. Since ransomware typically
employs a hybrid encryption system, it is difficult to find the key without
obtaining the attacker’s private key. Therefore, researchers diligently work
to develop decryption methods through reverse engineering by identifying
weaknesses in ransomware implementations.

In developing ransomware decryption methods, there are instances where key
regeneration is possible. If key regeneration succeeds, the next step is to
determine the specific key used to encrypt each encrypted file. Ransomware
often employs multiprocessing for swift encryption, thereby introducing a
potential randomization factor in the order of file encryption, despite the
sequential generation of encryption keys. This can pose a challenge for
researchers developing decryption tools.

In this study, we analyze the Rhysida ransomware, which emerged in 2023 and
affected numerous victims, including hospitals. Despite its randomized order
of file access for encryption and the absence of a developed decryption tool,
our results reveal the feasibility of decrypting Rhysida ransomware.

#### Our Contributions

Our contributions are summarized as follows:

  1. 1.

We performed an in-depth analysis of Rhysida Ransomware. Through a
comprehensive analysis of Rhysida Ransomware, we identified an implementation
vulnerability, enabling us to regenerate the encryption key used by the
malware. Subsequently, we developed a recovery tool111Currently, the developed
recovery tool is being distributed through the Korea Internet & Security
Agency (KISA) [5] for systems infected with Rhysida ransomware, which requires
no additional information.

#### Paper Organization

This paper is organized as follows. Section 2 provides an introduction to
related work. Section 3 outlines the operation of Rhysida ransomware. Section
4 details a decryption method for Rhysida ransomware derived from our
analysis. The paper concludes with Section 5.

##  2 Related Work

Ransomware research spans various fields and is categorized into proactive and
reactive responses. Proactive responses leverage domain knowledge to minimize
ransomware damage by employing techniques such as hash databases, Yara rules,
and similarity analysis. Prevention methods, such as creating decoys, halt
infection onset and minimize harm. Reactive responses focus on damage recovery
after infection, involving tasks such as collecting encryption keys, backing
up data, and developing decryption methods. Similar to this study, other some
studies attempted to decrypt data by identifying vulnerabilities in
ransomware.

Lee et al. analyzed Magniber v2 ransomware and devised a method to decrypt it
without the need for the attacker’s private key [6]. They identified a
vulnerability in the pseudo-random number generator used to generate
encryption keys in Magniber v2, which significantly reduced the number of
potential encryption keys. Employing CBC padding rules and NIST’s SP800-22
randomness test suite [10], they successfully determined the actual encryption
key, enabling the decryption of data. In addition, Lee et al. analyzed the
encryption processes of five major ransomware variants in 2019 (Gandcrab v5,
Clop, Sodinokibi, Phobos, and LooCipher), outlining scenarios where decryption
is possible [7]. LooCipher exhibited a vulnerability in its pseudo-random
number generator, as identified by Lee, who demonstrated the possibility of
decrypting all data by exploiting this weakness.

Kang et al. analyzed Ragnar Locker ransomware and proposed a data decryption
method [3]. Their research revealed that the Rangnar Locker improperly used
stream ciphers, making it susceptible to reused key attacks. They concluded
that if the originals of certain data could be obtained, it was possible to
decrypt all remaining data without the originals through a key reuse attack.

Yuste et al. developed a decryption method for the Avaddon ransomware,
developing an open source tool for decrypting the Avaddon ransomware family
[11]. They further integrated their tool with existing antivirus engines to
decrypt ransomware using an encryption process similar to that of Avaddon.

Kim et al. analyzed the HIVE ransomware and developed a method to decrypt
encrypted data without requiring the attacker’s private key [4]. They
demonstrated that the HIVE ransomware uses a custom encryption algorithm with
vulnerabilities. The ransomware encrypts the original data by XORing it with
two random numbers, thereby generating a linear equation. The authors
demonstrated that this equation could be used to infer the encryption key and
showed the possibility that if the key is reused, the encrypted data can be
decrypted.

These studies achieved data decryption by exploiting implementation
vulnerabilities in ransomware. Although there are similarities with our study,
the findings are not applicable to the Rhysida ransomware that we analyzed. In
addition, each of these studies had a clear order in which files were
encrypted. In contrast, our study distinguishes itself by assuming an unknown
order of file access for encryption.

##  3 Analysis of Rhysida Ransomware

In this section, we analyze the encryption process of Rhysida ransomware. The
Rhysida ransomware, compiled with MinGW GNU version 6.3.0, exists as either a
32-bit or 64-bit PE file. We conduct our analysis on 11 Rhysida ransomware
sample files, and Table 1 displays the SHA256 hash values for each sample.
Using the x64 debugger [9], we examined the ransomware. Rhysida ransomware
exclusively uses LibTomCrypt [2] for encryption. To expedite data encryption,
Rhysida ransomware performs parallel processing by creating sub-threads
equivalent to the number of processors on the victim PC. This chapter
describes Rhysida ransomware, with a focus on three essential parts for
decrypting the data: identification of factors for regenerating the encryption
key, determination of the encryption target, and the data encryption process.

Table 1: SHA256 hash values of the Rhysida ransomware sample files

SHA256 Hash Values
---
A864282FEA5A536510AE86C77CE46F7827687783628E4F2CEB5BF2C41B8CD3C6
0BB0E1FCFF8CCF54C6F9ECFD4BBB6757F6A25CB0E7A173D12CF0F402A3AE706F
F6F74E05E24DD2E4E60E5FB50F73FC720EE826A43F2F0056E5B88724FA06FBAB
1A9C27E5BE8C58DA1C02FC4245A07831D5D431CDD1A91CD35D2DD0AD62DA71CD
2C5D3FEA7AD3C9C49E9C1A154370229C86C48FBAF7044213FD85D31EFCEBF7F6
3D2013C2BA0AA1C0475CAB186DDF3D9005133FE5F88B5D8604B46673B96A40D8
67A78B39E760E3460A135A7E4FA096AB6CE6B013658103890C866D9401928BA5
250E81EEB4DF4649CCB13E271AE3F80D44995B2F8FFCA7A2C5E1C738546C2AB1
258DDD78655AC0587F64D7146E52549115B67465302C0CBD15A0CBA746F05595
3518195C256AA940C607F8534C91B5A9CD453C7417810DE3CD4D262E2906D24F
D5C2F87033A5BAEEB1B5B681F2C4A156FF1C05CCD1BFDAF6EAE019FC4D5320EE

###  3.1 Identification the factors for regenerating the encryption key

Decrypting data encrypted using a symmetric-key cryptographic algorithm
requires the encryption key used in the process. Since encryption keys can be
generated in various methods, it is important to identify the factors used by
ransomware in the key generation process during data encryption.

In this study, we categorize encryption key generation methods into two types:
generation based on a specific value (not a random number) or generation based
on a random number. The former involves generating the encryption key using a
fixed or inferred specific value, which is easily regenerable through
ransomware analysis. In the latter case, the key is generated based on a
random number, necessitating the identification of the random number generator
used for encryption and the internal state of the generator at that time. The
random number generator takes a seed as input, sets it as the initial internal
state, and generates a sequence of random numbers according to a defined rule.
Therefore, if we can identify the initial internal state, regenerating the
random number becomes feasible.

Rhysida ransomware uses a cryptographically secure pseudo-random number
generator (CSPRNG) to generate the encryption key. This generator uses a
cryptographically secure algorithm to generate random numbers. Our analysis
revealed that Rhysida ransomware uses CSPRNG, which is based on the ChaCha20
algorithm provided by the LibTomCrypt library. To enhance the randomness of
its internal state, CSPRNG can be input with random entropy data. Rhysida
ransomware updates its internal state once by incorporating specific entropy
data before using CSPRNG. The entropy data is a 40–byte random number
generated by the rand function in the C standard library. The initial seed of
the rand function is set based on the time at which Rhysida ransomware is
running. After updating the internal state of CSPRNG, Rhysida ransomware
verifies its proper functioning by generating a random number equivalent to
sizeof(long). During this process, the internal state of CSPRNG is incremented
by 4 bytes for x86 and 8 bytes for x64, depending on the compiled version of
Rhysida ransomware. The initialization of the CSPRNG process terminates if the
random number is successfully generated. In addition, to parallelize data
encryption, Rhysida ransomware creates sub-threads equal to the number of
processors on the victim PC, assigning a distinct CSPRNG to each thread.
However, in contrast to sub-threads, which are created corresponding to the
number of processes, the initialization of the CSPRNG process by Rhysida
ransomware is performed for a total of #(Processors) + 1. Consequently, this
leads to the generation of #(Processors) + 1 CSPRNGs. However, the first
initialized CSPRNG remains unused, and from the subsequent CSPRNG onward, it
is sequentially assigned to previously created sub-threads. Figure 1 shows the
initialization process of the Rhysida ransomware’s random number generator.

Figure 1: CSPRNG initialize process

######  Observation 1.

Our analysis reveals that the random number generated by the CSPRNG is based
on the execution time of the Rhysida ransomware. The time value used as a
seed, being 32-bit data, does not offer a large space for conducting an
exhaustive search Thus, the number of possible cases of CSPRNG is up to
$2^{32}$.

###  3.2 Determination of the encryption target

Before encrypting data, ransomware selects a target to be encrypted. The
process of identifying encryption targets can be categorized into two methods.
The first method is the on-the-fly approach, which involves traversing folders
and encrypting files immediately. The second method is the list-up approach,
which involves traversing the folder, initially listing the files, and
subsequently performing encryption by referencing these listed files.
Traversing folders encompasses four types of approaches, including depth-first
search (DFS), which prioritizes entering a folder first, and breadth-first
search (BFS), which traverses files within a folder first. In each case,
ascending and descending orders can be applied. When the entire process of
identifying encryption targets is exclusively performed by the main process,
determining the order of file encryption becomes feasible through analysis.
However, if this process is executed in parallel, it can pose challenges for
an analyst in determining the order of file encryption.

Our findings indicate that the main process of Rhysida ransomware compiles a
list of encryption targets, and the encryption threads reference this list for
data encryption. The main process traverses the entire drive in ascending
order, employing DFS, and subsequently pushes the encryption target list to
the stack of encryption threads. Simultaneously, the encryption thread
performs the encryption by popping the target to be encrypted from its own
stack, with the order of file access for encryption being determined by the
last in, first out (LIFO) order. If the current stack reaches full capacity,
the main process suspends pushing data and waits until the current stack is
ready to accommodate data. Due to the distinct threads handling the push and
pop processes, the final order of the encrypted files becomes disordered.
Figure 2 outlines the file selection process used for encryption by Rhysida
ransomware.

Figure 2: Rhysida ransomware file selection process when there are two
processes on the PC

To successfully decrypt data after regenerating the encryption key, it is
crucial to identify the order in which the encryption keys were used. However,
in the absence of explicit rules governing the order of file encryption, a
workaround becomes necessary. The file system stores mtime (modification time)
for each file. When a file is encrypted, its mtime is changed. This change
provides insight into the order in which the file was encrypted. However, in
cases where files share the same mtime (due to small file size or intermittent
encryption for swift processing), distinguishing the order of file access for
encryption becomes essential. This leads to the following observation.

######  Observation 2.

Accurately determining the whole order of files for encryption is possible
when distinguishing the order in instances where the files have the same
mtime.

###  3.3 Data encryption process

Ransomware commonly encrypts data in two ways. The first method is the whole
encryption technique, which encrypts the entire file. The second method is the
intermittent encryption technique, which gained popularity with the emergence
of LockBit ransomware [8]. Intermittent encryption involves partially
encrypting files and can be implemented in various ways. A typical approach is
to encrypt nbytes and then leave mbytes unencrypted, repeating this process
until the entire file is encrypted. While parts of the file remain in
plaintext due to intermittent encryption, the file becomes unusable, and the
encryption speed increases.

Rhysida ransomware implemented intermittent encryption, encrypting 1 MiB from
a specific offset (O). The calculation of Ois as follows:

$\displaystyle div$
$\displaystyle=\begin{cases}4&\text{if}\quad\text{fileSize}\geq
4\text{--MiB}\\\ \lfloor\frac{\text{fileSize}}{1\text{ MiB}}\rfloor&\text{elif
}1\text{--MiB}\leq\text{fileSize}<4\text{--MiB}\\\ 1&\text{else}\end{cases}$
(1) $\displaystyle O$
$\displaystyle=\\{\lfloor\frac{\text{fileSize}}{div}\rfloor\times i\mid
i\in\text{range(div)}\\}$ (2)

If the fileSize is less than 1 MiB, the entire data is encrypted. For the
fileSize is ranging from 1 MiB to less than 2 MiB, the top 1 MiB is encrypted.
In the case of fileSize ranging from 2 MiB to less than 3 MiB, the data are
divided into two parts, and the starting 1 MiB of each part is encrypted. For
the fileSize ranging from 3 MiB to less than 4 MiB, the data are divided into
three parts, and the starting 1 MiB of each part is encrypted. For the
fileSize is 4 MiB or more, the data are divided into four parts, and the
starting 1 MiB of each part is encrypted.

The data was encrypted using the AES–256–CTR (Little-Endian) encryption mode,
utilizing a 32–byte encryption key and a 16–byte IV. These key and IV were
generated by the CSPRNG assigned to each encryption thread. Rhysida ransomware
concludes the process by using a hardcoded RSA–4096 public key to encrypt each
randomly generated encryption key and IV, storing them at the end of the file.

Both AES and RSA, which were used for encryption, employed the LibTomCrypt
library. For RSA, Rhysida ransomware uses the optimal asymmetric encryption
padding (OAEP) technique. OAEP requires a random number and a hash function.
Therefore, the Rhysida ransomware uses a CSPRNG and a block cipher-based hash
function assigned to the encryption thread. Figure 3 outlines the data
encryption process of the Rhysida ransomware.

Figure 3: The intermittent encryption process of Rhysida ransomware

Successfully decrypting data encrypted by ransomware requires precise
identification of both the encryption method and the encryption key. Since the
encryption method of Rhysida ransomware is already known, it does not need to
be considered. Indeed, it is important to determine the encryption key from
the random numbers generated by the CSPRNG. The CSPRNG generates random
numbers four times during the encryption process: for encryption key
generation, IV generation, encryption of the encryption key (RSA), and
encryption of the IV (RSA). The encryption key is 32 bytes, the IV is 16
bytes, and the size of the random number generated within the OAEP is 16
bytes. Within the OAEP, two instances of 16-byte random numbers are generated:
one during the encryption of the encryption key and another during the
encryption of the IV. This leads to the following observation.

######  Observation 3.

In the encryption process of the Rhysida ransomware, the encryption thread
generates 80 bytes of random numbers when encrypting a single file. Of these,
the first 48 bytes are used as the encryption key and the IV.

##  4 Decryption Methodology of Rhysida Ransomware

We analyzed the Rhysida ransomware operation described in the previous
sections to identify the elements required for decryption. Decrypting data
encrypted by Rhysida ransomware requires reconstruction of the encryption key
and determination of the order of file encryption. This chapter provides a
detailed description of each process and presents the results of decrypting
the Rhysida ransomware based on these findings.

###  4.1 Methods for regenerating the encryption keys

The initially used seed must regenerate all the correct encryption keys. With
$2^{32}$ cases of seed, there are enough possibilities to regenerate all types
of encryption keys. However, this approach is inefficient, requiring more than
$2^{32}$ decryption trials for each file. Therefore, a validation method is
needed to find the seed. As a verification method, we decrypted the first file
encrypted by each encryption thread.

Initially, we assessed the number of encryption threads (processors) employed
on the victim’s system, which is represented as #(Processors). Following this,
we established a random seed to generate a CSPRNG in a manner similar to that
of the Rhysida ransomware. Subsequently, we arranged the files encrypted by
the Rhysida ransomware in ascending order based on mtime and selected the
first #(Processors). In this context, we evaluated whether the number of files
that overlapped with the mtime of the first file is greater than or less than
#(Processors). The following conditions were considered:

  1. i

If the number of files that overlap with the mtime of the initial file is less
than #(Processors).

Rhysida ransomware prevents overlap when the main process assigns the
encryption target to the encryption thread. Subsequently, the encryption key
is generated sequentially from the CSPRNG to encrypt the data. Therefore, in
this case, the selected #(Processors) files must include at least one file
encrypted with the first encryption key per encryption thread.

  2. ii

The number of files that overlap with the first file’s mtime is more than
#(Processors).

In cases where the file size is sufficiently small, leading to rapid
encryption, the mtime overlap may be greater than #(Processors). Consequently,
#(Processors) files may not include any files encrypted with the first
encryption key per encryption thread. For example, if the second or third file
encrypted by a thread shares the same mtime as the first file, the order of
file encryption may vary depending on the sorting method. This implies that
the number of files to be selected to ensure that at least one file is
encrypted with the first encryption key is #(Processors)$\times$N, where N is
the smallest integer that satisfies (#(Processors)$\times$N $>$ mtime is the
number of overlapping files).

Figure 4: The process of obtaining the initial seed of the Rhysida ransomware

Finally, we decrypted the selected #(Processors)$\times$N files with the first
encryption key per encryption thread.

Correct decryption of encrypted data relies on the encryption key used at the
time of encryption. Therefore, if the correct encryption key is regenerated,
one or more files will be decrypted correctly. By iteratively generating
encryption keys with different seeds and identifying a file decrypted
correctly using the key, we can conclude that we have found the initial seed.
Furthermore, through analysis, the initial seed used by Rhysida ransomware is
the time at the moment of encryption. Efficient retrieval of the initial seed
involves examining integers smaller than mtime of files encrypted by Rhysida
ransomware. Figure 4 outlines the process of obtaining the initial seed for
decrypting Rhysida ransomware.

###  4.2 Methods for reconstructing the order of file encryption

The file list generation process of the Rhysida ransomware can be inferred
from the operation of the main process and the mtime of the files. The main
process traverses drives based on the DFS in ascending order. file list
generation process of the Rhysida ransomware can be inferred from the
operation of the main process and the mtime of the files. The main process
traverses drives based on the DFS in ascending order. In addition, during
drive traversal, it stores the j–th file in the stack in the (j mod
#(Processors))+1–th encryption thread.

While the actual order of encryption may not be sequential due to LIFO, we can
assert that the list being assigned to the encryption thread is even.
Replicating this process allows us to compile a list of files accessed by each
thread. However, as mentioned above, the order of encryption within the list
may not be sequential. Therefore, it is essential to rearrange the order of
file for encryption in list.

Sorting the list of files accessed by threads based on mtime allows us to
determine the comprehensive file access order. First, we assume that the mtime
values of the encrypted files are all different. For a specific thread engaged
in encryption to proceed with encrypting the subsequent file in the list, it
must complete the encryption of the current file. Given distinct mtime values,
the list of files sorted by mtime represents the order of file encryption.

Subsequently, we consider scenarios where some files share identical mtime. If
the size of the file to be encrypted is very small, encryption may be
completed in the same mtime. In such instances, the list of files can be
divided into a subset with identical mtime and other files. The order of file
encryption is guaranteed for all files except the subset. For example, if
there are five file lists, where the first file shares the same mtime as the
second file and the fourth file shares mtime with the fifth file, encryption
is performed sequentially. Consequently, the first and second files are
encrypted using either the first or second encryption key. The third file,
which has a different mtime from the second and fourth files, is encrypted
with the third encryption key. In addition, it can be determined that the
fourth and fifth files are encrypted using the fourth or fifth encryption key,
respectively. In essence, the order of file encryption can be inferred by
resolving the subset resulting from the same mtime.

Before deducing the order of file encryption, we must consider the maximum
number of possible overlaps of mtime. In the Windows environment, mtime is
calculated in µs. Consequently, all encryptable files within a 1 µs timeframe
share the same mtime. For AES in the LibTomCrypt library used by the Rhysida
ransomware, the AES roundkey generation process requires approximately 1400
cycles, and the encryption process requires 18 cycles per byte. Therefore,
with a CPU performance of 6 GHz and no additional processing cycles, such as
I/O, except for encryption, up to four data can be encrypted in the same
mtime. However, in this case, the combined size of the four data cannot exceed
22 bytes. If three data are to be encrypted, their total size cannot exceed
100 bytes. Furthermore, for two data to be encrypted, the combined size must
not exceed 177 bytes. Consequently, we determined that having up to four data
with the same mtime is impractical. In these cases, it is effective to decrypt
all files in a subset using all encryption keys.

###  4.3 Methods for decrypting encrypted data

Rhysida ransomware used intermittent encryption with the AES-–256–CTR
algorithm. Data encrypted in CTR mode can be decrypted by performing
encryption once more., effectively constituting a decryption process. However,
upon analyzing the encryption procedure of Rhysida ransomware, we observed an
increase in file size during encryption compared with the original. To
facilitate the normal decryption of data upon ransom payment, Rhysida
ransomware appends the following information at the end of the file:
RSA–encrypted encryption key, RSA–encrypted IV and 4–byte version information.
Consequently, the encrypted data are larger than the original data by 0x40C
bytes. Because intermittent encryption is based on the size of the original
file, it is crucial to eliminate these appended data. Otherwise, the
calculation of the encryption location will be incorrect. Consequently, to
ensure accurate decryption, it is imperative to delete the last 0x40C bytes of
encrypted data before performing intermittent encryption with the correct
encryption key. Figure 5 shows the decryption results for files encrypted by
Rhysida ransomware. Our results demonstrate that encrypted files can be
successfully decrypted.

Figure 5: Decryption result of Rhysida ransomware

##  5 Conclusion

This paper introduces a method for decrypting files affected by Rhysida
ransomware through a thorough analysis that uncovers implementation
vulnerabilities. Leveraging these vulnerabilities, we successfully
reconstructed the encryption key and restored the encrypted system. Despite
the prevailing belief that ransomware renders data irretrievable without
paying the ransom. Although these studies have a limited scope, it is
important to acknowledge that certain ransomwares, as exemplified in this
paper, can be successfully decrypted. We anticipate further studies in this
direction to aid ransomware victims, and that our findings will benefit those
affected by the Rhysida ransomware.

## Acknowledgement

This work was supported by Korea Internet & Security Agency (KISA) grant
funded by the Korea government (Ministry of Science and ICT, MSIT)

## References

  * Abrams [2021] Abrams, L., 2021.  Computer giant acer hit by $50 million ransomware attack.  https://www.bleepingcomputer.com/news/security/computer-giant-acer-hit-by-50-million-ransomware-attack/.
  * Denis [2018] Denis, T.S., 2018.  Libtomcrypt - comprehensive, modular, and portable cryptographic toolkit.  https://www.libtom.net/LibTomCrypt/.  Public domain cryptographic toolkit.
  * Kang et al. [2021] Kang, S., Lee, S., Kim, S., Kim, D., Kim, K., Kim, J., 2021.  A study on decryption of files infected by ragnar locker ransomware through key reuse attack and its applications.  Journal of the Korea Institute of Information Security & Cryptology 31, 221–231.
  * Kim et al. [2022] Kim, G., Kim, S., Kang, S., Kim, J., 2022.  A method for decrypting data infected with hive ransomware.  Journal of Information Security and Applications 71, 103387.
  * KISA [2023] KISA, 2023.  Rhysida ransomware recovery tool.  https://seed.kisa.or.kr/kisa/Board/166/detailView.do.  Rhysida Ransomware Recovery Tool.
  * Lee et al. [2021] Lee, S., Park, M., Kim, J., 2021.  Magniber v2 ransomware decryption: Exploiting the vulnerability of a self-developed pseudo random number generator.  Electronics 10, 16\.
  * Lee et al. [2019] Lee, S., Youn, B., Kim, S., Kim, G., Lee, Y., Kim, D., Park, H., Kim, J., 2019.  A study on encryption process and decryption of ransomware in 2019.  Journal of the Korea Institute of Information Security & Cryptology 29, 1339–1350.
  * Milenkoski and Walter [2022] Milenkoski, A., Walter, J., 2022\.  Crimeware trends — ransomware developers turn to intermittent encryption to evade detection.  https://www.sentinelone.com/labs/crimeware-trends-ransomware-developers-turn-to-intermittent-encryption-to-evade-detection/.
  * Ogilvie [2024] Ogilvie, D., 2024.  x64dbg - an open-source x64/x32 debugger for windows.  https://x64dbg.com/.  Features support for various debugging tasks.
  * Rukhin [2001] Rukhin, A., 2001.  Nist special publication 800-22.  http://csrc. nist. gov/rng/SP800-22b. pdf .
  * Yuste and Pastrana [2021] Yuste, J., Pastrana, S., 2021\.  Avaddon ransomware: An in-depth analysis and decryption of infected systems.  Computers & Security 109, 102388\.